An exact solution method for quadratic matching: The one-quadratic-term technique and generalisations

Hupp L, Klein L, Liers F (2015)

Publication Status: Published

Publication Type: Journal article, Original article

Publication year: 2015

Journal

Discrete Optimization Elsevier

Publisher: Elsevier

Book Volume: 18

Pages Range: 193-216

DOI: 10.1016/j.disopt.2015.10.002

Abstract

The quadratic matching problem (QMP) asks for a matching in a graph that optimises a quadratic objective in the edge variables. The QMP generalises the quadratic assignment problem as the latter can be seen as a perfect matching on a bipartite graph. In our approach, we strengthen the linearised IP-formulation by cutting planes that are derived from facets of the corresponding matching problem where only one quadratic term is present in the objective function (QMP1). As the influence of these cutting planes on the root bound decreases for instances with more quadratic terms in the objective, we present different methods to strengthen these cutting planes. Adopting the idea of the reformulation linearisation technique (RLT) we derive valid inequalities for the general QMP from QMP1 facets. Following the approach in Fomeni et al. (2015) we replace cubic terms that appear in a reformulated QMP1 inequality by a quadratic estimator. Based on these methods we design and implement an exact branch-and-cut approach. When compared to solving the standard linearised IP formulation strengthened by cutting planes that result from the application of the RLT to the degree inequalities, we show that root bounds and cpu times for solving instances to optimality can significantly be improved, when the new method is applied.

Authors with CRIS profile

Lena Hupp Frauke Liers-Bergmann Professur für Optimization under Uncertainty & Data Analysis

Involved external institutions

Technische Universität Dortmund DE Germany (DE)

How to cite

APA:

Hupp, L., Klein, L., & Liers, F. (2015). An exact solution method for quadratic matching: The one-quadratic-term technique and generalisations. Discrete Optimization, 18, 193-216. https://doi.org/10.1016/j.disopt.2015.10.002

MLA:

Hupp, Lena, Laura Klein, and Frauke Liers. "An exact solution method for quadratic matching: The one-quadratic-term technique and generalisations." Discrete Optimization 18 (2015): 193-216.

BibTeX: Download