User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

The weighted arborescence constraint

Primary tabs

download
  • Open access
  • PDF
  • 513.61 K
Houndji, Vinasetan Ratheil [UCL] Schaus, Pierre [UCL] Hounkonnou, Mahouton Norbert [Université d’Abomey-Calavi] Wolsey, Laurence [UCL]

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.

Document type Communication à un colloque (Conference Paper) – Présentation orale sans comité de sélection
Access type Accès libre
Publication date 2017
Language Anglais
Conference "International conference on integration of artificial intelligence and operations research techniques in constraint program", Padova, Italy (du 05/06/2017 au 08/06/2017)
Journal information "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformat" - Vol. 10335 LNCS, p. 185-201 (2017)
Peer reviewed yes
issn 03029743
Publisher Springer Verlag
Publication status Publié
Affiliations UCL - SST/ICTM - Institute of Information and Communication Technologies, Electronics and Applied Mathematics
UCL - SST/ICTM/INGI - Pôle en ingénierie informatique
Links
  1. Beldiceanu Nicolas, Flener Pierre, Lorca Xavier, The tree Constraint, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (2005) ISBN:9783540261520 p.64-78, 10.1007/11493853_7
  2. Bock, F.: An algorithm to construct a minimum directed spanning tree in a directed network. Dev. Oper. Res. 1, 29–44 (1971)
  3. Chu, Y.J., Liu, T.H.: On the shortest arborescence of a directed graph. Sci. Sin. Ser. A 14, 1396–1400 (1965)
  4. Dooms Grégoire, Katriel Irit, The Minimum Spanning Tree Constraint, Principles and Practice of Constraint Programming - CP 2006 (2006) ISBN:9783540462675 p.152-166, 10.1007/11889205_13
  5. Dooms Grégoire, Katriel Irit, The “Not-Too-Heavy Spanning Tree” Constraint, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (2007) ISBN:9783540723967 p.59-70, 10.1007/978-3-540-72397-4_5
  6. Edmonds, J.: Optimum branchings. J. Res. Nat. Bur. Stand. B 71(4), 125–130 (1967)
  7. Fahle Torsten, Sellmann Meinolf, 10.1023/a:1021193019522
  8. Fischetti Matteo, Toth Paolo, An additive bounding procedure for the asymmetric travelling salesman problem, 10.1007/bf01585701
  9. Fischetti, M., Toth, P.: An efficient algorithm for min-sum arborescence problem on complete digraphs. Manage. Sci. 9(3), 1520–1536 (1993)
  10. Fischetti Matteo, Vigo Daniele, A branch-and-cut algorithm for the resource-constrained minimum-weight arborescence problem, 10.1002/(sici)1097-0037(199701)29:1<55::aid-net6>3.0.co;2-b
  11. Focacci Filippo, Lodi Andrea, Milano Michela, Vigo Daniele, Solving TSP through the Integration of OR and CP Techniques, 10.1016/s1571-0653(04)00002-2
  12. Gabow Harold N., Galil Zvi, Spencer Thomas, Tarjan Robert E., Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, 10.1007/bf02579168
  13. Graham, R.L., Hell, P.: On the history of the minimum spanning tree problem. Hist. Comput. 7, 13–25 (1985)
  14. Guignard Monique, Rosenwein Moshe B., An application of lagrangean decomposition to the resource-constrained minimum weighted arborescence problem, 10.1002/net.3230200306
  15. Houndji, V.R., Schaus, P.: Cp4cap: Constraint programming for constrained arborescence problem. https://bitbucket.org/ratheilesse/cp4cap
  16. Kleinberg, J., Tardos, E.: Minimum-cost arborescences: a multi-phase greedy algorithm. In: Algorithm Design, Tsinghua University Press (2005)
  17. Lorca, X.: Contraintes de Partitionnement de Graphe. Ph. D. thesis, Université de Nantes (2010)
  18. Fages Jean-Guillaume, Lorca Xavier, Revisiting the tree Constraint, Principles and Practice of Constraint Programming – CP 2011 (2011) ISBN:9783642237850 p.271-285, 10.1007/978-3-642-23786-7_22
  19. Mendelson Ran, Tarjan Robert E., Thorup Mikkel, Zwick Uri, Melding Priority Queues, Algorithm Theory - SWAT 2004 (2004) ISBN:9783540223399 p.223-235, 10.1007/978-3-540-27810-8_20
  20. Pesant Gilles, Gendreau Michel, Potvin Jean-Yves, Rousseau Jean-Marc, An Exact Constraint Logic Programming Algorithm for the Traveling Salesman Problem with Time Windows, 10.1287/trsc.32.1.12
  21. Régin Jean-Charles, Simpler and Incremental Consistency Checking and Arc Consistency Filtering Algorithms for the Weighted Spanning Tree Constraint, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems ISBN:9783540681540 p.233-247, 10.1007/978-3-540-68155-7_19
  22. Régin Jean-Charles, Rousseau Louis-Martin, Rueher Michel, van Hoeve Willem-Jan, The Weighted Spanning Tree Constraint Revisited, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (2010) ISBN:9783642135194 p.287-291, 10.1007/978-3-642-13520-0_31
  23. Tarjan R. E., Finding optimum branchings, 10.1002/net.3230070103
  24. OscaR Team. Oscar: Scala in or (2012). https://bitbucket.org/oscarlib/oscar
  25. Van Cauwelaert Sascha, Lombardi Michele, Schaus Pierre, Understanding the Potential of Propagators, Integration of AI and OR Techniques in Constraint Programming (2015) ISBN:9783319180076 p.427-436, 10.1007/978-3-319-18008-3_29
Bibliographic reference Houndji, Vinasetan Ratheil ; Schaus, Pierre ; Hounkonnou, Mahouton Norbert ; Wolsey, Laurence. The weighted arborescence constraint.International conference on integration of artificial intelligence and operations research techniques in constraint program (Padova, Italy, du 05/06/2017 au 08/06/2017). In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformat, Vol. 10335 LNCS, p. 185-201 (2017)
Permanent URL http://hdl.handle.net/2078.1/198034