کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141576 | 957029 | 2009 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Copositive and semidefinite relaxations of the quadratic assignment problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Semidefinite relaxations of the quadratic assignment problem (QAPQAP) have recently turned out to provide good approximations to the optimal value of QAPQAP. We take a systematic look at various conic relaxations of QAPQAP. We first show that QAPQAP 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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 6, Issue 3, August 2009, Pages 231–241
Journal: Discrete Optimization - Volume 6, Issue 3, August 2009, Pages 231–241
نویسندگان
Janez Povh, Franz Rendl,