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

Authors

G. Claßen, A. Koster, A. Schmeink,

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.

BibTEX Reference Entry 

@article{ClKoSc15,
	author = {Grit Cla{\"s}en and Arie Koster and Anke Schmeink},
	title = "The Multi-Band Robust Knapsack Problem -- A Dynamic Programming Approach",
	pages = "123-149",
	journal = "Discrete Optimization",
	volume = "18",
	doi = 10.1016/J.DISOPT.2015.09.007,
	month = Nov,
	year = 2015,
	hsb = RWTH-2015-06142,
	}

Downloads

 Download bibtex-file

Sorry, this paper is currently not available for download.