A bounded path propagator on directed graphs

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

doi:10.1007/978-3-319-44953-1_13

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 proceeding › Conference Paper › Research › peer-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 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	https://doi.org/10.1007/978-3-319-44953-1_13
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	France
City	Toulouse
Period	5/09/16 → 9/09/16
Internet address	http://cp2016.a4cp.org/

Access to Document

10.1007/978-3-319-44953-1_13

Link to publication in Scopus

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

de Uña, Diego ; Gange, Graeme ; Schachte, Peter ; Stuckey, Peter J. / A bounded path propagator on directed graphs. Principles and Practice of Constraint Programming: 22nd International Conference, CP 2016 Toulouse, France, September 5–9, 2016 Proceedings. editor / Michel Rueher. Cham Switzerland : Springer, 2016. pp. 189-206 (Lecture Notes in Computer Science ).

@inproceedings{ff7ac55a990b4d85b4569394cc3a6284,

title = "A bounded path propagator on directed graphs",

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.",

author = "{de U{\~n}a}, Diego and Graeme Gange and Peter Schachte and Stuckey, {Peter J.}",

year = "2016",

doi = "10.1007/978-3-319-44953-1_13",

language = "English",

isbn = "9783319449524",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "189--206",

editor = "Michel Rueher",

booktitle = "Principles and Practice of Constraint Programming",

note = "International Conference on Principles and Practice of Constraint Programming 2016, CP 2016 ; Conference date: 05-09-2016 Through 09-09-2016",

url = "http://cp2016.a4cp.org/",

}

de Uña, D, Gange, G, Schachte, P & Stuckey, PJ 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. Lecture Notes in Computer Science , vol. 9892 , Springer, Cham Switzerland, pp. 189-206, International Conference on Principles and Practice of Constraint Programming 2016, Toulouse, France, 5/09/16. https://doi.org/10.1007/978-3-319-44953-1_13

A bounded path propagator on directed graphs. / de Uña, Diego; Gange, Graeme; Schachte, Peter; Stuckey, Peter J.

Principles and Practice of Constraint Programming: 22nd International Conference, CP 2016 Toulouse, France, September 5–9, 2016 Proceedings. ed. / Michel Rueher. Cham Switzerland : Springer, 2016. p. 189-206 (Lecture Notes in Computer Science ; Vol. 9892 ).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - A bounded path propagator on directed graphs

AU - de Uña, Diego

AU - Gange, Graeme

AU - Schachte, Peter

AU - Stuckey, Peter J.

N1 - Conference code: 22d

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84986237998&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-44953-1_13

DO - 10.1007/978-3-319-44953-1_13

M3 - Conference Paper

AN - SCOPUS:84986237998

SN - 9783319449524

T3 - Lecture Notes in Computer Science

SP - 189

EP - 206

BT - Principles and Practice of Constraint Programming

A2 - Rueher, Michel

PB - Springer

CY - Cham Switzerland

T2 - International Conference on Principles and Practice of Constraint Programming 2016

Y2 - 5 September 2016 through 9 September 2016

ER -

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