- | ||||
|
![]()
|
On the connection of the Sherali-Adams closure and border bases
Sebastian Pokutta (pokutta 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 Modify/Update this entry | ||
Visitors | Authors | More about us | Links | |
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
![]() |