Please use this identifier to cite or link to this item: http://hdl.handle.net/1822/26805

TitleCombining column generation and metaheuristics
Author(s)Alvelos, Filipe Pereira e
Sousa, Amaro
Santos, Dorabella
Issue date2013
PublisherSpringer
JournalStudies in Computational Intelligence
CitationF. Alvelos, A. Sousa, D. Santos, Combining Column Generation and Metaheuristics, in Hybrid Metaheuristics, El-Ghazali Talbi (editor), Springer, 2013, pp 285-334. ISBN: 978-3-642-30670-9 (Print) 978-3-642-30671-6 (Online)
Abstract(s)In this Chapter, we consider the hybridization of column generation (CG) with metaheuristics (MHs) for solving integer programming and combinatorial optimization problems.We describe a general framework entitled ”metaheuristic search by column generation” (for short, SearchCol). CG is a decomposition approach in which one linear programming master problem interacts with subproblems to obtain an optimal solution to a relaxed version of a problem. The subproblems may be solved by problem-specific algorithms. After CG is applied, a set of subproblem’s solutions, optimal primal and dual values of the master problem variables and a lower bound to the optimal value of the problem are available. In contrast with enumerative approaches (e.g, branch-and-price), in SearchCol the information provided by CG is used in a MH search. The search is based on representing a solution (to the overall problem) as being composed by one solution from each subproblem. After a search is conducted, a perturbation for CG is defined and a new iteration begins. The perturbation consists in forcing or forbidding attributes of the subproblem’s solutions and, in general, leads to the generation of new subproblem’s solutions and different optimal primal and dual values of the master problem variables. In this Chapter, we discuss (i) which models are suitable for decomposition approaches as SearchCol, (ii) different alternatives for generating initial solutions for the search (with different degrees of randomization, greediness and influence of CG) (iii) different search approaches based on local search, (iv) different alternatives for perturbing CG (influenced by CG, based on the incumbent, and based on the memory of the search).
TypeBook part
URIhttp://hdl.handle.net/1822/26805
ISBN978-3-642-30670-9
DOI10.1007/978-3-642-30671-6_11
ISSN1860-949X
Publisher versionhttp://www.springer.com/engineering/computational+intelligence+and+complexity/book/978-3-642-30670-9
Peer-Reviewedyes
AccessRestricted access (UMinho)
Appears in Collections:CAlg - Livros e capítulos de livros/Books and book chapters

Files in This Item:
File Description SizeFormat 
AlvelosAl13_book.pdf
  Restricted access
467,16 kBAdobe PDFView/Open

Partilhe no FacebookPartilhe no TwitterPartilhe no DeliciousPartilhe no LinkedInPartilhe no DiggAdicionar ao Google BookmarksPartilhe no MySpacePartilhe no Orkut
Exporte no formato BibTex mendeley Exporte no formato Endnote Adicione ao seu ORCID