Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs
From MaRDI portal
Publication:5219296
DOI10.1287/MOOR.2017.0866zbMATH Open1432.90090arXiv1601.00198OpenAlexW2963926915MaRDI QIDQ5219296FDOQ5219296
Authors: Marco Molinaro, Qianyi Wang, Santanu S. Dey 
Publication date: 11 March 2020
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Abstract: 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 non-negative. Given a 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. Call the optimal objective function value of the linear programming relaxation together with these cuts as . We present bounds on the ratio of and the optimal objective function 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 scenario-specific cuts for two stage stochastic MILPs.
Full work available at URL: https://arxiv.org/abs/1601.00198
Recommendations
- A cutting plane method from analytic centers for stochastic programming
- Cutting planes for multistage stochastic integer programs
- Cutting plane method for multiple objective stochastic integer linear programming
- A cutting-plane approach to mixed 0-1 stochastic integer programs
- Stochastic dynamic cutting plane for multistage stochastic convex programs
- A Cutting Plane Approach for Chance Constrained Linear Programs
- Generalized cutting plane method for solving nonlinear stochastic programming problems
- A mixed integer model for the sparsest cut problem
- Convergent cutting-plane and partial-sampling algorithm for multistage stochastic linear programs with recourse
Cites Work
- On the ratio of optimal integral and fractional covers
- Dual decomposition in stochastic integer programming
- Incidence matrices and interval graphs
- Partial convexification of general mips by Dantzig-Wolfe reformulation
- Mixed integer programming computation
- The group-theoretic approach in mixed integer programming
- Solving Large-Scale Zero-One Linear Programming Problems
- Decomposing Matrices into Blocks
- Graph colouring and the probabilistic method
- The \(C^3\) theorem and a \(D^2\) algorithm for large scale stochastic mixed-integer programming: set convexification
- Cutting planes in integer and mixed integer programming
- A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems
- A fractional analogue of Brooks' theorem
- On the practical strength of two-row tableau cuts
- Finitely convergent decomposition algorithms for two-stage stochastic pure integer programs
- Strengthened benders cuts for stochastic integer programs with continuous recourse
- Two-stage stochastic matching and spanning tree problems: polynomial instances and approximation
- A recursive bipartitioning algorithm for permuting sparse square matrices into block diagonal form with overlap
- Approximating polyhedra with sparse inequalities
- Sparsity of lift-and-project cutting planes
- Computational experience with hypergraph-based methods for automatic decomposition in discrete optimization
Cited In (18)
- Average-case complexity of a branch-and-bound algorithm for \textsc{Min Dominating Set}
- Sparse PSD approximation of the PSD cone
- Branch-and-bound solves random binary IPs in poly\((n)\)-time
- Strong IP formulations need large coefficients
- Sparsity of integer formulations for binary programs
- Sparsity of lift-and-project cutting planes
- Sparse multi-term disjunctive cuts for the epigraph of a function of binary variables
- How good are sparse cutting-planes?
- New SOCP relaxation and branching rule for bipartite bilinear programs
- Sparse multi-term disjunctive cuts for the epigraph of a function of binary variables
- Split cuts from sparse disjunctions
- Decomposition Branching for Mixed Integer Programming
- Improving the randomization step in feasibility pump
- Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
- Distributed stochastic optimization with large delays
- Some lower bounds on sparse outer approximations of polytopes
- Optimization-Driven Scenario Grouping
- Easy and hard separation of sparse and dense odd-set constraints in matching
This page was built for publication: Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5219296)
