TY  - JOUR
U1  - Wissenschaftlicher Artikel
A1  - Peng, Jiming
A1  - Mittelmann, Hans
A1  - Li, Xiaoxue
T1  - A new relaxation framework for quadratic assignment problems based on matrix splitting
JF  - Mathematical Programming Computation
N2  - Quadratic assignment problems (QAPs) are known to be among the hardest discrete optimization problems. Recent study shows that even obtaining a strong lower bound for QAPs is a computational challenge. In this paper, we first discuss how to construct new simple convex relaxations of QAPs based on various matrix splitting schemes. Then we introduce the so-called symmetric mappings that can be used to derive strong cuts for the proposed relaxation model. We show that the bounds based on the new models are comparable to some strong bounds in the literature. Promising experimental results based on the new relaxations are reported.
AB  - Quadratic assignment problems (QAPs) are known to be among the hardest discrete optimization problems. Recent study shows that even obtaining a strong lower bound for QAPs is a computational challenge. In this paper, we first discuss how to construct new simple convex relaxations of QAPs based on various matrix splitting schemes. Then we introduce the so-called symmetric mappings that can be used to derive strong cuts for the proposed relaxation model. We show that the bounds based on the new models are comparable to some strong bounds in the literature. Promising experimental results based on the new relaxations are reported.
KW  - Software
KW  - Theoretical Computer Science
Y1  - 2010
SN  - 1867-2949
SS  - 1867-2949
U6  - https://doi.org/10.1007/s12532-010-0012-6
DO  - https://doi.org/10.1007/s12532-010-0012-6
VL  - 2
IS  - 1
SP  - 59
EP  - 77
S1  - 19
PB  - Springer Science and Business Media LLC
ER  -