Replacing Hard Mathematical Models with Set Covering Formulations

Many packing, routing, and knapsack problems can be expressed both in terms of standard assignment-type integer linear programming models and in terms of set-covering-based models. Black-box solvers such as CPLEX and Gurobi find it generally very hard to solve assignment-type mathematical models of these problems. Therefore, the Operations Research community has developed specific exact and heuristic techniques that exploit set-covering-based models. In this chapter, it is shown that integer linear programming models based on set covering can also be very useful for their use within CMSA. In particular, this is shown by applications of CMSA to the Variable-Sized Bin Packing (VSBP) problem and to the Electric Vehicle Routing Problem with Time Windows and Simultaneous Pickups and Deliveries (EVRP-TW-SPD). In both applications, CMSA based on a set covering model significantly outperforms CMSA when using an assignment-type model. Moreover, state-of-the-art results are obtained for both considered optimization problems.