Outer approximation for integer nonlinear programs via decision diagrams

Thumbnail Image
Date
2021-02-13
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Springer
Authors
Research Projects
Organizational Units
Journal Issue
Is Version Of
Versions
Series
Department
Industrial and Manufacturing Systems Engineering
Abstract
As an alternative to traditional integer programming (IP), decision diagrams (DDs) provide a new solution technology for discrete problems exploiting 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 introducing IP techniques that can be derived from DDs and used in conjunction with IP to enhance the overall performance. This perspective 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 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 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.
Comments
This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at DOI: 10.1007/s10107-020-01475-4. Copyright 2020 Springer-Verlag GmbH Germany. Posted with permission.
Description
Keywords
Citation
DOI
Copyright
Collections