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

EasyChair Preprint no. 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, framework générique, Meta-heuristiques, Recherches Arborescentes, sequential ordering problem

@Booklet{EasyChair:2647,
  author = {Luc Libralesso and Florian Fontan and Vincent Jost},
  title = {Pourquoi Les Branch-and-Bounds Sont Des Meta-Heuristiques},
  howpublished = {EasyChair Preprint no. 2647},

  year = {EasyChair, 2020}}