Creating and sharing knowledge for telecommunications

Project: SearchCol: Meta-heuristic Search by Column generation

Acronym: SearchCol
Main Objective: Many relevant practical problems can be modeled as combinatorial optimization problems (COPs). Examples are the definition of routes for vehicles, schedules for machines, or the dimensioning of telecommunication networks. Meta-heuristics (MHs), such as tabu search or genetic algorithms, are the most successful methods in providing good-quality solutions in reasonable amounts of time for large-size instances of several COPs.

The aim of this project is to propose a new MH, entitled Search by Column generation (SearchCol), for COPs. SearchCol algorithms will be applied in specific problems from four areas: production planning and scheduling, telecommunications, forest management, and cutting and packing. The main distinctive feature of SearchCol is that its ingredients (such as construction of solutions, neighborhood structures, or crossover operators) are based on column generation (CG).

We aim at proving that a suitable search strategy (provided by the hybrid MHs framework) taking advantage of decomposition exact methods (CG) quickly leads to high-quality solutions for NP-hard COPs. The evidence is that CG provides tight lower bounds (in minimization problems) on the optimal value and that the columns belonging to the restricted master problem define a search space where high-quality solutions exist.

The drawbacks of standard MHs (the lack of ameasure of the quality of the solution obtained and the lack of a well defined stopping criterion) are overcome in SearchCol since the lower bound provided by CG is available.
Reference: PTDC/EIA-EIA/100645/2008
Funding: FCT/PTDC
Start Date: 01-04-2010
End Date: 01-04-2013
Team: Amaro Fernandes de Sousa, Dorabella Martins da Silva Santos
Groups: Applied Mathematics - Av
Partners: Universidade do Minho (Principal contractor), Fundação da Faculdade de Ciências, Universidade de Lisboa, Instituto Superior de Engenharia do Porto
Local Coordinator: Amaro Fernandes de Sousa
Internal Page
Associated Publications