A New Relaxation Framework for Quadratic Assignment Problems based on Matrix Splitting

  • Xiaoxue Li
  • Hans D Mittelmann
  • Jiming Peng
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Linear, Cone and Semidefinite Programming Tags , , , , Short URL: https://optimization-online.org/?p=10668

    Quadratic assignment problems (QAPs) are 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 the strongest bounds in the literature. Promising experimental results based on the new relaxations will be reported.

    Citation

    Math. Prog. Comp. 2, 59-77 (2010)

    Article

    Download

    View A New Relaxation Framework for Quadratic Assignment Problems based on Matrix Splitting