کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
476365 | 699457 | 2006 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Exploiting semidefinite relaxations in constraint programming
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Exploiting semidefinite relaxations in constraint programming Exploiting semidefinite relaxations in constraint programming](/preview/png/476365.png)
چکیده انگلیسی
Constraint programming uses enumeration and search tree pruning to solve combinatorial optimization problems. In order to speed up this solution process, we investigate the use of semidefinite relaxations within constraint programming. In principle, we use the solution of a semidefinite relaxation to guide the traversal of the search tree, using a limited discrepancy search strategy. Furthermore, a semidefinite relaxation produces a bound for the solution value, which is used to prune parts of the search tree. Experimental results on stable set and maximum clique problem instances show that constraint programming can indeed greatly benefit from semidefinite relaxations.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 33, Issue 10, October 2006, Pages 2787–2804
Journal: Computers & Operations Research - Volume 33, Issue 10, October 2006, Pages 2787–2804
نویسندگان
Willem-Jan van Hoeve,