The multi-band robust knapsack problem–A dynamic programming approach

The multi-band robust knapsack problem–A dynamic programming approach

0.00 Avg rating0 Votes
Article ID: iaor201530304
Volume: 18
Issue: 11
Start Page Number: 123
End Page Number: 149
Publication Date: Nov 2015
Journal: Discrete Optimization
Authors: , ,
Keywords: programming: dynamic, combinatorial optimization
Abstract:

In this paper, we consider the multi‐band robust knapsack problem which generalizes the Γ equ1‐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.

Reviews

Required fields are marked *. Your email address will not be published.