Abstract
Path finding is an ubiquitous problem in optimization and graphs in general, for which fast algorithms exist. Yet, in many cases side constraints make these well known algorithms inapplicable. In this paper we study constraints to find shortest paths on a weighted directed graph with arbitrary side constraints. We use the conjunction of two directed tree constraints to model the path, and a bounded path propagator to take into account the weights of the arcs. We show how to implement these constraints with explanations so that we can make use of powerful constraint programming solving techniques using learning. We give experiments to show how the resulting propagators substantially accelerate the solving of complex path problems on directed graphs.
Original language | English |
---|---|
Title of host publication | Principles and Practice of Constraint Programming |
Subtitle of host publication | 22nd International Conference, CP 2016 Toulouse, France, September 5–9, 2016 Proceedings |
Editors | Michel Rueher |
Place of Publication | Cham Switzerland |
Publisher | Springer |
Pages | 189-206 |
Number of pages | 18 |
ISBN (Electronic) | 9783319449531 |
ISBN (Print) | 9783319449524 |
DOIs | |
Publication status | Published - 2016 |
Externally published | Yes |
Event | International Conference on Principles and Practice of Constraint Programming 2016 - Toulouse, France Duration: 5 Sep 2016 → 9 Sep 2016 Conference number: 22d http://cp2016.a4cp.org/ |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 9892 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | International Conference on Principles and Practice of Constraint Programming 2016 |
---|---|
Abbreviated title | CP 2016 |
Country/Territory | France |
City | Toulouse |
Period | 5/09/16 → 9/09/16 |
Internet address |