Steiner tree problems with side constraints using constraint programming

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

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

5 Citations (Scopus)

Abstract

The Steiner Tree Problem is a well know NP-complete problem that is well studied and for which fast algorithms are already available. Nonetheless, in the real world the Steiner Tree Problem is almost always accompanied by side constraints which means these approaches cannot be applied. For many problems with side constraints, only approximation algorithms are known. We introduce here a propagator for the tree constraint with explanations, as well as lower bounding techniques and a novel constraint programming approach for the Steiner Tree Problem and two of its variants. We find our propagators with explanations are highly advantageous when it comes to solving variants of this problem.

Original languageEnglish
Title of host publicationProceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI'16 )
Subtitle of host publicationFebruary 12–17, 2016 Phoenix, Arizona, USA
EditorsDale Schuurmans, Michael Wellman
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages3383-3389
Number of pages7
ISBN (Electronic)9781577357605
Publication statusPublished - 2016
Externally publishedYes
EventAAAI Conference on Artificial Intelligence 2016 - Phoenix Convention Center, Phoenix, United States of America
Duration: 12 Feb 201617 Feb 2016
Conference number: 30th
http://www.aaai.org/Conferences/AAAI/aaai16.php

Conference

ConferenceAAAI Conference on Artificial Intelligence 2016
Abbreviated titleAAAI 2016
CountryUnited States of America
CityPhoenix
Period12/02/1617/02/16
Internet address

Cite this