Beyond Hand-Derived Inequalities: Decision Diagrams for Cut Generation in Binary Polynomial Optimization
TL;DR
The empirical results show that the DD-based methodologies achieve a larger gap closure at the root node with fewer cuts than existing procedures and, in turn, markedly accelerate branch-and-bound procedures.
Abstract
We study cutting-plane generation for binary polynomial optimization (BPO), whose feasible region is the multilinear set of a hypergraph. Strong inequalities for this set---such as two-links, flowers, and odd $\beta$-cycles---are classically hand-derived for fixed support patterns. Instead, we propose a decision-diagram (DD) approach: for any chosen support, it separates a facet-defining cut in the local multilinear polytope and lifts it back to the original problem. We utilize a novel compact DD encoding based on a recursive formulation that represents only the vertex variables and implicitly encodes the hyperedge variables inside the state representation. From this DD encoding, we also obtain: (i) an extended formulation of the multilinear polytope, (ii) a width characterization via valid antichains that uncovers a new polynomially solvable class of hypergraphs, and (iii) a certificate for the facetness of the generated cuts. We explore three different support strategies for cut generation that reuse, expand, or partition local structures into section hypergraphs. Our empirical results show that our DD-based methodologies achieve a larger gap closure at the root node with fewer cuts than existing procedures and, in turn, markedly accelerate branch-and-bound procedures.