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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
