Propagation de contraintes arithmétiques

Abstract : We consider the resolution by constraint programming of large problems, i.e. involving millions of constraints, which mainly imply arithmetic constraints, like shortest path problems or other related problems. We show that a simple constraint programming model is not competitive with dedicated algorithms (or dedicated constraints). This mainly comes from the propagation mechanism, i.e. the ordering along which the constraints are revised. Thus, we propose a modification of this propagation mechanism integrating the main ideas of the dedicated algorithms. We give some experiments for the shortest path problem and more general problems which confirms the robustness of our approach. Last, we give some results showing that only a few variables are considered more than once during a propagation step.
Liste complète des métadonnées

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/hal-00812011
Contributor : Arnaud Malapert <>
Submitted on : Thursday, April 11, 2013 - 3:17:51 PM
Last modification on : Monday, November 5, 2018 - 3:48:02 PM
Document(s) archivé(s) le : Friday, July 12, 2013 - 4:07:02 AM

File

malapert-regin-jfpc-12.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-00812011, version 1

Collections

Citation

Arnaud Malapert, Jean-Charles Régin. Propagation de contraintes arithmétiques. JFPC 2012, May 2012, Toulouse, France. 2012. 〈hal-00812011〉

Share

Metrics

Record views

174

Files downloads

108