Quadratic Combinatorial Optimization Using Separable Underestimators

Christoph Buchheim () and Emiliano Traversi ()
Additional contact information
Christoph Buchheim: Fakultät für Mathematik, Technische Universität Dortmund, 44227 Dortmund, Germany
Emiliano Traversi: Laboratoire d’Informatique de Paris Nord, Université Paris 13, 93430 Villetaneuse, France

INFORMS Journal on Computing, 2018, vol. 30, issue 3, 424-437

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 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 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0789 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:30:y:2018:i:3:p:424-437

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().