Target Cuts from Relaxed Decision Diagrams
Christian Tjandraatmadja,, Willem-Jan van Hoeve
INFORMS Journal on Computing · 2019 · Volume 31 · Issue 2
Abstract
The most common approach to generate cuts in integer programming is to derive them from the linear programming relaxation. We study an alternative approach that extracts cuts from discrete relaxations known as relaxed decision diagrams. Through a connection between decision diagrams and polarity, the algorithm generates cuts that are facet defining for the convex hull of a decision diagram relaxation. As proof of concept, we provide computational evidence that this algorithm generates strong cuts for the maximum independent set problem and the minimum set covering problem. The online appendices are available at https://doi.org/10.1287/ijoc.2018.0830 .
Keywords
integer programming, cutting planes, decision diagrams
Enable JavaScript for citation tools and additional paper interactions.