
arXiv: 1601.00198
In this paper, we present an analysis of the strength of sparse cutting planes for mixed integer linear programs (MILP) with sparse formulations. We examine three kinds of problems: packing problems, covering problems, and more general MILPs with the only assumption that the objective function is nonnegative. Given an MILP instance of one of these three types, assume that we decide on the support of cutting planes to be used and the strongest inequalities on these supports are added to the linear programming relaxation. We present bounds on the ratio of optimal value of the LP relaxation after adding cuts and the optimal value of the MILP that depends only on the sparsity structure of the constraint matrix and the support of sparse cuts selected, that is, these bounds are completely data independent. These results also shed light on the strength of single-scenario cuts for two-stage stochastic MILPs.
Mixed integer programming, Optimization and Control (math.OC), sparsity, FOS: Mathematics, Stochastic programming, mixed-integer linear programming, Mathematics - Optimization and Control, cutting planes
Mixed integer programming, Optimization and Control (math.OC), sparsity, FOS: Mathematics, Stochastic programming, mixed-integer linear programming, Mathematics - Optimization and Control, cutting planes
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 18 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
