Weighted spanning tree constraint with explanations

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

doi:10.1007/978-3-319-33954-2_8

Weighted spanning tree constraint with explanations

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

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

3 Citations (Scopus)

Abstract

Minimum Spanning Trees (MSTs) are ubiquitous in optimization problems in networks. Even though fast algorithms exist to solve the MST problem, real world applications are usually subject to constraints that do not let us apply such methods directly. In these cases we confront a version of the MST called the “Weighted Spanning Tree” (WST) in which we look for a spanning tree in a graph that satisfies other side constraints and is of minimum cost. In this paper we implement this constraint using a lower bound and learning to accelerate the search and thus reduce the solving time. We show that having this propagator is tremendously beneficial for solvers and we show the benefits of learning.

Original language	English
Title of host publication	Integration of AI and OR Techniques in Constraint Programming
Subtitle of host publication	13th International Conference, CPAIOR 2016 Banff, AB, Canada, May 29 – June 1, 2016 Proceedings
Editors	Claude-Guy Quimper
Place of Publication	Cham Switzerland
Publisher	Springer
Pages	98-107
Number of pages	10
ISBN (Electronic)	9783319339542
ISBN (Print)	9783319339535
DOIs	https://doi.org/10.1007/978-3-319-33954-2_8
Publication status	Published - 2016
Externally published	Yes
Event	International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2016 - Banff, Canada Duration: 29 May 2016 → 1 Jun 2016 Conference number: 13th https://symposia.cirrelt.ca/CPAIOR2016/en/home (Conference website) https://link.springer.com/book/10.1007/978-3-319-33954-2 (Proceedings)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	9676
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2016
Abbreviated title	CPAIOR 2016
Country/Territory	Canada
City	Banff
Period	29/05/16 → 1/06/16
Internet address	https://symposia.cirrelt.ca/CPAIOR2016/en/home (Conference website) https://link.springer.com/book/10.1007/978-3-319-33954-2 (Proceedings)

Access to Document

10.1007/978-3-319-33954-2_8

Cite this

de Uña, D., Gange, G., Schachte, P., & Stuckey, P. J. (2016). Weighted spanning tree constraint with explanations. In C-G. Quimper (Ed.), Integration of AI and OR Techniques in Constraint Programming: 13th International Conference, CPAIOR 2016 Banff, AB, Canada, May 29 – June 1, 2016 Proceedings (pp. 98-107). (Lecture Notes in Computer Science ; Vol. 9676). Springer. https://doi.org/10.1007/978-3-319-33954-2_8

de Uña, Diego ; Gange, Graeme ; Schachte, Peter et al. / Weighted spanning tree constraint with explanations. Integration of AI and OR Techniques in Constraint Programming: 13th International Conference, CPAIOR 2016 Banff, AB, Canada, May 29 – June 1, 2016 Proceedings. editor / Claude-Guy Quimper. Cham Switzerland : Springer, 2016. pp. 98-107 (Lecture Notes in Computer Science ).

@inproceedings{58612e17df6841ff887dcaabf4447556,

title = "Weighted spanning tree constraint with explanations",

abstract = "Minimum Spanning Trees (MSTs) are ubiquitous in optimization problems in networks. Even though fast algorithms exist to solve the MST problem, real world applications are usually subject to constraints that do not let us apply such methods directly. In these cases we confront a version of the MST called the “Weighted Spanning Tree” (WST) in which we look for a spanning tree in a graph that satisfies other side constraints and is of minimum cost. In this paper we implement this constraint using a lower bound and learning to accelerate the search and thus reduce the solving time. We show that having this propagator is tremendously beneficial for solvers and we show the benefits of learning.",

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

year = "2016",

doi = "10.1007/978-3-319-33954-2_8",

language = "English",

isbn = "9783319339535",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "98--107",

editor = "Claude-Guy Quimper",

booktitle = "Integration of AI and OR Techniques in Constraint Programming",

note = "International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2016, CPAIOR 2016 ; Conference date: 29-05-2016 Through 01-06-2016",

url = "https://symposia.cirrelt.ca/CPAIOR2016/en/home, https://link.springer.com/book/10.1007/978-3-319-33954-2",

}

de Uña, D, Gange, G, Schachte, P & Stuckey, PJ 2016, Weighted spanning tree constraint with explanations. in C-G Quimper (ed.), Integration of AI and OR Techniques in Constraint Programming: 13th International Conference, CPAIOR 2016 Banff, AB, Canada, May 29 – June 1, 2016 Proceedings. Lecture Notes in Computer Science , vol. 9676, Springer, Cham Switzerland, pp. 98-107, International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2016, Banff, Alberta, Canada, 29/05/16. https://doi.org/10.1007/978-3-319-33954-2_8

Weighted spanning tree constraint with explanations. / de Uña, Diego; Gange, Graeme; Schachte, Peter et al.

Integration of AI and OR Techniques in Constraint Programming: 13th International Conference, CPAIOR 2016 Banff, AB, Canada, May 29 – June 1, 2016 Proceedings. ed. / Claude-Guy Quimper. Cham Switzerland : Springer, 2016. p. 98-107 (Lecture Notes in Computer Science ; Vol. 9676).

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

TY - GEN

T1 - Weighted spanning tree constraint with explanations

AU - de Uña, Diego

AU - Gange, Graeme

AU - Schachte, Peter

AU - Stuckey, Peter J.

N1 - Conference code: 13th

PY - 2016

Y1 - 2016

N2 - Minimum Spanning Trees (MSTs) are ubiquitous in optimization problems in networks. Even though fast algorithms exist to solve the MST problem, real world applications are usually subject to constraints that do not let us apply such methods directly. In these cases we confront a version of the MST called the “Weighted Spanning Tree” (WST) in which we look for a spanning tree in a graph that satisfies other side constraints and is of minimum cost. In this paper we implement this constraint using a lower bound and learning to accelerate the search and thus reduce the solving time. We show that having this propagator is tremendously beneficial for solvers and we show the benefits of learning.

AB - Minimum Spanning Trees (MSTs) are ubiquitous in optimization problems in networks. Even though fast algorithms exist to solve the MST problem, real world applications are usually subject to constraints that do not let us apply such methods directly. In these cases we confront a version of the MST called the “Weighted Spanning Tree” (WST) in which we look for a spanning tree in a graph that satisfies other side constraints and is of minimum cost. In this paper we implement this constraint using a lower bound and learning to accelerate the search and thus reduce the solving time. We show that having this propagator is tremendously beneficial for solvers and we show the benefits of learning.

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

U2 - 10.1007/978-3-319-33954-2_8

DO - 10.1007/978-3-319-33954-2_8

M3 - Conference Paper

AN - SCOPUS:84978782666

SN - 9783319339535

T3 - Lecture Notes in Computer Science

SP - 98

EP - 107

BT - Integration of AI and OR Techniques in Constraint Programming

A2 - Quimper, Claude-Guy

PB - Springer

CY - Cham Switzerland

T2 - International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2016

Y2 - 29 May 2016 through 1 June 2016

ER -

de Uña D, Gange G, Schachte P, Stuckey PJ. Weighted spanning tree constraint with explanations. In Quimper C-G, editor, Integration of AI and OR Techniques in Constraint Programming: 13th International Conference, CPAIOR 2016 Banff, AB, Canada, May 29 – June 1, 2016 Proceedings. Cham Switzerland: Springer. 2016. p. 98-107. (Lecture Notes in Computer Science ). https://doi.org/10.1007/978-3-319-33954-2_8

Weighted spanning tree constraint with explanations

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this