publication . Part of book or chapter of book . Preprint . 2018

Generic CP-Supported CMSA for Binary Integer Linear Programs

Blum, Christian; Santos, Haroldo Gambini;
Open Access
  • Published: 30 May 2018
  • Publisher: Springer International Publishing
Abstract
Construct, Merge, Solve and Adapt (CMSA) is a general hybrid metaheuristic for solving combinatorial optimization problems. At each iteration, CMSA (1) constructs feasible solutions to the tackled problem instance in a probabilistic way and (2) solves a reduced problem instance (if possible) to optimality. The construction of feasible solutions is hereby problem-specific, usually involving a fast greedy heuristic. The goal of this paper is to design a problem-agnostic CMSA variant whose exclusive input is an integer linear program (ILP). In order to reduce the complexity of this task, the current study is restricted to binary ILPs. In addition to a basic problem...
Subjects
free text keywords: Mathematical optimization, Greedy algorithm, Local consistency, Metaheuristic, Integer, Probabilistic logic, Binary Integer Decimal, Linear programming, Binary number, Computer science, Computer Science - Artificial Intelligence
Download fromView all 2 versions
http://arxiv.org/pdf/1805.1182...
Part of book or chapter of book
Provider: UnpayWall
http://link.springer.com/conte...
Part of book or chapter of book . 2018
Provider: Crossref
20 references, page 1 of 2

[1] Tobias Achterberg. Constraint Integer Programming'. PhD thesis, 2007.

[2] David L. Applegate, Robert E. Bixby, Vasek Chvatal, and William J. Cook. The traveling salesman problem: a computational study. Princeton university press, 2007.

[3] Thierry Benoist, Bertrand Estellon, Frederic Gardi, Romain Megel, and Karim Nouioua. Localsolver 1.x: a black-box local-search solver for 0-1 programming. 4OR, 9(3):299, 2011.

