کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1141491 1489496 2015 27 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The multi-band robust knapsack problem—A dynamic programming approach
ترجمه فارسی عنوان
مشکل چند باند قوی حلقه زدن یک رویکرد برنامه نویسی پویا
کلمات کلیدی
استحکام چند باند، مشکل حلقه برنامه پویا
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
چکیده انگلیسی

In this paper, we consider the multi-band robust knapsack problem which generalizes the ΓΓ-robust knapsack problem by subdividing the single deviation band into several smaller bands. We state a compact ILP formulation and develop two dynamic programming algorithms based on the presented model where the first has a complexity linear in the number of items and the second has a complexity linear in the knapsack capacity. As a side effect, we generalize a result of Bertsimas and Sim on combinatorial optimization problems with uncertain objective. A computational study demonstrates that the second dynamic program is significantly faster than the first algorithm, especially after application of further algorithmic ideas. The improved algorithm clearly outperforms cplex solving the compact ILP formulation.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 18, November 2015, Pages 123–149
نویسندگان
, , ,