Strong Relaxations for Continuous Nonlinear Programs Based on Decision Diagrams

Over the past decade, Decision Diagrams (DDs) have risen as a powerful modeling tool to solve discrete optimization problems. The extension of this emerging concept to continuous problems, however, has remained a challenge, posing a limitation on its applicability scope. In this paper, we introduce a novel framework that utilizes DDs to model continuous programs. In particular, we develop a new relaxation concept for DDs that leads to strong linear outer approximations for continuous nonlinear programs. This framework, when combined with the array of developed techniques for discrete problems, illuminates a new pathway to solving mixed integer nonlinear programs with the help of DDs. Preliminary computational experiments conducted on a nonconvex pricing application show the potential of our framework by reporting a remarkable gap closure compared to the state-of-the-art global solvers.

Article

Download

View Strong Relaxations for Continuous Nonlinear Programs Based on Decision Diagrams