Why Branch-and-Bounds Are Meta-Heuristics

EasyChair Preprint 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, Meta-heuristiques, Recherches Arborescentes, framework générique, 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 2647},
  year      = {EasyChair, 2020}}