SearchCol : metaheuristic search by column generation

Abstract

We propose a general framework for the combination of column generation (CG) with metaheuristics (MHs) aiming to solve combinatorial optimization problems amenable for decomposition approaches, "SearchCol". The combination of the two approaches is based on representing the solution of the problem as the selection of a subset of solutions of smaller (sub)problems which are generated by CG. In each iteration of a SearchCol algorithm, CG provides the optimal solution (primal and dual) to the MH which returns a (incumbent) solution used for defining the (perturbed) CG problem of the next iteration. We describe the SearchCol framework and a general SearchCol algorithm based on local search.