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

Beitrag in einer Fachzeitschrift
(Originalarbeit)


Details zur Publikation

Autorinnen und Autoren: Hupp LM, Klein L, Liers F
Zeitschrift: Discrete Optimization
Verlag: Elsevier
Jahr der Veröffentlichung: 2015
Band: 18
Seitenbereich: 193-216
ISSN: 1572-5286


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.



FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Hupp, Lena
Professur für Angewandte Mathematik (Ganzzahlige und robuste Optimierung)
Liers-Bergmann, Frauke Prof. Dr.
Professur für Angewandte Mathematik (Ganzzahlige und robuste Optimierung)


Einrichtungen weiterer Autorinnen und Autoren

Technische Universität Dortmund


Zitierweisen

APA:
Hupp, L.M., 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://dx.doi.org/10.1016/j.disopt.2015.10.002

MLA:
Hupp, Lena Maria, 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: 

Zuletzt aktualisiert 2018-09-10 um 21:50