How Good Are Sparse Cutting-Planes?

Santanu S. Dey, Marco Molinaro, Qianyi Wang

Abstract

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{\bf P}^k} (\min_{y \in \bf P} \| x - y\|)\) as a measure of the quality of sparse cuts.
BibTeX
@inproceedings{dey2014how,
  author = {Santanu S. Dey and Marco Molinaro and Qianyi Wang},
  title = {{How Good Are Sparse Cutting-Planes?}},
  booktitle = {IPCO},
  year = {2014},
  doi = {10.1007/978-3-319-07557-0\_22},
}

Loading related content...

Figure