TY - GEN

T1 - Extension of the CMSA algorithm

T2 - 2016 Genetic and Evolutionary Computation Conference, GECCO 2016

AU - Blum, Christian

AU - Pereira, Jordi

PY - 2016/7/20

Y1 - 2016/7/20

N2 - Construct, Merge, Solve, & Adapt (CMSA) is a recently proposed hybrid algorithm for combinatorial optimization. At each iteration, the algorithm solves a subinstance of the original problem instance by means of an exact technique. The incumbent sub-instance is adapted at each iteration, first, by adding solution components present in probabilistically constructed solutions; and, second, by removing solution components that have reached a certain age limit and that do not appear in the optimal solution to the current sub-instance. In this work we propose a refined way for selecting the solution components to be removed from the current sub-instance in those cases in which the exact method employed is an integer linear programming solver. More specifically, the information on the reduced costs of the solution components with respect to the linear programming solution is used for this purpose. Experimental results for the chosen test case, the multidimensional knapsack problem, demonstrate the usefulness of this extension of CMSA.

AB - Construct, Merge, Solve, & Adapt (CMSA) is a recently proposed hybrid algorithm for combinatorial optimization. At each iteration, the algorithm solves a subinstance of the original problem instance by means of an exact technique. The incumbent sub-instance is adapted at each iteration, first, by adding solution components present in probabilistically constructed solutions; and, second, by removing solution components that have reached a certain age limit and that do not appear in the optimal solution to the current sub-instance. In this work we propose a refined way for selecting the solution components to be removed from the current sub-instance in those cases in which the exact method employed is an integer linear programming solver. More specifically, the information on the reduced costs of the solution components with respect to the linear programming solution is used for this purpose. Experimental results for the chosen test case, the multidimensional knapsack problem, demonstrate the usefulness of this extension of CMSA.

KW - Hybrid algorithms

KW - ILP solvers

KW - Metaheuristics

UR - http://www.scopus.com/inward/record.url?scp=84985930134&partnerID=8YFLogxK

U2 - 10.1145/2908812.2908830

DO - 10.1145/2908812.2908830

M3 - Conference contribution

AN - SCOPUS:84985930134

T3 - GECCO 2016 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference

SP - 285

EP - 292

BT - GECCO 2016 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference

A2 - Friedrich, Tobias

PB - Association for Computing Machinery, Inc

Y2 - 20 July 2016 through 24 July 2016

ER -