Kernel search is a purely matheuristic method, which leverages MIP solvers to obtain heuristic, or possibly optimal, solutions of instances encoded as (mixed) integer linear programming problems. It was first presented as a method to solve mixed-integer linear problems defined on binary variables modeling items selection, together with other integer or continuous variables related to the selected items, and later extended also to problems that do not involve a selection stage. The central idea of kernel search is to use some method, for example, the LP-relaxation, to identify a subset (named kernel) of promising decision variables and then to partition the remaining ones into buckets, which are concatenated one at a time to the kernel in order to check whether improving solutions can be found. An example along these lines is proposed in this chapter for the GAP.

Maniezzo, V., Boschetti, M.A., Stützle, T. (2021). Kernel Search. Cham : Springer [10.1007/978-3-030-70277-9_9].

Kernel Search

Maniezzo, Vittorio;Boschetti, Marco Antonio;
2021

Abstract

Kernel search is a purely matheuristic method, which leverages MIP solvers to obtain heuristic, or possibly optimal, solutions of instances encoded as (mixed) integer linear programming problems. It was first presented as a method to solve mixed-integer linear problems defined on binary variables modeling items selection, together with other integer or continuous variables related to the selected items, and later extended also to problems that do not involve a selection stage. The central idea of kernel search is to use some method, for example, the LP-relaxation, to identify a subset (named kernel) of promising decision variables and then to partition the remaining ones into buckets, which are concatenated one at a time to the kernel in order to check whether improving solutions can be found. An example along these lines is proposed in this chapter for the GAP.
2021
Matheuristics
189
197
Maniezzo, V., Boschetti, M.A., Stützle, T. (2021). Kernel Search. Cham : Springer [10.1007/978-3-030-70277-9_9].
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/832905
 Attenzione

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

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