How Good Are Sparse Cutting-Planes?
Lists
Only you see this
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...