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

DOI10.1007/978-3-319-33461-5_32zbMath1419.90068OpenAlexW2481713999MaRDI QIDQ3186518

Yanjun Li, Cornuéjols, Gérard

Publication date: 10 August 2016

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-33461-5_32

zbMATH Keywords

computational complexityinteger programminginteger hullGomory-Chvátal closureGomory-Chvátal cuts

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items

On Some Polytopes Contained in the 0,1 Hypercube that Have a Small Chvátal Rank, When the Gomory-chvátal closure coincides with the integer hull, On the NP-hardness of deciding emptiness of the split closure of a rational polytope in the 0,1 hypercube, On the rational polytopes with Chvátal rank 1, On some polytopes contained in the 0,1 hypercube that have a small Chvátal rank

Cites Work

• Unnamed Item
• Stable sets, corner polyhedra and the Chvàtal closure
• Matrices with the Edmonds-Johnson property
• On the membership problem for the elementary closure of a polyhedron
• The ellipsoid method and its consequences in combinatorial optimization
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Edmonds polytopes and a hierarchy of combinatorial problems
• Integer Programming with a Fixed Number of Variables
• On the Complexity of Selecting Disjunctions in Integer Programming
• Integer Programming
• Outline of an algorithm for integer solutions to linear programs
• Odd Minimum Cut-Sets and b-Matchings
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• Maximum matching and a polyhedron with 0,1-vertices