The weighted arborescence constraint
(2017) International conference on integration of artificial intelligence and operations research techniques in constraint program — Location: Padova, Italy (5.June.2017)
Files
document.pdf
Open Access - Adobe PDF
- 513.61 KB
Details
- Authors
- Abstract
- For a directed graph, a Minimum Weight Arborescence (MWA) rooted at a vertex r is a directed spanning tree rooted at r with the minimum total weight. We define the MinArborescence constraint to solve constrained arborescence problems (CAP) in Constraint Programming (CP). A filtering based on the LP reduced costs requires O(|V |2) where |V | is the number of vertices. We propose a procedure to strengthen the quality of the LP reduced costs in some cases, also running in O(|V |2). Computational results on a variant of CAP show that the additional filtering provided by the constraint reduces the size of the search tree substantially.
- Affiliations
Citations
Houndji, V. R., Schaus, P., Hounkonnou, M. N., & Wolsey, L. (2017). The weighted arborescence constraint. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformat, 10335 LNCS, 185-201. https://doi.org/10.1007/978-3-319-59776-8_15 (Original work published 2017)