Strengthening convex relaxations of 0/1-sets using Boolean formulas
From MaRDI portal
(Redirected from Publication:2235155)
Abstract: In convex integer programming, various procedures have been developed to strengthen convex relaxations of sets of integer points. On the one hand, there exist several general-purpose methods that strengthen relaxations without specific knowledge of the set , such as popular linear programming or semi-definite programming hierarchies. On the other hand, various methods have been designed for obtaining strengthened relaxations for very specific sets that arise in combinatorial optimization. We propose a new efficient method that interpolates between these two approaches. Our procedure strengthens any convex set containing a set by exploiting certain additional information about . Namely, the required extra information will be in the form of a Boolean formula defining the target set . The aim of this work is to analyze various aspects regarding the strength of our procedure. As one result, interpreting an iterated application of our procedure as a hierarchy, our findings simplify, improve, and extend previous results by Bienstock and Zuckerberg on covering problems.
Recommendations
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Strong valid inequalities for orthogonal disjunctions and bilinear covering sets
- Ap-cone sequential relaxation procedure for 0-1 integer programs
- A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
- Combining semidefinite and polyhedral relaxations for integer programs
Cites work
- scientific article; zbMATH DE number 1757962 (Why is no real title available?)
- scientific article; zbMATH DE number 6850362 (Why is no real title available?)
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Approximate fixed-rank closures of covering problems
- Characterizing polytopes in the 0/1-cube with bounded Chvátal-Gomory rank
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Disjunctive Programming
- Edmonds polytopes and a hierarchy of combinatorial problems
- Exponential lower bounds for polytopes in combinatorial optimization
- Extension complexity of independent set polytopes
- High degree sum of squares proofs, Bienstock-Zuckerberg hierarchy and CG cuts
- Improving integrality gaps via Chvátal-Gomory rounding
- Maximum semidefinite and linear extension complexity of families of polytopes
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Monotone Circuits for the Majority Function
- Monotone circuits for matching require linear depth
- Monotone circuits for monotone weighted threshold functions
- No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
- On some polytopes contained in the 0,1 hypercube that have a small Chvátal rank
- On the membership problem for the elementary closure of a polyhedron
- On the nonnegative rank of distance matrices
- Relating monotone formula size and monotone depth of Boolean functions
- Small extended formulation for knapsack cover inequalities from monotone circuits
- Some \(0/1\) polytopes need exponential size extended formulations
- Subset Algebra Lift Operators for 0-1 Integer Programming
- The complexity of cover inequality separation
Cited in
(3)
This page was built for publication: Strengthening convex relaxations of 0/1-sets using Boolean formulas
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2235155)
