Optimization Online


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

Sebastian Pokutta (pokutta***at***mathematik.tu-darmstadt.de)
Andreas S. Schulz (schulz***at***mit.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society