Approximating polyhedra with sparse inequalities

作者：Dey Santanu S; Molinaro Marco^*; Wang Qianyi

来源：Mathematical Programming, 2015, 154(1-2): 329-352.

DOI：10.1007/s10107-015-0925-y

• Integer programming
• Cutting-planes
• Sparsity

In this paper, we study how well one can approximate arbitrary polytopes using sparse inequalities. Our motivation comes from the use of sparse cutting-planes 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 (e.g. the integer hull of a MIP), let be its best approximation using cuts with at most k non-zero coefficients. We consider as a measure of the quality of sparse cuts.In our first result, we present general upper bounds on which depend on the number of vertices in the polytope. Our bounds imply that if has polynomially many vertices, using half sparsity already approximates it very well. Second, we present a lower bound on 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, that is is large for such instances unless k is very close to n. 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.

• 出版日期2015-12