کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4959093 | 1445468 | 2017 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An improved integer linear programming formulation for the closest 0-1 string problem
ترجمه فارسی عنوان
یک فرمول برنامه ریزی خطی بهبود یافته برای نزدیکترین مشکل رشته 0-1
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نزدیکترین مشکل رشته، شعبه و برش، آرامش مستمر،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
The Closest String Problem (CSP) calls for finding an n-string that minimizes its maximum Hamming distance from m given n-strings. Recently, integer linear programs (ILP) have been successfully applied within heuristics to improve efficiency and effectiveness. We consider an ILP for the binary case (0-1 CSP) that updates the previous formulations and solve it by branch-and-cut. The method separates in polynomial time the first closure of {0,12}-Chvátal-Gomory cuts and can either be used stand-alone to find optimal solutions, or as a plug-in to improve heuristics based on the exact solution of reduced problems. Due to the parity structure of the right-hand side, the impressive performances obtained with this method in the binary case cannot be directly replicated in the general case.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 80, April 2017, Pages 94-100
Journal: Computers & Operations Research - Volume 80, April 2017, Pages 94-100
نویسندگان
Claudio Arbib, Mara Servilio, Paolo Ventura,