Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download
Contributor : Arnaud Malapert Connect in order to contact the contributor
Submitted on : Thursday, April 11, 2013 - 3:17:51 PM
Last modification on : Tuesday, December 7, 2021 - 4:10:10 PM
Long-term archiving on: : Friday, July 12, 2013 - 4:07:02 AM


Publisher files allowed on an open archive


  • HAL Id : hal-00812011, version 1



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



Les métriques sont temporairement indisponibles