Deciding Emptiness of the Gomory-Chvátal Closure is NP-Complete, Even for a Rational Polyhedron Containing No Integer Point

详细信息    查看全文

• 关键词：Integer programming ; Gomory ; Chvátal cuts ; Gomory ; Chvátal closure ; Integer hull ; Computational complexity
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9682
• 期：1
• 页码：387-397
• 全文大小：218 KB
• 参考文献：1.Borosh, I., Treybig, L.B.: Bounds on positive integral solutions to linear Diophantine equations. Proc. Am. Math. Soc. 55, 299–304 (1976)MathSciNet CrossRef MATH
  2.Campelo, M., Cornuéjols, G.: Stable sets, corner polyhedra and the Chvátal closure. Oper. Res. Lett. 37, 375–378 (2009)MathSciNet CrossRef MATH
  3.Chvátal, V.: Edmonds polytope and a hierarchy of combinatorial problems. Discrete Math. 4, 305–337 (1973)MathSciNet CrossRef MATH
  4.Conforti, M., Cornuéjols, G., Zambelli, G.: Integer Programming. Springer, Switzerland (2014)CrossRef MATH
  5.Edmonds, J.: Maximum matching and a polyhedron with 0,1-vertices. J. Res. Natl. Bur. Stan. B 69, 125–130 (1965)MathSciNet CrossRef MATH
  6.Eisenbrand, F.: On the membership problem for the elementary closure of a polyhedron. Combinatorica 19, 297–300 (1999)MathSciNet CrossRef MATH
  7.Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco (1979)MATH
  8.Gerards, A.M.H., Schrijver, A.: Matrices with the Edmonds-Johnson property. Combinatorica 6, 365–379 (1986)MathSciNet CrossRef MATH
  9.Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs. Bull. Am. Math. Soc. 64, 275–278 (1958)MathSciNet CrossRef MATH
  10.Grötschel, M., Lovász, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169–197 (1981)MathSciNet CrossRef MATH
  11.Lenstra Jr., H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538–548 (1983)MathSciNet CrossRef MATH
  12.Lueker, G.S.: Two NP-complete Problems in Non-negative Integer Programming. Report No. 178, Department of Computer Science, Princeton University, Princeton, N.J. (1975)
  13.Mahajan, A., Ralphs, T.: On the complexity of selecting disjunctions in integer programming. SIAM J. Optim. 20, 2181–2198 (2010)MathSciNet CrossRef MATH
  14.Padberg, M.W., Rao, M.R.: Odd minimum cut-sets and \(b\) -matchings. Math. Oper. Res. 7, 67–80 (1982)MathSciNet CrossRef MATH
  15.Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)MATH
  
• 作者单位：Gérard Cornuéjols (15)
  Yanjun Li (16)
  
  15. Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA, 15213, USA
  16. Krannert School of Management, Purdue University, West Lafayette, IN, 47906, USA
  
• 丛书名：Integer Programming and Combinatorial Optimization
• ISBN：978-3-319-33461-5
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9682

文摘

Gomory-Chvátal cuts are prominent in integer programming. The Gomory-Chvátal closure of a polyhedron is the intersection of all half spaces defined by its Gomory-Chvátal cuts. In this paper, we show that it is \(\mathcal {NP}\)-complete to decide whether the Gomory-Chvátal closure of a rational polyhedron is empty, even when this polyhedron contains no integer point. This implies that the problem of deciding whether the Gomory-Chvátal closure of a rational polyhedron P is identical to the integer hull of P is \(\mathcal {NP}\)-hard. Similar results are also proved for the \(\{-1,0,1\}\)-cuts and \(\{0,1\}\)-cuts, two special types of Gomory-Chvátal cuts with coefficients restricted in \(\{-1, 0, 1\}\) and \(\{0, 1\}\), respectively.