Some lower bounds on sparse outer approximations of polytopes

DOI10.1016/J.ORL.2015.03.007MaRDI QIDQ1785369zbMATH OpenOpenAlexFDO

Authors Santanu S. Dey, Andres Iroume, Marco Molinaro

Publication date 28 September 2018

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.3765

zbMATH Keywords

approximationpolytopessparse inequalities

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Abstract: Motivated by the need to better understand the properties of sparse cutting-planes used in mixed integer programming solvers, the paper [2] studied the idealized problem of how well a polytope is approximated by the use of sparse valid inequalities. As an extension to this work, we study the following less idealized questions in this paper: (1) Are there integer programs, such that sparse inequalities do not approximate the integer hull well even when added to a linear programming relaxation? (2) Are there polytopes, where the quality of approximation by sparse inequalities cannot be significantly improved by adding a budgeted number of arbitrary (possibly dense) valid inequalities? (3) Are there polytopes that are difficult to approximate under every rotation? (4) Are there polytopes that are difficult to approximate in all directions using sparse inequalities? We answer each of the above questions in the positive.

Recommendations

• Approximating polyhedra with sparse inequalities
• How good are sparse cutting-planes?
• Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs
• Approximability of Sparse Integer Programs
• Sparsity of lift-and-project cutting planes

Cites work

• How good are sparse cutting-planes?
• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• scientific article; zbMATH DE number 1313392 (Why is no real title available?)
• Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008.

Cited in

(12)

• Theoretical challenges towards cutting-plane selection
• Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
• Sparse multi-term disjunctive cuts for the epigraph of a function of binary variables
• Sparsity of integer formulations for binary programs
• Constructing New Weighted ℓ₁-Algorithms for the Sparsest Points of Polyhedral Sets
• On Theorem 10 in “On Polar Polytopes and the Recovery of Sparse Representations” [Sep 07 3188-3195]
• How good are sparse cutting-planes?
• Approximation of convex bodies by multiple objective optimization and an application in reachable sets
• Beating the SDP bound for the floor layout problem: a simple combinatorial idea
• Sparse multi-term disjunctive cuts for the epigraph of a function of binary variables
• Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
• Approximating polyhedra with sparse inequalities

This page was built for publication: Some lower bounds on sparse outer approximations of polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1785369)