Steiner Tree Problems with Side Constraints Using Constraint Programming
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.
Cite
Text
de Uña et al. "Steiner Tree Problems with Side Constraints Using Constraint Programming." AAAI Conference on Artificial Intelligence, 2016. doi:10.1609/AAAI.V30I1.10435Markdown
[de Uña et al. "Steiner Tree Problems with Side Constraints Using Constraint Programming." AAAI Conference on Artificial Intelligence, 2016.](https://mlanthology.org/aaai/2016/deuna2016aaai-steiner/) doi:10.1609/AAAI.V30I1.10435BibTeX
@inproceedings{deuna2016aaai-steiner,
title = {{Steiner Tree Problems with Side Constraints Using Constraint Programming}},
author = {de Uña, Diego and Gange, Graeme and Schachte, Peter and Stuckey, Peter J.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2016},
pages = {3383-3389},
doi = {10.1609/AAAI.V30I1.10435},
url = {https://mlanthology.org/aaai/2016/deuna2016aaai-steiner/}
}