Extension of the CMSA algorithm: An LP-based way for reducing sub-instances

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.