Optimization Online


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

Dabeen Lee(dabeenl***at***andrew.cmu.edu)

Abstract: Split cuts are prominent general-purpose cutting planes in integer programming. The split closure of a rational polyhedron is what is obtained after intersecting the half-spaces defined by all the split cuts for the polyhedron. In this paper, we prove that deciding whether the split closure of a rational polytope is empty is NP-hard, even when the polytope is contained in the unit hypercube. As a direct corollary, we prove that optimization and separation over the split closure of a rational polytope in the unit hypercube are NP-hard, extending an earlier result of Caprara and Letchford.

Keywords: Integer programming, split closure, split cuts

Category 1: Integer Programming (Cutting Plane Approaches )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Integer Programming (0-1 Programming )

Citation: April 2018

Download: [PDF]

Entry Submitted: 08/07/2018
Entry Accepted: 08/07/2018
Entry Last Modified: 08/07/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society