On the connection of the Sherali-Adams closure and border bases

Sebastian Pokutta (pokuttamathematik.tu-darmstadt.de)
Andreas S. Schulz (schulzmit.edu)

Abstract: 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.

Keywords: Sherali-Adams closure, border bases, reformulation-linearization technique, cutting-plane procedures

Category 1: Integer Programming (Cutting Plane Approaches )

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Integer Programming (0-1 Programming )

Citation: Working Paper, Technische Universität Darmstadt / Massachusetts Institute of Technology, July 2009

Download: [PDF]

Entry Submitted: 08/17/2009
Entry Accepted: 08/17/2009
Entry Last Modified: 12/13/2010

Modify/Update this entry