| 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 |
| Links:
http://searchcol.dps.uminho.pt/ Internal Page |
|
|
|
Associated Publications
|
