Fore-and-Back

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.