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

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 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
PublisherSpringer
Pages189-206
Number of pages18
ISBN (Electronic)9783319449531
ISBN (Print)9783319449524
DOIs
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
http://cp2016.a4cp.org/

Publication series

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

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2016
Abbreviated titleCP 2016
CountryFrance
CityToulouse
Period5/09/169/09/16
Internet address

Cite this

de Uña, D., Gange, G., Schachte, P., & Stuckey, P. J. (2016). A bounded path propagator on directed graphs. In M. Rueher (Ed.), Principles and Practice of Constraint Programming: 22nd International Conference, CP 2016 Toulouse, France, September 5–9, 2016 Proceedings (pp. 189-206). (Lecture Notes in Computer Science ; Vol. 9892 ). Springer. https://doi.org/10.1007/978-3-319-44953-1_13