کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
477866 | 1446215 | 2006 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Improving the efficiency of the Branch and Bound algorithm for integer programming based on “flatness” information
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Improving the efficiency of the Branch and Bound algorithm for integer programming based on “flatness” information Improving the efficiency of the Branch and Bound algorithm for integer programming based on “flatness” information](/preview/png/477866.png)
چکیده انگلیسی
This paper describes a strategy for defining priorities for the branching variables in a Branch and Bound algorithm. The strategy is based on shape information about the polyhedron over which we are optimizing. This information is related to measures of the integer width, as provided by the so called “Flatness Theorem”. Our selection rule uses that knowledge to define branching priorities on the variables. Computational results with simulated small to medium size integer problems are presented, as well with multi-knapsack problems. These show savings of about 40% in CPU time, as well as in nodes generated in the search tree, and compare favorably with respect to other standard branching rules.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 174, Issue 1, 1 October 2006, Pages 92–101
Journal: European Journal of Operational Research - Volume 174, Issue 1, 1 October 2006, Pages 92–101
نویسندگان
Iván Derpich, Jorge R. Vera,