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

Des explications pour reconnaître et exploiter les structures cachées

Hadrien Cambazard 1 Narendra Jussien 2
2 TASC - Theory, Algorithms and Systems for Constraints
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
Résumé : L'identification de structures propres à un problème est souvent une étape clef pour la conception d'heuristiques de recherche comme la compréhension de la complexité du problème. De nombreuses approches en Recherche Opérationnelle emploient des stratégies de relaxations ou décompositions dès lors que certaines structures idoines ont été identifiées. L'étape suivante est la conception d'algorithmes de résolution qui puisse intégrer à la volée, pendant la résolution, ce type d'information. Cet article propose d'utiliser un solveur de contraintes à base d'explications pour collecter de l'information pertinente sur les structures dynamiques et statiques inhérentes au problème. Par ailleurs, la reconnaissance de relations spécifiques entre les variables suggère l'adaptation d'algorithmes dédiés issus du monde de la Recherche Opérationnelle au contexte de la programmation par contraintes. Une telle adaptation est discutée dans le cadre de la décomposition de Benders.
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/inria-00000064
Contributor : Christine Solnon Connect in order to contact the contributor
Submitted on : Thursday, May 26, 2005 - 9:55:40 AM
Last modification on : Wednesday, April 27, 2022 - 4:21:25 AM
Long-term archiving on: : Thursday, April 1, 2010 - 9:32:50 PM

File

Identifiers

  • HAL Id : inria-00000064, version 1

Citation

Hadrien Cambazard, Narendra Jussien. Des explications pour reconnaître et exploiter les structures cachées. Premières Journées Francophones de Programmation par Contraintes, CRIL - CNRS FRE 2499, Jun 2005, Lens, pp.403-412. ⟨inria-00000064⟩

Share

Metrics

Record views

145

Files downloads

132