A bounded path propagator on directed graphs

Diego de Uña, Graeme Gange, Peter Schachte, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

2 Citations (Scopus)


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 languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
Subtitle of host publication22nd International Conference, CP 2016 Toulouse, France, September 5–9, 2016 Proceedings
EditorsMichel Rueher
Place of PublicationCham Switzerland
Number of pages18
ISBN (Electronic)9783319449531
ISBN (Print)9783319449524
Publication statusPublished - 2016
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 2016 - Toulouse, France
Duration: 5 Sep 20169 Sep 2016
Conference number: 22d

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceInternational Conference on Principles and Practice of Constraint Programming 2016
Abbreviated titleCP 2016
Internet address

Cite this