Creating and sharing knowledge for telecommunications

SearchCol: Metaheuristic Search by Column Generation

Alvelos, F. ; Sousa, A. F. ; Santos, D.

SearchCol: Metaheuristic Search by Column Generation, Proc International Workshop on Hybrid Metaheuristics - HM, Vienna, Austria, Vol. 6373, Lecture Notes on Computer Sciences, pp. 190 - 205, October, 2010.

Digital Object Identifier:

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.