Author(s): Alvelos, Filipe Pereira e ; Sousa, Amaro ; Santos, Dorabella
Date: 2010
Persistent ID: http://hdl.handle.net/1822/26845
Origin: RepositóriUM - Universidade do Minho
Subject(s): Combinatorial optimization; Column generation; Hybrid metaheuristics; Matheuristics; Science & Technology
Apresentação efetuada no "Hybrid Metaheuristics : 7th International Workshop (HM 2010), Vienna, Austria, October 1-2, 2010.
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.
This work have been partially funded by FCT (Fundacao para a Ciencia e a Tecnologia - Portugal) through project SearchCol: Metaheuristic search by column generation (PTDC/EIA-EIA/100645/2008) and through the post-doc grant SFRH/BPD/41581/2007 of D. Santos.
