TY - JOUR

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

AU - Goerigk, Marc

PY - 2014/12

Y1 - 2014/12

N2 - 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.

AB - 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.

KW - Branch-and-bound

KW - Max–min optimization

KW - Robust knapsack problem

KW - Robust optimization

U2 - 10.1007/s10479-014-1618-2

DO - 10.1007/s10479-014-1618-2

M3 - Journal article

AN - SCOPUS:84939885629

VL - 223

SP - 461

EP - 469

JO - Annals of Operations Research

JF - Annals of Operations Research

SN - 0254-5330

IS - 1

ER -