A note on upper bounds to the robust knapsack problem with discrete scenarios

We consider the knapsack problem in which the objective function is uncertain, and given by a finite set of possible realizations. The resulting robust optimization problem is a max–min problem that follows the pessimistic view of optimizing the worst-case behavior. Several branch-and-bound algorith...

Full description

Saved in:
Bibliographic Details
Published in:Annals of operations research 2014-12, Vol.223 (1), p.461-469
Main Author: Goerigk, Marc
Format: Article
Language:English
Subjects:
Algorithms
Branch & bound algorithms
Business and Management
Combinatorial optimization
Combinatorics
Knapsack problem
Linear programming
Mathematical research
Operations research
Operations Research/Decision Theory
Optimization
Studies
Theory of Computation
Variables
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the knapsack problem in which the objective function is uncertain, and given by a finite set of possible realizations. The resulting robust optimization problem is a max–min problem that follows the pessimistic view of optimizing the worst-case behavior. Several branch-and-bound algorithms have been proposed in the recent literature. In this short note, we show that by using a simple upper bound that is tailored to balance out the drawbacks of the current best approach based on surrogate relaxation, computation times improve by up to an order of magnitude. Additionally, one can make use of any upper bound for the classic knapsack problem as an upper bound for the robust problem.
ISSN:0254-5330
1572-9338
DOI:10.1007/s10479-014-1618-2