Optimization Online


Quadratic combinatorial optimization using separable underestimators

Christoph Buchheim (christoph.buchheim***at***tu-dortmund.de)
Emiliano Traversi (emiliano.traversi***at***tu-dortmund.de)

Abstract: Binary programs with a quadratic objective function are NP-hard in general, even if the linear optimization problem over the same feasible set is tractable. In this paper, we address such problems by computing quadratic global underestimators of the objective function that are separable but not necessarily convex. Exploiting the binary constraint on the variables, a minimizer of the separable underestimator over the feasible set can be computed by solving an appropriate linear minimization problem over the same feasible set. Embedding the resulting lower bounds into a branch-and-bound framework, we obtain an exact algorithm for the original quadratic binary program. The main practical challenge is the fast computation of an appropriate underestimator, which in our approach reduces to solving a series of semidefinite programs. We exploit the special structure of the resulting problems and adapt an algorithm of Dong (2014) in order to obtain a tailored coordinate-descent method for their solution. Our extensive experimental results on various quadratic combinatorial optimization problems show that our approach outperforms both Cplex and the related QCR method as well as the SDP-based software BiqCrunch on instances of the quadratic shortest path problem and the quadratic assignment problem.

Keywords: Binary Quadratic Optimization, Separable Underestimators, Quadratic Shortest Path Problem

Category 1: Integer Programming (0-1 Programming )

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Linear, Cone and Semidefinite Programming (Semi-definite Programming )


Download: [PDF]

Entry Submitted: 10/24/2012
Entry Accepted: 10/24/2012
Entry Last Modified: 02/27/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