Steiner Tree Problems with Side Constraints Using Constraint Programming

Authors

  • Diego de Uña The University of Melbourne
  • Graeme Gange The University of Melbourne
  • Peter Schachte The University of Melbourne
  • Peter Stuckey The University of Melbourne and National ICT Australia, Victoria Laboratory

DOI:

https://doi.org/10.1609/aaai.v30i1.10435

Keywords:

Steiner tree, constraint programming, propagation

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.

AAAI 2016 Proceedings Cover

Downloads

Published

2016-03-05

How to Cite

de Uña, D., Gange, G., Schachte, P., & Stuckey, P. (2016). Steiner Tree Problems with Side Constraints Using Constraint Programming. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10435

Issue

Vol. 30 No. 1 (2016): Thirtieth AAAI Conference on Artificial Intelligence

Section

Technical Papers: Search and Constraint Satisfaction