کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141633 | 957075 | 2013 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
One-level reformulation of the bilevel Knapsack problem using dynamic programming
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In this paper, we consider the Bilevel Knapsack Problem (BKP), which is a hierarchical optimization problem in which the feasible set is determined by the set of optimal solutions for a parametric Knapsack Problem. We introduce a new reformulation of the BKP into a one-level integer programming problem using dynamic programming. We propose an algorithm that allows the BKP to be solved exactly in two steps. In the first step, a dynamic programming algorithm is used to compute the set of follower reactions to leader decisions. In the second step, an integer problem that is equivalent to the BKP is solved using a branch-and-bound algorithm. Numerical results are presented to show the performance of our method.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 10, Issue 1, February 2013, Pages 1–10
Journal: Discrete Optimization - Volume 10, Issue 1, February 2013, Pages 1–10
نویسندگان
Luce Brotcorne, Saïd Hanafi, Raïd Mansi,