Construct, Merge, Solve & Adapt: A Hybrid Approach With a Resemblance to Evolutionary Algorithms

Abstract

Construct, Merge, Solve & Adapt (CMSA) is a recent hybrid algorithm for solving combinatorial optimization problems. This algorithm tackles reduced problem instances in an iterative way by making use, for example, of general-purpose integer linear programming (ILP) solvers. This is very similar to the use of so-called optimal recombination operators in the field of evolutionary algorithms. In this talk, the standard CMSA algorithm will, first, be introduced by means of examples. Subsequently, the focus of the presentation will shift to the following recent developments. The first one deals with the use of a learning method (ant colony optimization) for the generation of the reduced problem instances at each iteration. The second one is about a problem-independent version of CMSA for solving any combinatorial problem that can be modeled as a binary integer linear program.