Copositive and semidefinite relaxations of the quadratic assignment problem.

*(English)*Zbl 1167.90597Summary: Semidefinite relaxations of the quadratic assignment problem \((QAP)\) have recently turned out to provide good approximations to the optimal value of \(QAP\). We take a systematic look at various conic relaxations of \(QAP\). We first show that \(QAP\) can equivalently be formulated as a linear program over the cone of completely positive matrices. Since it is hard to optimize over this cone, we also look at tractable approximations and compare with several relaxations from the literature. We show that several of the well-studied models are in fact equivalent. It is still a challenging task to solve the strongest of these models to reasonable accuracy on instances of moderate size.

##### MSC:

90C10 | Integer programming |

90C20 | Quadratic programming |

90C22 | Semidefinite programming |

90C27 | Combinatorial optimization |

##### Keywords:

quadratic assignment problem; copositive programming; semidefinite relaxations; lift-and-project relaxations##### Software:

QAPLIB
PDF
BibTeX
XML
Cite

\textit{J. Povh} and \textit{F. Rendl}, Discrete Optim. 6, No. 3, 231--241 (2009; Zbl 1167.90597)

Full Text:
DOI

##### References:

[1] | Koopmans, T.C.; Beckmann, M.J., Assignment problems and the location of economics activities, Econometrica, 25, 53-76, (1957) · Zbl 0098.12203 |

[2] | Çela, F., The quadratic assignment problem: theory and algorithms, (1998), Kluwer Academic Publishers Dordrecht · Zbl 0909.90226 |

[3] | Rendl, F., The quadratic assignment problem, () · Zbl 0565.90055 |

[4] | Loiola, E.M.; de Abreu, N.M.M.; Boaventura-Netto, P.O.; Hahn, P.; Querido, T., A survey for the quadratic assignment problem, European J. oper. res., 176, 2, 657-690, (2007) · Zbl 1103.90058 |

[5] | Sahni, S.; Gonzales, T., P-complete approximation problems, J. assoc. comput. Mach., 23, 555-565, (1976) · Zbl 0348.90152 |

[6] | Anstreicher, K., Recent advances in the solution of quadratic assignment problems, Math. program. B, 97, 27-42, (2003) · Zbl 1035.90067 |

[7] | R. Sotirov, Bundle methods in combinatorial optimization, Ph.D. Thesis, Universität Klagenfurt, Klagenfurt, 2003 |

[8] | Rendl, F.; Sotirov, R., Bounds for the quadratic assignment problem using the bundle method, Math. program. ser. B, 109, 2-3, 505-524, (2007) · Zbl 1278.90303 |

[9] | Zhao, Q.; Karisch, S.E.; Rendl, F.; Wolkowicz, H., Semidefinite programming relaxations for the quadratic assignment problem, J. comb. optim., 2, 71-109, (1998) · Zbl 0904.90145 |

[10] | Burer, S.; Vandenbussche, D., Solving lift-and-project relaxations of binary integer programs, SIAM J. optim., 16, 726-750, (2006) · Zbl 1113.90100 |

[11] | Lovász, L.; Schrijver, A., Cones of matrices and set-functions and 0-1 optimization, SIAM J. optim., 1, 166-190, (1991) · Zbl 0754.90039 |

[12] | Anstreicher, K.; Wolkowicz, H., On Lagrangian relaxation of quadratic matrix constraints, SIAM J. matrix anal. appl., 22, 41-55, (2000) · Zbl 0990.90088 |

[13] | Horn, R.A.; Johnson, C.R., Matrix analysis, (1985), Cambridge University Press · Zbl 0576.15001 |

[14] | J. Povh, F. Rendl, Approximating non-convex quadratic programs by semidefinite and copositive programming, in: Proceedings of the 11th International Conference on Operational Research KOI 2006, 2008 · Zbl 1180.90223 |

[15] | De Klerk, E.; Pasechnik, D.V., Approximation of the stability number of a graph via copositive programming, SIAM J. optim., 12, 875-892, (2002) · Zbl 1035.90058 |

[16] | Povh, J.; Rendl, F., A copositive programming approach to graph partitioning, SIAM J. optim., 18, 1, 223-241, (2007) · Zbl 1143.90025 |

[17] | Helmberg, C.; Rendl, F.; Mohar, B.; Poljak, S., A spectral approach to bandwidth and separator problems in graphs, Linear multilinear algebra, 39, 73-90, (1995) · Zbl 0832.05093 |

[18] | S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs, Math. program., published online on April 29th, 2008 |

[19] | P.A. Parrilo, Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization, Ph.D. Thesis, California Institute of Technology, Pasadena, 2000 |

[20] | Laurent, M., A comparison of the sherali – adams, lovász – schrijver and Lasserre relaxations for 0-1 programming, Math. oper. res., 28, 470-496, (2003) · Zbl 1082.90084 |

[21] | X. Zhao, D. Sun, K. Toh, A Newton-CG augmented Lagrangian method for semidefinite programming, Optimization online 2008. Available from http://www.optimization-online.org/DB_HTML/2008/03/1930.html, October 2008 |

[22] | R.E. Burkard, F. Çela, S.E. Karisch, F. Rendl, QAPLIB - A Quadratic Assignment Problem Library. Available at http://www.seas.upenn.edu/qaplib/, February 2006 · Zbl 0729.90993 |

[23] | J. Povh, Application of semidefinite and copositive programming in combinatorial optimization, Ph.D. Thesis, University of Ljubljana, Faculty of Mathematics and Physics, Ljubljana, 2006 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.