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 $\underset{x\in L}{max}{\pi }^{T}x-\underset{x\in L}{min}{\pi }^{T}x\le w$ for all facets ${\pi }^{T}x\le {\pi }_0$ of L, and $\underset{x\in L}{max}{\pi }^{T}x-\underset{x\in L}{min}{\pi }^{T}x=w$ for some facet ${\pi }^{T}x\le {\pi }_0$ 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.