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 language | English |
|---|---|
| Title of host publication | Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI'16 ) |
| Subtitle of host publication | February 12–17, 2016 Phoenix, Arizona, USA |
| Editors | Dale Schuurmans, Michael Wellman |
| Place of Publication | Palo Alto CA USA |
| Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
| Pages | 3383-3389 |
| Number of pages | 7 |
| ISBN (Electronic) | 9781577357605 |
| Publication status | Published - 2016 |
| Externally published | Yes |
| Event | AAAI Conference on Artificial Intelligence 2016 - Phoenix Convention Center, Phoenix, United States of America Duration: 12 Feb 2016 → 17 Feb 2016 Conference number: 30th http://www.aaai.org/Conferences/AAAI/aaai16.php |
Conference
| Conference | AAAI Conference on Artificial Intelligence 2016 |
|---|---|
| Abbreviated title | AAAI 2016 |
| Country/Territory | United States of America |
| City | Phoenix |
| Period | 12/02/16 → 17/02/16 |
| Internet address |