.png){kind=icon}
.png){kind=icon}
Return
Chance-Constrained Multiple-Choice Knapsack Problem: Model, Algorithms, and Applications
.png){kind=icon}
OA
AI
DOI：10.1109/TCYB.2024.3402395.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Optimization
Probability distribution
Heuristic algorithms
Approximation algorithms
Random variables
Benchmark testing
Supply chains
Chance-constrained multiple-choice knapsack problem (CCMCKP)
combinatorial optimization
data-driven optimization
evolutionary algorithm
Journal
IF:
10.5
Papers:
1.1W
Citations:
5.0W