Final published version
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - The robust knapsack problem with queries
AU - Goerigk, Marc
AU - Gupta, Manoj
AU - Ide, Jonas
AU - Schöbel, Anita
AU - Sen, Sandeep
PY - 2015/3
Y1 - 2015/3
N2 - We consider robust knapsack problems where item weights are uncertain. We are allowed to query an item to find its exact weight,where the number of such queries is bounded by a given parameter Q. After these queries are made, we need to pack the items robustly, i.e., so that the choice of items is feasible for every remaining possible scenario of item weights. The central question that we consider is: Which items should be queried in order to gain maximum profit? We introduce the notion of query competitiveness for strict robustness to evaluate the quality of an algorithm for this problem, and obtain lower and upper bounds on this competitiveness for interval-based uncertainty. Similar to the study of online algorithms, we study the competitiveness under different frameworks, namely we analyze the worst-case query competitiveness for deterministic algorithms, the expected query competitiveness for randomized algorithms and the average case competitiveness for known distributions of the uncertain input data. We derive theoretical bounds for these different frameworks and evaluate them experimentally. We also extend this approach to Γ-restricted uncertainties introduced by Bertsimas and Sim. Furthermore, we present heuristic algorithms for the problem. In computational experiments considering both the interval-based and the Γ-restricted uncertainty, we evaluate their empirical performance. While the usage of a Γ-restricted uncertainty improves the nominal performance of a solution (as expected), we find that the query competitiveness gets worse.
AB - We consider robust knapsack problems where item weights are uncertain. We are allowed to query an item to find its exact weight,where the number of such queries is bounded by a given parameter Q. After these queries are made, we need to pack the items robustly, i.e., so that the choice of items is feasible for every remaining possible scenario of item weights. The central question that we consider is: Which items should be queried in order to gain maximum profit? We introduce the notion of query competitiveness for strict robustness to evaluate the quality of an algorithm for this problem, and obtain lower and upper bounds on this competitiveness for interval-based uncertainty. Similar to the study of online algorithms, we study the competitiveness under different frameworks, namely we analyze the worst-case query competitiveness for deterministic algorithms, the expected query competitiveness for randomized algorithms and the average case competitiveness for known distributions of the uncertain input data. We derive theoretical bounds for these different frameworks and evaluate them experimentally. We also extend this approach to Γ-restricted uncertainties introduced by Bertsimas and Sim. Furthermore, we present heuristic algorithms for the problem. In computational experiments considering both the interval-based and the Γ-restricted uncertainty, we evaluate their empirical performance. While the usage of a Γ-restricted uncertainty improves the nominal performance of a solution (as expected), we find that the query competitiveness gets worse.
KW - Competitiveness
KW - Queries
KW - Robust knapsack problem
KW - Robust optimization
U2 - 10.1016/j.cor.2014.09.010
DO - 10.1016/j.cor.2014.09.010
M3 - Journal article
AN - SCOPUS:84908627994
VL - 55
SP - 12
EP - 22
JO - Computers and Operations Research
JF - Computers and Operations Research
SN - 0305-0548
ER -