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

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. (C) 2018 Elsevier B.V. All rights reserved.