An Analysis of Mixed Integer Linear Sets Based on Lattice Point Free Convex Sets

A maximal lattice free polyhedron L has max-facet-width equal to w if for all facets of L, and for some facet of L. The set obtained by adding all cuts whose validity follows from a maximal lattice free polyhedron with max-facet-width at most w is called the wth split closure. We show the wth split closure is a polyhedron. This generalizes a previous result showing this to be true when w = 1. We also consider the design of finite cutting plane proofs for the validity of an inequality. Given a measure of “size” of a maximal lattice free polyhedron, a natural question is how large a size s^* of a maximal lattice free polyhedron is required to design a finite cutting plane proof for the validity of an inequality. We characterize s^* based on the faces of the linear relaxation of the mixed integer linear set.