Strengthening convex relaxations of 0/1-sets using Boolean formulas

DOI10.1007/S10107-020-01542-WzbMATH Open1478.90060arXiv1711.01358OpenAlexW3042828318MaRDI QIDQ2235155FDOQ2235155

Authors: Samuel Fiorini, Tony Huynh, Stefan Weltge 

Publication date: 20 October 2021

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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 $S$, 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 $Qsubseteqmathbb{R}^n$ containing a set $Ssubseteq{0,1}^n$ by exploiting certain additional information about $S$. Namely, the required extra information will be in the form of a Boolean formula $phi$ defining the target set $S$. 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.

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

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

Mathematics Subject Classification ID

Convex programming (90C25) Integer programming (90C10) Networks and circuits as models of computation; circuit complexity (68Q06)

Cites Work

• The complexity of cover inequality separation
• Relating monotone formula size and monotone depth of Boolean functions
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Disjunctive Programming
• On the nonnegative rank of distance matrices
• Some \(0/1\) polytopes need exponential size extended formulations
• Title not available (Why is that?)
• Edmonds polytopes and a hierarchy of combinatorial problems
• Improving integrality gaps via Chvátal-Gomory rounding
• On the membership problem for the elementary closure of a polyhedron
• Exponential lower bounds for polytopes in combinatorial optimization
• Monotone circuits for monotone weighted threshold functions
• Approximate fixed-rank closures of covering problems
• Subset Algebra Lift Operators for 0-1 Integer Programming
• Monotone circuits for matching require linear depth
• Extension complexity of independent set polytopes
• Maximum semidefinite and linear extension complexity of families of polytopes
• Monotone Circuits for the Majority Function
• High degree sum of squares proofs, Bienstock-Zuckerberg hierarchy and CG cuts
• No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
• Title not available (Why is that?)
• On some polytopes contained in the 0,1 hypercube that have a small Chvátal rank
• Characterizing polytopes in the 0/1-cube with bounded Chvátal-Gomory rank
• Small extended formulation for knapsack cover inequalities from monotone circuits

Cited In (3)

• Extended formulations via decision diagrams
• Pitch, extension complexity, and covering problems
• Set characterizations and convex extensions for geometric convex-hull proofs

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)