A combinatorial cut-and-lift procedure with an application to 0–1 second-order conic programming

Abstract

Cut generation and lifting are key components for the performance of state-of-the-art mathematical programming solvers. This work proposes a new general cut-and-lift procedure that exploits the combinatorial structure of 0–1 problems via a binary decision diagram (BDD) encoding of their constraints. We present a general framework that can be applied to a wide range of binary optimization problems and show its applicability for second-order conic inequalities. We identify conditions for which our lifted inequalities are facet-defining and derive a new BDD-based cut generation linear program. Such a model serves as a basis for a max-flow combinatorial algorithm over the BDD that can be applied to derive valid cuts more efficiently. Our numerical results show encouraging performance when incorporated into a state-of-the-art mathematical programming solver, significantly reducing the root node gap, increasing the number of problems solved, and reducing the run-time by a factor of three on average.