Scalable effective approaches for quadratic assignment problems based on conic optimization and applications

Project Summary

                  Quadratic assignment problem (QAP) has provided a standard model for many problems from facility location, communication and data clustering. For a generic introduction to QAPs, we refer to the Reference [1]. In general, QAP is regarded as one of the hardest discrete optimization problems. For example, solving a QAP instance of size n=30 is recognized as a computational challenge. In most cases, even finding a strong lower bound for QAPs of size n=30 or above is nontrivial. Joint with several colleagues and students, we have been developing new cheap but strong convex programming relaxation schemes that allow us to effectively obtain rather strong lower bounds for large scale QAP instances upto a couple hundreds or even thousands, develop effective approximation algorithms based on low rank matrix decomposition and randomization techniques, as well as extensions to other assignment problems from various applications.

Sample Publications and Reference

      • [1] E.M. Loiola, N.M. Maia de Abreu, P.O. Boaventura-Netto, P. Hahn, and T. Querido. A survey for the quadratic assignment problem. European J. Oper. Res., 176(2), 657–690, 2007.
      • [2] Hans Mittelmann and J. Peng. Estimating Bounds for Quadratic Assignment Problems Associated with Hamming and Manhattan Distance Matrices based on Semidefinite Programming. SIAM J. Optim. Volume 20, Issue 6, pp. 3408-3426,2010.
      • [3] J. Peng, H. Mittelmann and X. Li. A New Convex Relaxation Framework for Quadratic Assignment Problems based on Matrix Splitting. Mathematical Programming: Computation, 1(2), 59-77, 2010.
      • [4] J. Peng, T. Zhu, H.Zh. Luo and K.Ch. Toh.Semi-definite Relaxation of Quadratic Assignment Problems based on Non-redundant Matrix Splitting. J. Comp. Optimi. Applications, 60(1), 171-198, 2015.

 Participants

    • PI: Jiming Peng (UI). Co-PI: Hans Mittlemann (ASU).
    • PhD student: Tao Zhu.
    • Visiting scholar: Dr. Hezhi Luo.
    • Sponsor: AFOSR, 2009–2011.