Pourquoi Les Branch-and-Bounds Sont Des Meta-Heuristiques

EasyChair Preprint 2647

Abstract

Nous présentons une famille de branch-and-bound dits "anytime" que l'on retrouve principalement en IA/planning. L'un de ces membres connu en RO est la Beam Search. Ceux-ci ont la propriété de trouver rapidement de bonnes solutions et tentent de les améliorer par la suite. Cette approche est similaire aux meta-heuristiques classiques, mais les branch-and-bounds anytime sont en fait plus performants dans certains cas. Nous présentons ici deux de ces cas : des problèmes de cutting & packing et un TSP asymétrique avec contraintes de précédence.

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}}