Skip to Main content Skip to Navigation
Conference papers

Au sujet de certaines contraintes globales

Résumé : Alors que les algorithmes de recherche opérationnelle permettant de résoudre certains problèmes classiques tel le chemin, l'arbre ou le couplage de coût minimal sont connus depuis plusieurs décennies, les contraintes globales correspondantes sont relativement récentes. Ainsi Sellmann n'a-t-il montré comment réaliser une contrainte globale de plus court chemin qu'en 2003 tandis que le couplage a été résolu en 1999 par Régin après des tentatives de Focacci et al. (au moyen des coûts réduits) ou Laburthe et Caseau (au moyen de l'algorithme hongrois). Quant à l'arbre couvrant, il n'apparaît que marginalement dans un travail de Aron et Van Hentenryck en 2002. Toutes ces contraintes globales peuvent être dérivées d'algorithmes d'énumération en ordre des coûts croissants dus à Eppstein, urty ou Gabow. Le propos de cet article est de monter le lien entre ces algorithmes classiques de recherche opérationnelle et les contraintes globales correspondantes.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/inria-00000085
Contributor : Christine Solnon <>
Submitted on : Friday, May 27, 2005 - 2:28:06 PM
Last modification on : Wednesday, December 9, 2020 - 3:08:16 PM
Long-term archiving on: : Thursday, April 1, 2010 - 9:34:22 PM

Files

Identifiers

  • HAL Id : inria-00000085, version 1

Collections

Citation

Diego Olivier Fernandez Pons. Au sujet de certaines contraintes globales. Premières Journées Francophones de Programmation par Contraintes, CRIL - CNRS FRE 2499, Jun 2005, Lens, pp.239-248. ⟨inria-00000085⟩

Share

Metrics

Record views

127

Files downloads

105