Optimization Online


The Multi-Band Robust Knapsack Problem -- A Dynamic Programming Approach --

Grit Claßen (classen***at***umic.rwth-aachen.de)
Arie M.C.A. Koster (koster***at***math2.rwth-aachen.de)
Anke Schmeink (schmeink***at***umic.rwth-aachen.de)

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.

Keywords: multi-band robustness, knapsack problem, dynamic program

Category 1: Robust Optimization


Download: [PDF]

Entry Submitted: 02/25/2014
Entry Accepted: 02/25/2014
Entry Last Modified: 02/25/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society