Multi-Objective Evolutionary Optimization of Chance-Constrained Multiple-Choice Knapsack Problems with Implicit Probability Distributions
This work is significant for practitioners in fields like 5G network configuration who need to optimize resource allocation under uncertain conditions and multiple conflicting objectives, offering an incremental improvement over existing methods.
This paper addresses the multi-objective chance-constrained multiple-choice knapsack problem (MO-CCMCKP) with implicit probability distributions, aiming to minimize cost and maximize confidence in capacity satisfaction. The proposed NHILS algorithm, incorporating an efficient Monte Carlo method (OPERA-MC) and specialized search strategies, consistently outperforms state-of-the-art multi-objective optimizers on synthetic and real-world 5G network configuration benchmarks.
The multiple-choice knapsack problem (MCKP) is a classic combinatorial optimization with wide practical applications. This paper investigates a significant yet underexplored extension of MCKP: the multi-objective chance-constrained MCKP (MO-CCMCKP) under implicit probability distributions. The goal of the problem is to simultaneously minimize the total cost and maximize the confidence level of satisfying the capacity constraint, capturing essential trade-offs in domains like 5G network configuration. To address the computational challenge of evaluating chance constraints under implicit distributions, we first propose an order-preserving efficient resource allocation Monte Carlo (OPERA-MC) method. This approach adaptively allocates sampling resources to preserve dominance relationships while reducing evaluation time significantly. Further, we develop NHILS, a hybrid evolutionary algorithm that integrates specialized initialization and local search into NSGA-II to navigate sparse feasible regions. Experiments on synthetic benchmarks and real-world 5G network configuration benchmarks demonstrate that NHILS consistently outperforms several state-of-the-art multi-objective optimizers in convergence, diversity, and feasibility. The benchmark instances and source code will be made publicly available to facilitate research in this area.