Join us in welcoming Josh Domeyer, a research scientist at Toyota, as he discusses global solver for mixed-integer nonlinear programs. Alums and friends of the program are always welcome.
A graphical global solver for mixed-integer nonlinear programs
While mixed-integer linear programming and convex programming solvers have advanced significantly over the past several decades, solution technologies for general mixed-integer nonlinear programs (MINLPs) have yet to reach the same level of maturity. Various problem structures across different application domains remain challenging to model and solve using modern global solvers, primarily due to the lack of efficient parsers and convexification routines for their complex algebraic representations. In this paper, we introduce a novel graphical framework for globally solving MINLPs based on decision diagrams (DDs), which enable the modeling of complex problem structures that are intractable for conventional solution techniques. We describe the core components of this framework, including a graphical reformulation of MINLP constraints, convexification techniques derived from the constructed graphs, efficient cutting plane methods to generate linear outer approximations, and a spatial branch-and-bound scheme with convergence guarantees. In addition to providing a global solution method for tackling challenging MINLPs, our framework addresses a longstanding gap in the DD literature by developing a general-purpose DD-based approach for solving general MINLPs. To demonstrate its capabilities, we apply our framework to solve instances from one of the most difficult classes of unsolved test problems in the MINLP Library, which are otherwise inadmissible for state-of-the-art global solvers.
Danial Davarnia is an Assistant Professor and Black-&-Veatch Faculty Fellow in the Industrial and Manufacturing Systems Engineering Department at Iowa State University. Prior to this position, he was a postdoctoral fellow in the Tepper School of Business at Carnegie Mellon University. He earned his PhD in Industrial Engineering from the University of Florida. His research interests include developing solution methodology and efficient computational tools for challenging mixed-integer nonlinear (nonconvex) programs, with applications in transportation, energy, finance, and network interdiction. His research has been recognized by several awards, including the Harvey J. Greenberg Research Award from INFORMS Computing Society, the Young Investigator Program Award from the Air Force Office of Scientific Research, and the CAREER Award from the NSF.
