As an alternative to traditional integer programming (IP), decision diagrams (DDs) provide a new solution technology for discrete problems based on their combinatorial structure and dynamic programming representation. While the literature mainly focuses on the competitive aspects of DDs as a stand-alone solver, we investigate their complementary role by studying IP techniques that can be derived from DDs and used in conjunction with IP to enhance the overall performance. This allows for studying problems with more general structure than those typically modeled via recursive formulations. In particular, we develop linear programming and subgradient-type methods to generate valid inequalities for the convex hull of the feasible region described by DDs. For convex separable IPs, these cutting planes dominate the so-called linearized cuts used in the outer approximation framework. These cutting planes can also be derived for nonconvex separable IPs, which leads to a generalization of the outer approximation framework. Computational experiments show significant optimality gap improvement for integer nonlinear programs over the traditional cutting plane methods employed in the state-of-the-art solvers.
Article
View Outer Approximation for Integer Nonlinear Programs via Decision Diagrams