Optimization Online


Decision Diagram Decomposition for Quadratically Constrained Binary Optimization

David Bergman(david.bergman***at***uconn.edu)
Leonaro Lozano(lozanolo***at***ucmail.uc.edu)

Abstract: In recent years the use of decision diagrams within the context of discrete optimization has proliferated. This paper continues this expansion by proposing the use of decision diagrams for modeling and solving binary optimization problems with quadratic constraints. The model proposes the use of multiple decision diagrams to decompose a quadratic matrix so that each component diagram has provably limited size. The decision diagrams are then linked through channeling constraints to ensure that the solution represented is consistent across the decision diagrams and that the original quadratic constraints are satisfied. The resulting family of decision diagrams are optimized over by a dedicated cutting-plane algorithm akin to Benders decomposition. The approach is general, in that commercial integer programming solvers can readily apply the technique. A thorough experimental evaluation on both benchmark and synthetic instances exhibits that the proposed decision diagram reformulation provides significant improvements over current methods for quadratic constraints in state-of-the-art solvers.

Keywords: Networks/graphs:Flow algorithms; Networks/graphs: Generalized networks; Programming:Integer:Algorithms

Category 1: Integer Programming

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization )


Download: [PDF]

Entry Submitted: 10/02/2018
Entry Accepted: 10/02/2018
Entry Last Modified: 10/02/2018

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