[4] Christian Blum. Construct, merge, solve and adapt: Application to unbalanced minimum common string partition. In Maria J. Blesa, Christian Blum, Angelo Cangelosi, Vincenzo Cutello, Alessandro Di Nuovo, Mario Pavone, and El-Ghazali Talbi, editors, Proceedings of HM 2016 { 10th International Workshop on Hybrid Metaheuristics, volume 9668 of Lecture Notes in Computer Science, pages 17{31. Springer International Publishing, 2016.

[5] Christian Blum and Maria J. Blesa. A comprehensive comparison of metaheuristics for the repetition-free longest common subsequence problem. Journal of Heuristics, 2017. In press. [OpenAIRE]

[6] Christian Blum, Pedro Pinacho, Manuel Lopez-Iban~ez, and Jose A. Lozano. Construct, merge, solve & adapt: A new general algorithm for combinatorial optimization. Computers & Operations Research, 68:75{ 88, 2016.

[7] Andreas T. Ernst and Gaurav Singh. Lagrangian particle swarm optimization for a resource constrained machine scheduling problem. In 2012 IEEE Congress on Evolutionary Computation, pages 1{8, 2012.

[8] Matteo Fischetti, Fred Glover, and Andrea Lodi. The feasibility pump. Mathematical Programming, 104(1):91{104, 2005. [OpenAIRE]

[9] Matteo Fischetti and Domenico Salvagnin. Feasibility pump 2.0. Mathematical Programming Computation, 1(2):201{222, 2009.

[10] Robert Fourer, David Gay, and Brian Kernighan. AMPL, volume 117. Boyd & Fraser Danvers, MA, 1993.

[11] Gerald Gamrath, Thorsten Koch, Alexander Martin, Matthias Miltenberger, and Dieter Weninger. Progress in Presolving for Mixed Integer Programming. Mathematical Programming Computation, 7:367{ 398, 2015.

[12] E.L. Johnson, G. Nemhauser, and W.P. Savelsbergh. Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition. INFORMS Journal on Computing, 12, 2000. [OpenAIRE]

[13] Thorsten Koch, Tobias Achterberg, Erling Andersen, Oliver Bastert, Timo Berthold, Robert E Bixby, Emilie Danna, Gerald Gamrath, Ambros M Gleixner, Stefan Heinz, et al. Miplib 2010. Mathematical Programming Computation, 3(2):103, 2011.

[14] Gary Kochenberger, Jin-Kao Hao, Fred Glover, Mark Lewis, Zhipeng Lu, Haibo Wang, and Yang Wang. The unconstrained binary quadratic programming problem: a survey. Journal of Combinatorial Optimization, 28(1):58{81, 2014.

[15] Evelia Lizarraga, Maria J. Blesa, and Christian Blum. Construct, merge, solve and adapt versus large neighborhood search for solving the multi-dimensional knapsack problem: Which one works better when? In Bin Hu and Manuel Lopez-Iban~ez, editors, Proceedings of EvoCOP 2017 { 17th European Conference on Evolutionary Computation in Combinatorial Optimization, volume 10197 of Lecture Notes in Computer Science, pages 60{74. Springer International Publishing, 2017.

20 references, page 1 of 2
Related research
Abstract
Construct, Merge, Solve and Adapt (CMSA) is a general hybrid metaheuristic for solving combinatorial optimization problems. At each iteration, CMSA (1) constructs feasible solutions to the tackled problem instance in a probabilistic way and (2) solves a reduced problem instance (if possible) to optimality. The construction of feasible solutions is hereby problem-specific, usually involving a fast greedy heuristic. The goal of this paper is to design a problem-agnostic CMSA variant whose exclusive input is an integer linear program (ILP). In order to reduce the complexity of this task, the current study is restricted to binary ILPs. In addition to a basic problem...
Subjects
free text keywords: Mathematical optimization, Greedy algorithm, Local consistency, Metaheuristic, Integer, Probabilistic logic, Binary Integer Decimal, Linear programming, Binary number, Computer science, Computer Science - Artificial Intelligence
Download fromView all 2 versions
http://arxiv.org/pdf/1805.1182...
Part of book or chapter of book
Provider: UnpayWall
http://link.springer.com/conte...
Part of book or chapter of book . 2018
Provider: Crossref
20 references, page 1 of 2

[1] Tobias Achterberg. Constraint Integer Programming'. PhD thesis, 2007.

[2] David L. Applegate, Robert E. Bixby, Vasek Chvatal, and William J. Cook. The traveling salesman problem: a computational study. Princeton university press, 2007.

[3] Thierry Benoist, Bertrand Estellon, Frederic Gardi, Romain Megel, and Karim Nouioua. Localsolver 1.x: a black-box local-search solver for 0-1 programming. 4OR, 9(3):299, 2011.

[4] Christian Blum. Construct, merge, solve and adapt: Application to unbalanced minimum common string partition. In Maria J. Blesa, Christian Blum, Angelo Cangelosi, Vincenzo Cutello, Alessandro Di Nuovo, Mario Pavone, and El-Ghazali Talbi, editors, Proceedings of HM 2016 { 10th International Workshop on Hybrid Metaheuristics, volume 9668 of Lecture Notes in Computer Science, pages 17{31. Springer International Publishing, 2016.

[5] Christian Blum and Maria J. Blesa. A comprehensive comparison of metaheuristics for the repetition-free longest common subsequence problem. Journal of Heuristics, 2017. In press. [OpenAIRE]

[6] Christian Blum, Pedro Pinacho, Manuel Lopez-Iban~ez, and Jose A. Lozano. Construct, merge, solve & adapt: A new general algorithm for combinatorial optimization. Computers & Operations Research, 68:75{ 88, 2016.

[7] Andreas T. Ernst and Gaurav Singh. Lagrangian particle swarm optimization for a resource constrained machine scheduling problem. In 2012 IEEE Congress on Evolutionary Computation, pages 1{8, 2012.

[8] Matteo Fischetti, Fred Glover, and Andrea Lodi. The feasibility pump. Mathematical Programming, 104(1):91{104, 2005. [OpenAIRE]

[9] Matteo Fischetti and Domenico Salvagnin. Feasibility pump 2.0. Mathematical Programming Computation, 1(2):201{222, 2009.

[10] Robert Fourer, David Gay, and Brian Kernighan. AMPL, volume 117. Boyd & Fraser Danvers, MA, 1993.

[11] Gerald Gamrath, Thorsten Koch, Alexander Martin, Matthias Miltenberger, and Dieter Weninger. Progress in Presolving for Mixed Integer Programming. Mathematical Programming Computation, 7:367{ 398, 2015.

[12] E.L. Johnson, G. Nemhauser, and W.P. Savelsbergh. Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition. INFORMS Journal on Computing, 12, 2000. [OpenAIRE]

[13] Thorsten Koch, Tobias Achterberg, Erling Andersen, Oliver Bastert, Timo Berthold, Robert E Bixby, Emilie Danna, Gerald Gamrath, Ambros M Gleixner, Stefan Heinz, et al. Miplib 2010. Mathematical Programming Computation, 3(2):103, 2011.

[14] Gary Kochenberger, Jin-Kao Hao, Fred Glover, Mark Lewis, Zhipeng Lu, Haibo Wang, and Yang Wang. The unconstrained binary quadratic programming problem: a survey. Journal of Combinatorial Optimization, 28(1):58{81, 2014.

[15] Evelia Lizarraga, Maria J. Blesa, and Christian Blum. Construct, merge, solve and adapt versus large neighborhood search for solving the multi-dimensional knapsack problem: Which one works better when? In Bin Hu and Manuel Lopez-Iban~ez, editors, Proceedings of EvoCOP 2017 { 17th European Conference on Evolutionary Computation in Combinatorial Optimization, volume 10197 of Lecture Notes in Computer Science, pages 60{74. Springer International Publishing, 2017.

20 references, page 1 of 2
Related research
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Part of book or chapter of book . Preprint . 2018

Generic CP-Supported CMSA for Binary Integer Linear Programs

Blum, Christian; Santos, Haroldo Gambini;