Fore-and-Back, previously also denoted as Forward&Backward or simply as F&B (though the algorithm presented in this chapter differs in some details from the previously published ones), is an extension of beam search that can improve its effectiveness and that, when run with no limits on computational resources, becomes an exact solution method. However, by design, Fore-and-Back is mainly concerned with heuristic solving, trying to quickly get high quality solutions with little attention paid to optimality proofs. A significant characteristic of this method is that, despite being a primal only method, it is able to compute bounds to the cost of completing partial solutions, therefore to discard partial solutions from expansion and ultimately to reduce the search space.

Fore-and-Back

Maniezzo, Vittorio;Boschetti, Marco Antonio;
2021

Abstract

Fore-and-Back, previously also denoted as Forward&Backward or simply as F&B (though the algorithm presented in this chapter differs in some details from the previously published ones), is an extension of beam search that can improve its effectiveness and that, when run with no limits on computational resources, becomes an exact solution method. However, by design, Fore-and-Back is mainly concerned with heuristic solving, trying to quickly get high quality solutions with little attention paid to optimality proofs. A significant characteristic of this method is that, despite being a primal only method, it is able to compute bounds to the cost of completing partial solutions, therefore to discard partial solutions from expansion and ultimately to reduce the search space.
2021
Matheuristics
199
211
Maniezzo, Vittorio; Boschetti, Marco Antonio; Stützle, Thomas
File in questo prodotto:
File Dimensione Formato  
Chapter - Fore and Back - Maniezzo Boschetti Stuzle.pdf

accesso aperto

Tipo: Postprint
Licenza: Licenza per accesso libero gratuito
Dimensione 8.41 MB
Formato Adobe PDF
8.41 MB Adobe PDF Visualizza/Apri

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/832907
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact