کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10347969 | 699358 | 2013 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Achieving MILP feasibility quickly using general disjunctions
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Achieving MILP feasibility quickly using general disjunctions Achieving MILP feasibility quickly using general disjunctions](/preview/png/10347969.png)
چکیده انگلیسی
Branch and bound algorithms for Mixed-Integer Linear Programming (MILP) almost universally branch on a single variable to create disjunctions. General linear expressions involving multiple variables are another option for branching disjunctions, but are not used for two main reasons: (i) descendent LPs tend to solve more slowly because of the added constraints, so the overall solution time is increased, and (ii) it is difficult to quickly find an effective general disjunction. We study the use of general disjunctions to reach the first MILP-feasible solution quickly, showing for the first time that general disjunctions can provide speed improvements for hard MILP models. The speed-up is due to new and efficient ways to (i) trigger the inclusion of a general disjunction only when it is likely to be beneficial, and (ii) construct effective general disjunctions very quickly. Our empirical results show performance improvements versus a state of the art commercial MILP solver.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 40, Issue 8, August 2013, Pages 2094-2102
Journal: Computers & Operations Research - Volume 40, Issue 8, August 2013, Pages 2094-2102
نویسندگان
Hanan Mahmoud, John W. Chinneck,