Optimization Online


Outer Approximation for Integer Nonlinear Programs via Decision Diagrams

Danial Davarnia (ddavarni***at***andrew.cmu.edu)
Willem-Jan van Hoeve (vanhoeve***at***andrew.cmu.edu)

Abstract: 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.

Keywords: Decision Diagrams, Cutting planes, Outer approximation, Dynamic programming, Integer nonlinear programs

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Other Topics (Dynamic Programming )


Download: [PDF]

Entry Submitted: 03/07/2018
Entry Accepted: 03/07/2018
Entry Last Modified: 06/04/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society