When the Gomory-chvátal closure coincides with the integer hull

DOI10.1016/j.orl.2018.01.013OpenAlexW2737142356MaRDI QIDQ2417111

Yanjun Li, Cornuéjols, Gérard

Publication date: 11 June 2019

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2018.01.013

zbMATH Keywords

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

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Related Items

On the complexity of recognizing integrality and total dual integrality of the \(\{0,1/2\}\)-closure, 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple algorithm for finding a maximum triangle-free \(2\)-matching in subcubic graphs
• Optimizing over the first Chvátal closure
• Chvátal closures for mixed integer programming problems
• 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
• On matrices with the Edmonds-Johnson property arising from bidirected graphs
• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Polyhedron of triangle-free simple 2-matchings in subcubic graphs
• Some polyhedra related to combinatorial problems
• Edmonds polytopes and a hierarchy of combinatorial problems
• The Cutting Plane Method is Polynomial for Perfect Matchings
• Facet Generating Techniques
• P, NP, and NP-Completeness
• On the Complexity of Selecting Disjunctions in Integer Programming
• Deciding Emptiness of the Gomory-Chvátal Closure is NP-Complete, Even for a Rational Polyhedron Containing No Integer Point
• Outline of an algorithm for integer solutions to linear programs
• Half-Integral Vertex Covers on Bipartite Bidirected Graphs: Total Dual Integrality and Cut-Rank
• On Cutting Planes
• Odd Minimum Cut-Sets and b-Matchings
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• On the existence of optimal solutions to integer and mixed-integer programming problems
• Matching, Euler tours and the Chinese postman
• Mixed-Integer Vertex Covers on Bipartite Graphs
• Maximum matching and a polyhedron with 0,1-vertices