Approximating polyhedra with sparse inequalities
Approximating polyhedra with sparse inequalities
复制标题
具有稀疏不等式的近似多面体
作者：
Santanu S. Dey;M. Molinaro;Qianyi Wang
在本文中，我们研究如何以及可以近似任意多面体使用稀疏不等式。我们的动机来自于稀疏切割平面在混合整数规划（MIP）求解器中的使用，因为它们有助于更有效地解决分支-&-绑定过程中遇到的线性规划。然而，仅仅使用稀疏切割平面，我们能很好地近似整船体吗？为了更好地理解这个问题，给定一个多面体P（例如MIP的整数船体），让P^k Pk是它的最佳近似，使用最多k个非零系数的切割。我们考虑$${ ext {d}}（P，P^k）= max _{x in P^k} left（min _{y in P} Vert x-yVert
八）$$d（P，Pk）=maxx∈Pkminy∈P作为稀疏割质量的度量。在我们的第一个结果中，我们给出了$${ ext {d}}（P，P^k）$$d（P，Pk），取决于多面体中顶点的数量。我们的界限意味着，如果P$$P有多项式多个顶点，使用半稀疏已经很好地近似它。其次，我们给出了$${ ext {d}}（P，P^k）$$d（P，Pk）对于随机多面体，表明上界相当紧。第三，我们证明了对于一类硬填充IP，稀疏切割平面不能很好地逼近整数船体，即d（P，P^k）d（P，Pk）在这种情况下是大的，除非k非常接近n。最后，我们表明，使用稀疏切割平面在扩展配方中至少是一样好，使用它们在原来的多面体，并给出一个例子，前者实际上是更好。
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 $$P$$P (e.g. the integer hull of a MIP), let $$P^k$$Pk be its best approximation using cuts with at most k non-zero coefficients. We consider $${ ext {d}}(P, P^k) = max _{x in P^k} left( min _{y in P} Vert x - yVert
ight) $$d(P,Pk)=maxx∈Pkminy∈P‖x-y‖ as a measure of the quality of sparse cuts.In our first result, we present general upper bounds on $${ ext {d}}(P, P^k)$$d(P,Pk) which depend on the number of vertices in the polytope. Our bounds imply that if $$P$$P has polynomially many vertices, using half sparsity already approximates it very well. Second, we present a lower bound on $${ ext {d}}(P, P^k)$$d(P,Pk) 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 $$d(P, P^k)$$d(P,Pk) 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.