# Strengthening Convex Relaxations of 0/1-Sets Using Boolean Formulas

arXiv: https://arxiv.org/abs/1711.01358 · HTML: https://mlsanity.com/paper/1711.01358/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2017.

## Built on by (most cited first, 3 of 3)

- [Neuro-symbolic Learning Yielding Logical Constraints](https://mlsanity.com/paper/2410.20957/) (2024)
- [Neural Networks and (Virtual) Extended Formulations](https://mlsanity.com/paper/2411.03006/) (2024)
- [Arithmetic Circuits and Neural Networks for Regular Matroids](https://mlsanity.com/paper/2511.02406/) (2025)

## Abstract (arXiv)

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  Q subseteq ℝn  containing a set  S subseteq 0,1n  by exploiting certain additional information about  S . Namely, the required extra information will be in the form of a Boolean formula  φ  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.