Titel
Mining for diamonds—Matrix generation algorithms for binary quadratically constrained quadratic problems
Autor*in
... show all
Abstract
In this paper, we consider binary quadratically constrained quadratic problems and propose a new approach to generate stronger bounds than the ones obtained using the Semidefinite Programming relaxation. The new relaxation is based on the Boolean Quadric Polytope and is solved via a Dantzig–Wolfe Reformulation in matrix space. For block-decomposable problems, we extend the relaxation and analyze the theoretical properties of this novel approach. If overlapping size of blocks is at most two (i.e., when the sparsity graph of any pair of intersecting blocks contains either a cut node or an induced diamond graph), we establish equivalence to the one based on the Boolean Quadric Polytope. We prove that this equivalence does not hold if the sparsity graph is not chordal and we conjecture that equivalence holds for any block structure with a chordal sparsity graph. The tailored decomposition algorithm in the matrix space is used for efficiently bounding sparsely structured problems. Preliminary numerical results show that the proposed approach yields very good bounds in reasonable time.
Stichwort
Binary quadratic problemDantzig–Wolfe ReformulationBoolean Quadric PolytopeSparse problem
Objekt-Typ
Sprache
Englisch [eng]
Persistent identifier
Erschienen in
Titel
Computers & Operations Research
Band
142
ISSN
0305-0548
Erscheinungsdatum
2022
Publication
Elsevier BV
Erscheinungsdatum
2022
Zugänglichkeit
Rechte
Rechteangabe
© 2022 The Author(s)
Universität Wien | Universitätsring 1 | 1010 Wien | T
+43-1-4277-0