Weighted spanning tree constraint with explanations

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

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-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 languageEnglish
Title of host publicationIntegration of AI and OR Techniques in Constraint Programming
Subtitle of host publication13th International Conference, CPAIOR 2016 Banff, AB, Canada, May 29 – June 1, 2016 Proceedings
EditorsClaude-Guy Quimper
Place of PublicationCham Switzerland
PublisherSpringer
Pages98-107
Number of pages10
ISBN (Electronic)9783319339542
ISBN (Print)9783319339535
DOIs
Publication statusPublished - 2016
Externally publishedYes
EventInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2016 - Banff, Canada
Duration: 29 May 20161 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

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

Conference

ConferenceInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2016
Abbreviated titleCPAIOR 2016
CountryCanada
CityBanff
Period29/05/161/06/16
Internet address

Cite this