Subset Algebra Lift Operators for 0-1 Integer Programming
Authors:
- Daniel BienstockDBDaniel Bienstock
- Mark ZuckerbergMZMark Zuckerberg
- 1 January 2004
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 15 (1) , 63-95
Abstract
We extend the Sherali--Adams, Lovász--Schrijver, Balas--Ceria--Cornuéjols, and Lasserre lift-and-project methods for 0-1 optimization by considering liftings to subset algebras. Our methods yield polynomial-time algorithms for solving a relaxation of a set-covering problem at least as strong as that given by the set of all valid inequalities with small coefficients and, more generally, all valid inequalities where the right-hand side is not very large relative to the positive coefficients in the left-hand side. Applied to generalizations of vertex-packing problems, our methods yield, in polynomial time, relaxations that have unbounded rank using, for example, the N + operator.Keywords
This publication has 23 references indexed in Scilit:
- Pseudo-Boolean optimizationDiscrete Applied Mathematics, 2002
- On the Matrix-Cut Rank of PolyhedraMathematics of Operations Research, 2001
- Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut FrameworkManagement Science, 1996
- Reducing Matching to Polynomial Size Linear ProgrammingSIAM Journal on Optimization, 1993
- A lift-and-project cutting plane algorithm for mixed 0–1 programsMathematical Programming, 1993
- The perfectly Matchable Subgraph Polytope of an arbitrary graphCombinatorica, 1989
- On the set covering polytope: II. Lifting the facets with coefficients in {0, 1, 2}Mathematical Programming, 1989
- On cutting-plane proofs in combinatorial optimizationLinear Algebra and its Applications, 1989
- Disjunctive Programming1979
- Advanced Combinatorics1974