Chance-Constrained Multiple-Choice Knapsack Problem: Model, Algorithms, and Applications

Xuanfeng Li1; Shengcai Liu2; Jin Wang3; Xiao Chen3; Yew-Soon Ong2,4; Ke Tang1

2024

10.1109/TCYB.2024.3402395

IEEE Transactions on Cybernetics   影响因子和分区

2168-2275

The multiple-choice knapsack problem (MCKP) is a classic NP-hard combinatorial optimization problem. Motivated by several significant real-world applications, this work investigates a novel variant of MCKP called the chance-constrained MCKP (CCMCKP), where item weights are random variables. In particular, we focus on the practical scenario of CCMCKP, in which the probability distributions of random weights are unknown and only sample data is available. We first present the problem formulation of CCMCKP and then establish the two benchmark sets. The first set contains synthetic instances, while the second set is designed to simulate a real-world application scenario of a telecommunication company. To solve CCMCKP, we propose a data-driven adaptive local search (DDALS) algorithm. Compared to existing stochastic optimization and distributionally robust optimization methods, the main novelty of DDALS lies in its data-driven solution evaluation approach, which does not make any assumptions about the underlying distributions and is highly effective even when faced with a high intensity of the chance constraint and a limited amount of sample data. Experimental results demonstrate the superiority of DDALS over the baselines on both the benchmarks. Finally, DDALS can serve as the baseline for future research, and the benchmark sets are open-sourced to further promote research on this challenging problem.

SCI ; EI

第一

1.Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation and Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen, China
2.Centre for Frontier AI Research, Agency for Science, Technology and Research, Singapore, Singapore
3.Reliability Laboratory, Huawei Technologies Co Ltd, Shenzhen, China
4.College of Computing and Data Science, Nanyang Technological University, Singapore, Singapore

Xuanfeng Li,Shengcai Liu,Jin Wang,et al. Chance-Constrained Multiple-Choice Knapsack Problem: Model, Algorithms, and Applications[J]. IEEE Transactions on Cybernetics,2024,PP(99).

Xuanfeng Li,Shengcai Liu,Jin Wang,Xiao Chen,Yew-Soon Ong,&Ke Tang.(2024).Chance-Constrained Multiple-Choice Knapsack Problem: Model, Algorithms, and Applications.IEEE Transactions on Cybernetics,PP(99).

Xuanfeng Li,et al."Chance-Constrained Multiple-Choice Knapsack Problem: Model, Algorithms, and Applications".IEEE Transactions on Cybernetics PP.99(2024).