On the NP-hardness of deciding emptiness of the split closure of a rational polytope in the 0,1 hypercube

DOI10.1016/j.disopt.2018.10.003zbMath1506.90162OpenAlexW2899717957WikidataQ128909383 ScholiaQ128909383MaRDI QIDQ2419579

Dabeen Lee

Publication date: 14 June 2019

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2018.10.003

zbMATH Keywords

integer linear programmingcutting planesseparationNP-hardnesssplit cutssplit closure

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• On \(t\)-branch split cuts for mixed-integer programs
• MIR closures of polyhedral sets
• Optimizing over the first Chvátal closure
• Chvátal closures for mixed integer programming problems
• The ellipsoid method and its consequences in combinatorial optimization
• Disjunctive programming: Properties of the convex hull of feasible points
• On the separation of split cuts and related inequalities
• Split closure and intersection cuts
• A recursive procedure to generate all cuts for 0-1 mixed integer programs
• When the Gomory-chvátal closure coincides with the integer hull
• Optimizing over the split closure
• Edmonds polytopes and a hierarchy of combinatorial problems
• 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
• Integer Programming
• Outline of an algorithm for integer solutions to linear programs
• On Cutting Planes
• Paths, Trees, and Flowers
• Intersection Cuts—A New Type of Cutting Planes for Integer Programming
• Elementary closures for integer programs.

This page was built for publication: On the NP-hardness of deciding emptiness of the split closure of a rational polytope in the 0,1 hypercube