Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs
From MaRDI portal
Publication:5219296
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.
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
- A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems
- A fractional analogue of Brooks' theorem
- A recursive bipartitioning algorithm for permuting sparse square matrices into block diagonal form with overlap
- Approximating polyhedra with sparse inequalities
- Computational experience with hypergraph-based methods for automatic decomposition in discrete optimization
- Cutting planes in integer and mixed integer programming
- Decomposing Matrices into Blocks
- Dual decomposition in stochastic integer programming
- Finitely convergent decomposition algorithms for two-stage stochastic pure integer programs
- Graph colouring and the probabilistic method
- Incidence matrices and interval graphs
- Mixed integer programming computation
- On the practical strength of two-row tableau cuts
- On the ratio of optimal integral and fractional covers
- Partial convexification of general mips by Dantzig-Wolfe reformulation
- Solving Large-Scale Zero-One Linear Programming Problems
- Sparsity of lift-and-project cutting planes
- Strengthened benders cuts for stochastic integer programs with continuous recourse
- The \(C^3\) theorem and a \(D^2\) algorithm for large scale stochastic mixed-integer programming: set convexification
- The group-theoretic approach in mixed integer programming
- Two-stage stochastic matching and spanning tree problems: polynomial instances and approximation
Cited in
(18)- Average-case complexity of a branch-and-bound algorithm for \textsc{Min Dominating Set}
- Sparse PSD approximation of the PSD cone
- Strong IP formulations need large coefficients
- Branch-and-bound solves random binary IPs in poly\((n)\)-time
- 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
- Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
- Decomposition Branching for Mixed Integer Programming
- Improving the randomization step in feasibility pump
- 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)
