Recently, several classes of cutting planes have been introduced for binary polynomial optimization. In this paper, we present the first results connecting the combinatorial structure of these inequalities with their Chvatal rank. We show that almost all known cutting planes have Chvatal rank 1. All these inequalities have an associated hypergraph that is beta-acyclic, thus, in order to derive deeper cutting planes, we consider hypergraphs that contain beta-cycles. In particular, we introduce a novel class of valid inequalities arising from odd beta-cycles, that generally have Chvatal rank 2. These cuts subsume odd-cycle inequalities for binary quadratic optimization. We then provide an indication of their theoretical power by showing that they yield the multilinear polytope of cycle hypergraphs. To obtain this result, we introduce a novel proof technique that allows us to iteratively obtain multilinear polytopes of increasingly complex hypergraphs.
Citation
Manuscript