HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
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

42

Files downloads

33