Why Branch-and-Bounds Are Meta-Heuristics

EasyChair Preprint no. 2647

Abstract

We present a branch-and-bound family called "anytime" which is usually found in AI/planning. One of its member well-known in OR is Beam Search. Such algorithms are able to find good solutions fast and then try to improve them if possible. This approach is similar to classical meta-heuristics, but anytime branch-and-bounds happen to be more efficient in some cases. We present here two of these cases: cutting & packing problems and an asymmetrical TSP with precedence constraints.

Keyphrases: Challenge EURO/ROADEF 2018, framework générique, Meta-heuristiques, Recherches Arborescentes, sequential ordering problem

@Booklet{EasyChair:2647,
  author = {Luc Libralesso and Florian Fontan and Vincent Jost},
  title = {Why Branch-and-Bounds Are Meta-Heuristics},
  howpublished = {EasyChair Preprint no. 2647},

  year = {EasyChair, 2020}}