Decision Diagram Decomposition for Quadratically Constrained Binary Optimization

DOI10.1287/IJOC.2019.0938MaRDI QIDQ4995079zbMATH OpenOpenAlexFDO

Authors

Publication date 23 June 2021

Published in INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/ijoc.2019.0938

zbMATH Keywords

flow algorithmsgeneralized networksgraphsinteger programming

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Recommendations

• Decomposition based on decision diagrams
• Theoretical insights and algorithmic tools for decision diagram-based optimization
• Discrete optimization with decision diagrams
• BDD-based optimization for the quadratic stable set problem
• Incorporating bounds from decision diagrams into integer programming

Cites work

• 0/1 vertex and facet enumeration with BDDs
• A brief history of linear and mixed-integer programming computation
• A Class of Hard Small 0-1 Programs
• An effective branch-and-bound algorithm for convex quadratic integer programming
• An efficient compact quadratic convex reformulation for general integer quadratic programs
• Compact representations of all members of an independence system
• Computing the Minimum Fill-In is NP-Complete
• Constructions and in-place operations for MDDs based constraints
• Decision diagrams for optimization
• Discrete optimization with decision diagrams
• Experimental and Efficient Algorithms
• Improved Linear Integer Programming Formulations of Nonlinear Integer Problems
• Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
• Manipulating MDD relaxations for combinatorial optimization
• Network flows. Theory, algorithms, and applications.
• Oblivious bounds on the probability of boolean functions
• On the pathwidth of chordal graphs
• Optimization Bounds from Binary Decision Diagrams
• Pathwidth is NP-Hard for Weighted Trees
• Semidefinite relaxations for non-convex quadratic mixed-integer programming
• Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program
• The unconstrained binary quadratic programming problem: a survey

Cited in

(5)

• A combinatorial cut-and-lift procedure with an application to 0-1 second-order conic programming
• Optimization Bounds from Binary Decision Diagrams
• Decision diagrams for optimization
• Models and Algorithms for the Bin-Packing Problem with Minimum Color Fragmentation
• Decision Diagrams for Discrete Optimization: A Survey of Recent Advances

Describes a project that uses

Uses Software

• Gurobi
• CPLEX
• QPLIB

This page was built for publication: Decision Diagram Decomposition for Quadratically Constrained Binary Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4995079)