Lifting operators for 0-1 integer programming (Daniel Bienstock)

This research extends the work of Lovasz and Schrijver, Sherali-Adams, and Lasserre, on the idea of lifting an n-dimensional polyhedron to a space whose coordinates are indexed by members of a subset-lattice of an n-element set. 

Instead, in work to appear in the PhD dissertation of Mark Zuckerberg, we have devised operators that lift to a space whose coordinates are indexed by the much larger subset algebra of an n-element set. 

This leads to provably stronger operators. As an example of our results, we have obtained a polynomial-time algorithm that solves a relaxation of set-covering problems that is stronger than that provided by the set of all valid inequalities with coefficients 0,1,2, ..., k (for any fixed k). 

Our current research centers on extending these operators with the goal of making them computationally practicable. 

http://www.corc.ieor.columbia.edu/projects/algebra/algebra.html