Text

Decision Diagram Decomposition for Quadratically Constrained Binary Optimization

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 individual 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.

Ketersediaan

Informasi Detail

Judul Seri

INFORMS JOURNAL ON COMPUTING; Vol.33 No.1 Winter 2021

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 401 - 418

Bahasa

English

ISBN/ISSN

-

Klasifikasi

-

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

NETWORKS/GRAPHS: FLOW ALGORITHMS
NETWORKS/GRAPHS: GENERALIZED NETWORKS
PROGRAMMING: INTEGER: ALGORITHMS

Info Detail Spesifik

https://doi.org/10.1287/ijoc.2019.0938

Pernyataan Tanggungjawab

David Bergman, Leonardo Lozano

Versi lain/terkait

Lampiran Berkas

Komentar