Valid inequalities and lifting procedures for the shortest path problem in digraphs with negative cycles

详细信息    查看全文

• 作者：M. S. Ibrahim (1)
  N. Maculan (2)
  M. Minoux (3)
  
  1. Facult茅 des Sciences ; Universit茅 A. Moumouni ; BP聽10.622聽 ; Niamey ; Niger
  2. Federal University of Rio de Janeiro ; Rio de Janeiro ; Brazil
  3. Universit茅 Pierre et Marie Curie ; Paris ; France
  
• 关键词：Polytope ; Digraphs ; Shortest path ; Valid inequality ; Lifting
• 刊名：Optimization Letters
• 出版年：2015
• 出版时间：February 2015
• 年：2015
• 卷：9
• 期：2
• 页码：345-357
• 全文大小：191 KB
• 参考文献：1. Bellman, R.: On routing problem. Q. Appl. Math. 16, 87鈥?0 (1958)
  2. Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1, 269鈥?71 (1959) 86390" target="_blank" title="It opens in new window">CrossRef
  3. Ford, L.R., Jr.: Networks flow theory. Paper P-923, The RAND Corporation, Santa Monica, California, [August 14] (1956)
  4. Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci. 10, 111鈥?21 (1980) 80)90009-2" target="_blank" title="It opens in new window">CrossRef
  5. Garey, M., Johnson, D.: Computer and Intractibility: a guide to the theory of NP-completeness. Freeman, San Francisco (1979)
  6. Gondran, M., Minoux, M.: Graphes et Algorithmes. Eyrolles, Paris (1995)
  7. Hansen, P.: Bicreterion path problems. Multiple criteria decision making: theory and applications, LNEMS 177, pp. 109鈥?27, Springer-verlag, Berlin
  8. Ibrahim, M.S.: Etude de formulations et in茅galit茅s valides pour le probl猫me du plus court chemin dans les graphes avec des circuits absorbants. PhD dissertation, Universit茅 Pierre et Marie Curie, Paris 6 (2007)
  9. Ibrahim, M.S., Maculan, N., Minoux, M.: Strong flow-based formulation for the shortest path problem in digraphs with negative cycles. ITOR 16, 361鈥?69 (2009)
  10. Di Puglia Pugliese, L., Guerriero, F.: On the shortest path problem with negative cost cycles. Technical Report n 5/10, 2010, LOGICA Laboratory, University of Calabria, Italy (2010)
  11. Klein, P.N., Mozes, S., Weimann, O.: Shortest paths in directed planar graphs with negative lengths: A linear space \(O(nlog^2 n)\) -time algorithm. ACM Trans. Algorithms (TALG) 6, 361鈥?69 (2010)
  12. Lipton, R., Rose, D.J., Tarjan, R.E.: Generalized nested dissection. SIAM J. Numer. Anal. 16, 346鈥?58 (1979) et="_blank" title="It opens in new window">CrossRef
  13. Lipton, R., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177鈥?89 (1979) et="_blank" title="It opens in new window">CrossRef
  14. Maculan, N., Plateau, G., Lisser, A.: Integer linear models with a polynomial number of variables and constraints for some classical combinatorial optimization problems. Pesquisa Oper. 23, 161鈥?68 (2003) 82003000100012" target="_blank" title="It opens in new window">CrossRef
  15. Mehlhorn, K., Priebe, V., Schafer, G., Sivadasan, N.: All-pairs shortest paths computation in the presence of negative cycles. Inf. Process. Lett. 81, 341鈥?43 (2002) et="_blank" title="It opens in new window">CrossRef
  16. Miller, G.L.: Finding small simple cycle separators for 2-connected planar graphs. J. Comput. System Sci. 32(3), 265鈥?79 (1986) 86)90030-9" target="_blank" title="It opens in new window">CrossRef
  17. Minoux, M.: Programmation math茅matique. 8"> \(2^e\) 茅dition Lavoisier (2008)
  18. Subramani, K.: A zero-space algorithm for negative cost cycle detection in networks. J. Discret. Algorithms 5, 408鈥?21 (2007) et="_blank" title="It opens in new window">CrossRef
  19. Subramani, K., Kovalchick, L.: A greedy strategy for detecting negative cost cycles in networks. Future Gener. Comput. Systems 21(4), 607鈥?23 (2005) et="_blank" title="It opens in new window">CrossRef
  20. Yamada, T., Kinoshita, H.: Finding all the negative cycles in a directedgraph. Discret. Appl. Math. 118, 279鈥?91 (2002) 8X(01)00201-3" target="_blank" title="It opens in new window">CrossRef
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Optimization
  Operation Research and Decision Theory
  Numerical and Computational Methods in Engineering
  Numerical and Computational Methods
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1862-4480

文摘

In this paper, we discuss exact algorithm for the shortest elementary path problem in digraphs containing negative directed cycles. We investigate various classes of valid inequalities for the polytope of \(s-t\) elementary paths in digraphs. The problem of separation of these valid inequalities can be shown to be NP-hard, thus only solvable for small sized problems. To deal with larger problems, lifting techniques are proposed. We provide results of computational experiments to show the efficiency of lifted inequalities in reducing the integrality gap. Indeed, considering a series of difficult test examples, the integrality gap is shown to be \(100\,\%\) closed in about half of the cases within no more than ten rounds of cutting plane generation.