Article ID Journal Published Year Pages File Type
1141491 Discrete Optimization 2015 27 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Control and Optimization
Authors
, , ,