Abstract: 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. Keywords:matematično programiranje, problem kvadratičnega prirejanja, kopozitivno programiranje, semidefinitna poenostavitev, quadratic assignment problem, copositive programming, semidefinite relaxations, lift-and-project relaxations Published in DKUM: 10.07.2015; Views: 1086; Downloads: 92 Link to full text

Abstract: We consider two classical problems from location theory which may serve as theoretical models for several logistic problems where one wants to assign elements of a set A to elements of a set B such that some linear or quadratic function attains its minimum. It turns out that linear objective function yields a linear assignment problem, which can be solved easily by several primal-dual methods like Hungarian method, Shortest augmenting path method etc. On the other hand, taking quadratic objective function into account makes the problem much harder. The resulting quadratic assignment problem is a very useful model but also very tough problem from theoretical and practical point of view. We list several well-known applications of these models and also the most effective methods to solve the problem. However, it is still a challenging task to solve this problem to optimality when the size of underlying sets A and B is greater than 25 and currently impossible task when the size is greater than 35. Keywords:quadratic assignment problem, linear assignment problem, branch and bound algorithm, heuristics Published in DKUM: 05.06.2012; Views: 1525; Downloads: 111 Full text (204,96 KB) This document has many files! More...