CMSA: A recent example of an ILP-based hybrid metaheuristic

Abstract

CMSA (Construct, Merge, Solve & Adapt) was developed by our group in 2016 as an alternative to LNS (Large Neighborhood Search). It is a hybrid metaheuristic which iteratively generates sub-instances to the original problem instances and solves these sub-instances by means of any available exact technique. So far the techniques has been applied to combinatorial optimization problems that can be modelled in terms of integer linear programming. Therefore, ILP solvers such as CPLEX habe been used so far as exact solution methods within CMSA. In this keynote talk we first provided a general description of CMSA, together with illustrative examples. Second, we presented a recent work that sheds light on the relation of CMSA with LNS. Third, our latest work in this context concerns an optimization problem for which no efficient exact method is known (not even for medium size problem instances). We experimentally showed that, in this case, it is even beneficial to replace the exact technique within CMSA with a standard metaheuristic. In other words, the performance of the standard metaheuristic could be significantly improved by applying it within the CMSA framework.