zbMATH — the first resource for mathematics

Copositive and semidefinite relaxations of the quadratic assignment problem. (English) Zbl 1167.90597
Summary: 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
QAPLIB
Full Text: