- Series
- ACO Seminar
- Time
- Wednesday, February 5, 2014 - 12:00pm for 1 hour (actually 50 minutes)
- Location
- IC 209
- Speaker
- Marco Molinaro – Georgia Tech – http://www.isye.gatech.edu/faculty-staff/profile.php?entry=mmolinaro3
- Organizer
- Emma Cohen
Please Note: Joint DOS-ACO Seminar. Food and refreshments will be provided.
Sparse cutting-planes are often the ones used in mixed-integer programing
(MIP) solvers, since they help in solving the linear programs encountered
during branch-&-bound more efficiently. However, how well can we
approximate the integer hull by just using sparse cutting-planes? In order
to understand this question better, given a polyope P (e.g. the integer
hull of a MIP), let P^k be its best approximation using cuts with at most k
non-zero coefficients. We consider d(P, P^k) = max_{x in P^k} (min_{y in
P} |x - y|) as a measure of the quality of sparse cuts.
In our first result, we present general upper bounds on d(P, P^k) which
depend on the number of vertices in the polytope and exhibits three phases
as k increases. Our bounds imply that if P has polynomially many vertices,
using half sparsity already approximates it very well. Second, we present a
lower bound on d(P, P^k) for random polytopes that show that the upper
bounds are quite tight. Third, we show that for a class of hard packing
IPs, sparse cutting-planes do not approximate the integer hull well.
Finally, we show that using sparse cutting-planes in extended formulations
is at least as good as using them in the original polyhedron, and give an
example where the former is actually much better.
Joint work with Santanu Dey and Qianyi Wang.