Decompositions are methods derived from the “divide et impera” principle, dictating to break up a difficult problem into smaller ones, and to solve each of the smaller ones separately, ultimately recomposing the individual solutions to get the overall one. Decompositions have longly been applied to solve optimization problems, and they come in many different flavors, ranging from constraint programming to logical decomposition, from dynamic programming to linear decompositions, among many others. In this text, we are interested in heuristic approaches. We present three related mathematical decomposition techniques that have been used as seeds for classes of heuristic algorithms, plainly to be included among matheuristics, namely Lagrangian, Dantzig–Wolfe, and Benders decompositions. A detailed presentation and a run trace will be presented for a Lagrangian heuristic.

Maniezzo, V., Boschetti, M.A., Stützle, T. (2021). Decomposition-Based Heuristics. Cham : Springer [10.1007/978-3-030-70277-9_7].

Decomposition-Based Heuristics

Maniezzo, Vittorio;Boschetti, Marco Antonio;
2021

Abstract

Decompositions are methods derived from the “divide et impera” principle, dictating to break up a difficult problem into smaller ones, and to solve each of the smaller ones separately, ultimately recomposing the individual solutions to get the overall one. Decompositions have longly been applied to solve optimization problems, and they come in many different flavors, ranging from constraint programming to logical decomposition, from dynamic programming to linear decompositions, among many others. In this text, we are interested in heuristic approaches. We present three related mathematical decomposition techniques that have been used as seeds for classes of heuristic algorithms, plainly to be included among matheuristics, namely Lagrangian, Dantzig–Wolfe, and Benders decompositions. A detailed presentation and a run trace will be presented for a Lagrangian heuristic.
2021
Matheuristics
159
177
Maniezzo, V., Boschetti, M.A., Stützle, T. (2021). Decomposition-Based Heuristics. Cham : Springer [10.1007/978-3-030-70277-9_7].
Maniezzo, Vittorio; Boschetti, Marco Antonio; Stützle, Thomas
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/832901
 Attenzione

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

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