Optimization Online


Mining for diamonds - matrix generation algorithms for binary quadratically constrained quadratic problems

Enrico Bettiol(enrico.bettiol***at***math.tu-dortmund.de)
Immanuel Bomze(immanuel.bomze***at***univie.ac.at)
Lucas Létocart(letocart***at***lipn.univ-paris13.fr)
Francesco Rinaldi(rinaldi***at***math.unipd.it)
Emiliano Traversi(traversi***at***lipn.univ-paris13.fr)

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

Keywords: Binary Quadratically Constrained Quadratic Programs, Dantzig-Wolfe Reformulation, Boolean Quadric Polytope, Sparse Problem

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

Category 2: Linear, Cone and Semidefinite Programming (Other )


Download: [PDF]

Entry Submitted: 04/23/2020
Entry Accepted: 04/23/2020
Entry Last Modified: 04/23/2020

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