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

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 of feasible integer points, 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 S 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 [Formula: see text] by exploiting certain additional information about S. Namely, the required extra information will be in the form of a Boolean formula [Formula: see text] defining the target set S. The new relaxation is obtained by “feeding” the convex set into the formula [Formula: see text] . We analyze various aspects regarding the strength of our procedure. As one application, 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.