The Sherali-Adams lift-and-project hierarchy is a fundamental construct in integer programming, which provides successively tighter linear programming relaxations of the integer hull of a polytope. We initiate a new approach to understanding the Sherali-Adams procedure by relating it to methods from computational algebraic geometry. Our main result is a refinement of the Sherali-Adams procedure that arises from this new connection. We present a modified version of the border basis algorithm to generate a hierarchy of linear programming relaxations that are tighter than those of Sherali and Adams, and over which one can still optimize in polynomial time (for a fixed number of rounds in the hierarchy). In contrast to the well-known Gröbner bases approach to integer programming, our procedure does not create primal solutions, but constitutes a novel approach of using computer-algebraic methods to produce dual bounds.
Citation
Working Paper, Technische Universität Darmstadt / Massachusetts Institute of Technology, July 2009
Article
View On the connection of the Sherali-Adams closure and border bases