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

• 成果类型: Article
• 署名作者: Fiorini, Samuel; Huynh, Tony; Weltge, Stefan
• 署名单位: Universite Libre de Bruxelles; Monash University; Technical University of Munich
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01542-w
• 发表日期: 2021
• 页码: 467-482
• 关键词: monotone circuits; complexity

摘要

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 setSof 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 setsSthat 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 S subset of {0,1}(n) by exploiting certain additional information aboutS. Namely, the required extra information will be in the form of a Boolean formula phi defining the target set S. The new relaxation is obtained by feeding the convex set into the formula phi. 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.