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 metadatas

Cited literature [8 references]  Display  Hide  Download
Contributor : Arnaud Malapert <>
Submitted on : Thursday, April 11, 2013 - 3:17:51 PM
Last modification on : Wednesday, October 14, 2020 - 4:23:35 AM
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⟩



Record views


Files downloads