2009 UW-PIMS Colloquium - 01

  • Date: 02/20/2009
Daniel Bienstock (Columbia University)

University of Washington


Recent Results on Lifted Formulations for Integer Programs



Disjunctive programming is a classical technique
for 0-1optimization in which a set of vertices of the hypercube is approximated
by the convex hull of (carefully selected) polyhedra. Through the work of Lovasz,
Schriver, Sherali and Adams, and others, this can be tied with the idea of
'lifting' a formulation to a higher dimensional space, again by carefully
choosing additional variables.


In this talk we will first provide an overview
of this subject, and then describe a new use of this idea which leads to an
approximation algorithm to the "minimum" knapsack problem:



min \sum_j c_j x_j<br />
 s.t. \sum_j a_j x_j >= b (*)<br />
x_j = 0 or 1, for all j


We show that for each fixed error 0 < ε < 1, there is a
polynomial-time algorithm that produces a 0 - 1 vector satisfying constraint(*),
whose value is at most a factor of (1 + ε) larger than the optimum.
Furthermore, this approximation is obtained by rounding the solution to a linear
program. This is the first such algorithm. If time permits, we will show
generalizations of this result. Joint work with Ben McClosky.



Time: 14:30

Location: Mary Gates Hall 231