کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6897661 | 1446036 | 2014 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems](/preview/png/6897661.png)
چکیده انگلیسی
The reformulation-linearization technique (RLT), introduced in [Sherali, H. D., Adams. W. P. (1990). A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics 3(3), 411-430], provides a way to compute a hierarchy of linear programming bounds on the optimal values of NP-hard combinatorial optimization problems. In this paper we show that, in the presence of suitable algebraic symmetry in the original problem data, it is sometimes possible to compute level two RLT bounds with additional linear matrix inequality constraints. As an illustration of our methodology, we compute the best-known bounds for certain graph partitioning problems on strongly regular graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 233, Issue 3, 16 March 2014, Pages 488-499
Journal: European Journal of Operational Research - Volume 233, Issue 3, 16 March 2014, Pages 488-499
نویسندگان
Etienne de Klerk, Marianna E. -Nagy, Renata Sotirov, Uwe Truetsch,