20.500.12556/DKUM-51786 Copositive and semidefinite relaxations of the quadratic assignment problem 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. matematično programiranje problem kvadratičnega prirejanja kopozitivno programiranje semidefinitna poenostavitev quadratic assignment problem copositive programming semidefinite relaxations lift-and-project relaxations true false false Angleški jezik Neznan jezik Delo ni kategorizirano 2015-07-10 15:08:22 2015-07-10 15:08:22 2022-05-30 03:07:23 2019-07-11 07:28:17 2009 0 0 str. 231-241 iss. 3 Vol. 6 2009 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.85 513620761 15143001 1572-5286 URN:SI:UM:DK:FCHQ0ZVW http://dx.doi.org/10.1016/j.disopt.2009.01.002 1 https://dk.um.si/Dokument.php?lang=slv&id=76346 Fakulteta za logistiko 0 0 0