User menu

Exact methods for solving the elementary shortest and longest path problems

Bibliographic reference Bui, Quoc Trung ; Deville, Yves ; Pham, Quang Dung. Exact methods for solving the elementary shortest and longest path problems. In: Annals of Operations Research, Vol. 238, no.1, p. 1-36 (2016)
Permanent URL
  1. Achterberg Tobias, Berthold Timo, Hybrid Branching, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (2009) ISBN:9783642019289 p.309-311, 10.1007/978-3-642-01929-6_23
  2. Achterberg Tobias, Koch Thorsten, Martin Alexander, Branching rules revisited, 10.1016/j.orl.2004.04.002
  3. Aráoz, J., Fernández, E., & Meza, O. (2007) A simple exact separation algorithm for 2-matching inequalities. Research Report DR-2007/13, EIO Departement, Technical University of Catalonia (Spain). .
  4. Ascheuer Norbert, Jünger Michael, Reinelt Gerhard, 10.1023/a:1008779125567
  5. Balas Egon, Ceria Sebastián, Cornuéjols Gérard, Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework, 10.1287/mnsc.42.9.1229
  6. Balas Egon, Fischetti Matteo, A lifting procedure for the asymmetric traveling salesman polytope and a large new class of facets, 10.1007/bf01581274
  7. Baldacci Roberto, Mingozzi Aristide, Roberti Roberto, Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints, 10.1016/j.ejor.2011.07.037
  8. Beasley J. E., Christofides N., An algorithm for the resource constrained shortest path problem, 10.1002/net.3230190402
  9. Belotti Pietro, Kirches Christian, Leyffer Sven, Linderoth Jeff, Luedtke James, Mahajan Ashutosh, Mixed-integer nonlinear optimization, 10.1017/s0962492913000032
  10. Bienstock Daniel, Goemans Michel X., Simchi-Levi David, Williamson David, A note on the prize collecting traveling salesman problem, 10.1007/bf01581256
  11. Boland Natashia, Dethridge John, Dumitrescu Irina, Accelerated label setting algorithms for the elementary resource constrained shortest path problem, 10.1016/j.orl.2004.11.011
  12. Comet Tutorial. Dynamic Decision Technologies, Inc, 2010.
  13. Cormen, T. H., et al. (2009). Introduction to algorithms, third edition (3rd ed.). Cambridge: The MIT Press.
  14. Costa, A. M., Cordeau, J. F., & Laporte, G. (2006). Steiner tree problems with profits. INFOR: Information Systems and Operational Research, 44, 99–116.
  15. Dell’Amico, M., Maffioli, F., & Värbrand, P. (1995). On prize-collecting tours and the asymmetric travelling salesman problem. International Transactions in Operational Research, 38, 1073–1079.
  16. Drexl Michael, Irnich Stefan, Solving elementary shortest-path problems as mixed-integer programs, 10.1007/s00291-012-0302-7
  17. Dror Moshe, Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW, 10.1287/opre.42.5.977
  18. Edmonds Jack, Maximum matching and a polyhedron with 0,1-vertices, 10.6028/jres.069b.013
  19. Feillet Dominique, Dejax Pierre, Gendreau Michel, Traveling Salesman Problems with Profits, 10.1287/trsc.1030.0079
  20. Feillet Dominique, Dejax Pierre, Gendreau Michel, Gueguen Cyrille, An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems, 10.1002/net.20033
  21. Fischetti Matteo, Facets of the Asymmetric Traveling Salesman Polytope, 10.1287/moor.16.1.42
  22. Fischetti, M., Lodi, A., & Toth, P. (2004). Exact methods for the asymmetric traveling salesman problem. In G. Gutin & A. P. Punnen (Eds.), The traveling salesman problem and its variations (pp. 169–205). US: Springer.
  23. Goemans, M. X., & Williamson, D. P. (1992). A general approximation technique for constrained forest problems. In Proceedings of the third annual ACM-SIAM symposium on discrete algorithms (pp. 307–316).
  24. Gondran, M., & Minoux, M. (1995). Graphes et algorithmes, 3e édition revue et augmentée. Paris: Eyrolles.
  25. Grötschel, M., & Padberg, M. (1985). Polyhedral theory. In E. L. Lawler, J. K. Lenstra & A. H. G. Rinnooy Kan (Eds.), The traveling salesman problem: A guided tour of combinatorial optimization (pp. 251–305). Wiley.
  26. Ibrahim M.S., Maculan N., Minoux M., A strong flow-based formulation for the shortest path problem in digraphs with negative cycles, 10.1111/j.1475-3995.2008.00681.x
  27. Irnich Stefan, Desaulniers Guy, Shortest Path Problems with Resource Constraints, Column Generation ISBN:0387254854 p.33-65, 10.1007/0-387-25486-2_2
  28. Jepsen, M. K., Petersen, B., & Spoorendonk, S. (2008). A branch-and-cut algorithm for the elementary shortest path problem with a capacity constraint. Technical Report, Department of Computer Science, University of Copenhagen.
  29. Karger D., Motwani R., Ramkumar G. D. S., On approximating the longest path in a graph, 10.1007/bf02523689
  30. Koch T., Martin A., Solving Steiner tree problems in graphs to optimality, 10.1002/(sici)1097-0037(199810)32:3<207::aid-net5>;2-o
  31. Kulkarni R.V., Bhave P.R., Integer programming formulations of vehicle routing problems, 10.1016/0377-2217(85)90284-x
  32. Little John D. C., Murty Katta G., Sweeney Dura W., Karel Caroline, An Algorithm for the Traveling Salesman Problem, 10.1287/opre.11.6.972
  33. Ljubić Ivana, Weiskircher René, Pferschy Ulrich, Klau Gunnar W., Mutzel Petra, Fischetti Matteo, An Algorithmic Framework for the Exact Solution of the Prize-Collecting Steiner Tree Problem, 10.1007/s10107-005-0660-x
  34. Lucena A., Beasley J. E., A branch and cut algorithm for the Steiner problem in graphs, 10.1002/(sici)1097-0037(199801)31:1<39::aid-net5>;2-l
  35. Miller C. E., Tucker A. W., Zemlin R. A., Integer Programming Formulation of Traveling Salesman Problems, 10.1145/321043.321046
  36. Nguyen Viet Hung, Nguyen Thi Thu Thuy, Approximating the asymmetric profitable tour, 10.1016/j.endm.2010.05.115
  37. Padberg M., Rinaldi G., Optimization of a 532-city symmetric traveling salesman problem by branch and cut, 10.1016/0167-6377(87)90002-2
  38. Padberg Manfred, Rinaldi Giovanni, Facet identification for the symmetric traveling salesman polytope, 10.1007/bf01580861
  39. Padberg Manfred W., Rao M. R., Odd Minimum Cut-Sets andb-Matchings, 10.1287/moor.7.1.67
  40. Padberg, M. W., & Grötschel, M. (1985). Polyhedral computation. In E. L. Lawler, J. K. Lenstra, & A. H. G. Rinnooy Kan (Eds.), The traveling salesman problem: A guided tour of combinatorial optimization (pp. 251–305). Wiley.
  41. Pham, Q. D & Deville, Y. (2012) Solving the longest simple path problem with constrains-based techniques. In Proceedings of the 9th international conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems (pp. 292–306).
  42. Portugal David, Antunes Carlos Henggeler, Rocha Rui, A study of genetic algorithms for approximating the longest path in generic graphs, 10.1109/icsmc.2010.5641920
  43. Portugal David, Rocha Rui, MSP algorithm : multi-robot patrolling based on territory allocation using balanced graph partitioning, 10.1145/1774088.1774360
  44. Punnen, A. P. (2004) The traveling salesman problem: Applications, formulations and variations. In G. Gutin, & A. P. Punnen (Eds.), The Traveling salesman problem and its variations (pp. 1–28).
  45. Radulescu, A., López-Ibáñez, M., & Stützle, T. (2012). Automatically improving the anytime behaviour of multiobjective evolutionary algorithms. Technical Report TR/IRIDIA/2012-019, IRIDIA, Université Libre de Bruxelles, Belgium.
  46. Righini Giovanni, Salani Matteo, Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints, 10.1016/j.disopt.2006.05.007
  47. Righini Giovanni, Salani Matteo, New dynamic programming algorithms for the resource constrained elementary shortest path problem, 10.1002/net.20212
  48. Schmidt Klaus, Schmidt Ece G., A longest-path problem for evaluating the worst-case packet delay of switched ethernet, 10.1109/sies.2010.5551398
  49. Tarjan Robert, Depth-First Search and Linear Graph Algorithms, 10.1137/0201010
  50. Toth, P., & Vigo, D. (Eds.). (2002). The vehicle routing problem. SIAM monographs on discrete mathematics and applications. Philadelphia: SIAM.
  51. Tseng, I. L., Chen, H. W. & Lee, C. I. (2010) Obstacle-aware longest-path routing with parallel MILP solvers. In Proceedings of the world congress on engineering and computer science (pp. 827–831).
  52. Uchoa Eduardo, Reduction tests for the prize-collecting Steiner problem, 10.1016/j.orl.2005.02.007
  53. Volgenant, T., & Jonker, R. (1987). On some generalizations of the travelling-salesman problem. Journal of the Operational Research Society, 3, 297–308.
  54. Wong, W. Y. (2005). Information retrieval in p2p networks using genetic algorithm. In Proceedings of the 14th international world wide web conference (pp. 922–923).