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

Area of Science:

• Operations Research
• Combinatorial Optimization
• Data-Driven Optimization

Background:

• The multiple-choice knapsack problem (MCKP) is a well-known NP-hard problem with practical applications.
• A novel variant, the chance-constrained MCKP (CCMCKP), addresses scenarios where item weights are random variables.
• Existing methods struggle when probability distributions are unknown and only sample data is available.

Purpose of the Study:

• To formulate and address the chance-constrained multiple-choice knapsack problem (CCMCKP) under data-driven conditions.
• To develop a novel algorithm that does not require prior knowledge of weight distributions.
• To establish benchmark datasets for evaluating CCMCKP solutions.

Main Methods:

• Problem formulation for CCMCKP with unknown probability distributions.
• Development of a data-driven adaptive local search (DDALS) algorithm.
• Creation of synthetic and real-world telecommunication-based benchmark instances.

Main Results:

• The proposed DDALS algorithm demonstrates superior performance compared to existing stochastic and distributionally robust optimization methods.
• DDALS is effective even with high chance constraint intensity and limited sample data.
• Experimental results validate the effectiveness of DDALS on both synthetic and application-specific benchmarks.

Conclusions:

• DDALS offers a robust and effective data-driven approach for solving CCMCKP without distribution assumptions.
• The developed benchmark sets and DDALS algorithm provide a foundation for future research in this area.
• This work advances the practical applicability of knapsack problem variants in uncertain environments.