Decomposition techniques are well-known as a means for obtaining tight lower bounds for combinatorial optimization problems, and thus as a component for solution methods. Moreover a long-established research literature uses them for defining problem-specific heuristics. More recently it has been observed that they can be the basis also for designing metaheuristics. This tutorial elaborates this last point, showing how the three main decomposition techniques, namely Dantzig-Wolfe, Lagrangean and Benders decompositions, can be turned into model-based, dual-aware metaheuristics. A well known combinatorial optimization problem, the Single Source Capacitated Facility Location Problem, is then chosen for validation, and the implemented codes of the proposed algorithms are benchmarked on standard instances from literature.

M.A. Boschetti, V. Maniezzo, M. Roffilli (2010). Decomposition Techniques as Metaheuristic Frameworks. NEW YORK : Springer [10.1007/978-1-4419-1306-7_5].

Decomposition Techniques as Metaheuristic Frameworks

BOSCHETTI, MARCO ANTONIO;MANIEZZO, VITTORIO;
2010

Abstract

Decomposition techniques are well-known as a means for obtaining tight lower bounds for combinatorial optimization problems, and thus as a component for solution methods. Moreover a long-established research literature uses them for defining problem-specific heuristics. More recently it has been observed that they can be the basis also for designing metaheuristics. This tutorial elaborates this last point, showing how the three main decomposition techniques, namely Dantzig-Wolfe, Lagrangean and Benders decompositions, can be turned into model-based, dual-aware metaheuristics. A well known combinatorial optimization problem, the Single Source Capacitated Facility Location Problem, is then chosen for validation, and the implemented codes of the proposed algorithms are benchmarked on standard instances from literature.
2010
Matheuristics, Hybridizing Metaheuristics and Mathematical Programming
135
158
M.A. Boschetti, V. Maniezzo, M. Roffilli (2010). Decomposition Techniques as Metaheuristic Frameworks. NEW YORK : Springer [10.1007/978-1-4419-1306-7_5].
M.A. Boschetti; V. Maniezzo; M. Roffilli
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/87115
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 70
social impact