A nonparametric robust optimization approach for chance-constrained knapsack problem

Abstract

A chance-constrained knapsack problem (CCKP) is a knapsack problem restricted by a chance constraint, which ensures that the total capacity constraint under uncertain volume can be violated only up to a given probability threshold. CCKP is challenging to solve due to its combinatorial nature and the involvement of its chance constraint. Existing solution methods for CCKP with tractability guarantees mainly focus on two approaches: (1) a full-information approach (stochastic programming) that assumes the uncertain volume follows certain distributions, such as normal or empirical distribution; (2) a partial-information approach (robust optimization) that adopts specific statistics of the unknown distribution, such as the mean and variance. The existing full-information approach lacks robustness under limited samples due to its strong assumption; the existing partial-information approach can be further improved, as the uncertainty set or distributional ambiguity set can be ameliorated. With these concerns in mind, we propose a nonparametric robust approach for CCKP by involving a novel nonparametric statistic to form a new distributional ambiguity set. Furthermore, we develop an upper bound on the violation probability of the chance constraint under the distributional ambiguity set to approximate CCKP by a deterministic robust counterpart. In terms of solution methodology, we decompose the deterministic robust counterpart into cardinality-constrained knapsack problems, which can be efficiently solved by the proposed dynamic programming algorithm. Computational results show that our proposed solution methods produce better solutions to CCKP compared with existing approaches.