Multi-Objective Evolutionary Optimization of Chance-Constrained Multiple-Choice Knapsack Problems with Implicit Probability Distributions

Xuanfeng Li; Shengcai Liu; Wenjie Chen; Yew-Soon Ong; Ke Tang

cs.NEMar 9, 2026

Multi-Objective Evolutionary Optimization of Chance-Constrained Multiple-Choice Knapsack Problems with Implicit Probability Distributions

Authors: Xuanfeng Li, Shengcai Liu, Wenjie Chen, Yew-Soon Ong, Ke Tang

Organizations: Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China · School of Information Management, Central China Normal University, Wuhan 430079, China · Centre for Frontier AI Research, Institute of High Performance Computing, Agency for Science Technology and Research, Singapore 138632 · College of Computing and Data Science, Nanyang Technological University, Singapore 639798

Abstract

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.

Figures & tables

Fig. 1: Technical architectures and requirement spectrum of heterogeneous 5G network service scenarios: Remote Surgery (mission-critical); Cloud Gaming (balanced); and Video Streaming (cost-sensitive).

Fig. 2: Trade-off and solution distribution heatmap between cost and CL.

Instance	$m$	$n$	$L$	$W^{LAB}$	$W^{APP}$
$ls1$	10	10	500	20	35
$ls2$	10	20	500	14	15
$ls3$	20	10	500	30	41
$ls4$	30	10	500	45	60
$ls5$	40	10	500	58	87
$ls6$	50	10	500	68	97

TABLE I: Problem Instances setting for MO-CCMCKP.

Panel of Figure 5 — Fig. 4: Probability density function. The horizontal axis represents the time delay and the vertical axis represents the probability density.

ST	Absolute Error for Different $W$ Values
ST	13.2	14.7	15.9	16.9	17.9
$10^{2}$	0.013997	0.007000	0.001702	8.74E-05	7.10E-06
$10^{3}$	0.008203	0.003251	0.000349	8.74E-05	7.10E-06
$10^{4}$	0.009426	0.003095	0.000448	4.76E-05	1.57E-05
$10^{5}$	0.008073	0.000737	6.59E-05	2.00E-05	1.43E-05
$10^{6}$	0.007041	0.000975	0.000427	3.85E-05	2.90E-06

TABLE II: Simulation Count and Estimation Error on LAB-ls2

ST	Absolute Error for Different $W$ Values
ST	13.2	14.6	15.8	16.8	17.8
$10^{2}$	0.025311	0.008009	0.000953	9.58E-05	7.90E-06
$10^{3}$	0.006966	0.002918	0.000700	9.58E-05	7.90E-06
$10^{4}$	0.017886	0.003295	0.000262	7.34E-05	7.90E-06
$10^{5}$	0.004049	0.001846	0.000439	3.02E-05	8.68E-06
$10^{6}$	0.000992	0.000829	0.000248	3.73E-05	3.52E-06

TABLE III: Simulation Count and Estimation Error on APP-ls2

$p_{LS}$	HV	IGD	Runtime(s)
0.02	5.73 $\pm$ 0.15	0.55 $\pm$ 0.08	268.9 $\pm$ 24.3
0.05	5.79 $\pm$ 0.12	0.40 $\pm$ 0.07	490.1 $\pm$ 32.7
0.10	5.83 $\pm$ 0.09	0.29 $\pm$ 0.05	859.3 $\pm$ 45.8
0.20	5.84 $\pm$ 0.08	0.28 $\pm$ 0.04	1664.7 $\pm$ 68.9
0.30	5.85 $\pm$ 0.07	0.25 $\pm$ 0.03	2440.7 $\pm$ 92.1

TABLE IV: Sensitivity Analysis of Local Search Operator Calling Probability

p_{LS}

for NHILS

Test Case	Indicators	NHILS	NSGA-II	SPEA-II	ANSGA-II	MOEA/D(ws)	MOEA/D(pbi)	MOEA/D(tche)
LAB-ls1	HV	$\mathbf{0.643\pm 0.153}$	$0.546\pm 0.163$	$0.545\pm 0.079$	$0.565\pm 0.110$	$0.241\pm 0.272$	$0.243\pm 0.247$	$0.238\pm 0.239$
	IGD	$0.322\pm 0.097$	$0.320\pm 0.107$	$\mathbf{0.315\pm 0.106}$	$0.339\pm 0.097$	$\infty$	$\infty$	$\infty$
	IGD+	$\mathbf{0.230\pm 0.146}$	$0.271\pm 0.127$	$0.271\pm 0.111$	$0.286\pm 0.117$	$\infty$	$\infty$	$\infty$
	FSR	$\mathbf{1.000\pm 0.000}$	$0.992\pm 0.027$	$0.997\pm 0.015$	$\mathbf{1.000\pm 0.000}$	$0.940\pm 0.185$	$0.900\pm 0.305$	$0.927\pm 0.252$
	#Gens	$100$	$1231\pm 974$	$1507\pm 1076$	$690\pm 563$	$9607\pm 3994$	$8275\pm 3442$	$9416\pm 3919$
LAB-ls2	HV	$2.958\pm 0.053$	$3.176\pm 0.692$	$3.275\pm 0.631$	$\mathbf{3.386\pm 0.798}$	$2.485\pm 0.720$	$2.031\pm 0.790$	$2.707\pm 0.795$

TABLE V: Performance Comparison of Algorithms Across LAB Instances

Test Case	Indicators	NHILS	NSGA-II	SPEA-II	ANSGA-II	MOEA/D(ws)	MOEA/D(pbi)	MOEA/D(tche)
APP-ls1	HV	$\mathbf{0.368\pm 0.027}$	$0.320\pm 0.084$	$0.321\pm 0.067$	$0.331\pm 0.062$	$0.202\pm 0.125$	$0.200\pm 0.073$	$0.244\pm 0.073$
	IGD	$0.039\pm 0.039$	$0.045\pm 0.027$	$0.042\pm 0.025$	$\mathbf{0.035\pm 0.019}$	$0.084\pm 0.068$	$0.131\pm 0.059$	$0.063\pm 0.060$
	IGD+	$0.035\pm 0.042$	$0.044\pm 0.028$	$0.041\pm 0.026$	$\mathbf{0.032\pm 0.022}$	$0.082\pm 0.070$	$0.131\pm 0.059$	$0.061\pm 0.060$
	FSR	$\mathbf{0.999\pm 0.005}$	$0.988\pm 0.011$	$0.992\pm 0.007$	$0.988\pm 0.010$	$0.943\pm 0.039$	$0.913\pm 0.032$	$0.941\pm 0.032$
	#Gens	$100$	$1340\pm 1055$	$1129\pm 876$	$775\pm 724$	$8953\pm 4124$	$7729\pm 3569$	$8763\pm 4051$
APP-ls2	HV	$\mathbf{0.582\pm 0.061}$	$0.338\pm 0.207$	$0.303\pm 0.190$	$0.394\pm 0.172$	$0.228\pm 0.173$	$0.189\pm 0.160$	$0.264\pm 0.203$

TABLE VI: Performance Comparison of Algorithms Across APP Instances

Panel of Figure 11 — Fig. 5: Pareto front comparisons of algorithms on LAB instances. From left to right and top to bottom: LAB-ls1 to LAB-ls6.

Variant	HV	IGD	Time (s)
Complete	$\mathbf{5.83^{*}\pm 2.88}$	$\mathbf{0.29^{*}\pm 0.34}$	859.32 $\pm$ 873.96
No Local Search	5.30 $\pm$ 2.44	1.93 $\pm$ 2.07	107.32 $\pm$ 100.06
No HybridInit	4.26 $\pm$ 1.75	2.18 $\pm$ 4.97	334.24 $\pm$ 191.82
NSGA-II	3.31 $\pm$ 1.20	2.82 $\pm$ 3.09	$\mathbf{20.36^{*}\pm 15.73}$

TABLE VII: Ablation Study Results of NHILS Components

Fig. 7: Acceleration performance of OPERA-MC compared with fixed-sample MC on various instances.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Fig. 8: Sample size requirement with different error in theory

Estimation error( $\%$ )	5	0.5	0.05	0.005
Hoeffding’s bound	139	13863	1386295	138629437
Chernoff’s bound [ 46 ]	278	27726	2772589	277258873
Alamo’s bound [ 47 ]	1573	15723	157227	1572269

Appendix

TABLE VIII: Relationship between EE and sample size

Chance-Constrained Optimization

Chance-constrained optimization chooses decisions that optimize performance while limiting the probability of violating uncertain constraints.

See all 29 papers

On the Use of Bi-Objective Evolutionary Algorithms for the Stochastic MKP under Dynamic Constraints
Apr 13, 2026Ishara Hewa Pathiranage, Aneta NeumannCombinatorial Optimization Constrained Optimization
Machine Learning and Optimisation, School of Computer Science and Information Technology, Adelaide University, Adelaide, Australia
Optimization for One, Feasibility for Most: Decoupling Optimization from Feasibility in Chance-Constrained Programs
Oct 13, 2026Justin Dumouchelle, Shunyu Yao, Beste Basciftci +1Chance-Constrained Optimization Stochastic Optimization
University of Calgary · University of Iowa
Ranking Constraints via Topological Dual-Directional Search in Evolutionary Multi-Objective Optimization
Apr 6, 2026Ruiqing Sun, Dawei Feng, Sheng Qi +6Multi-Objective Evolutionary Optimization Evolutionary Optimization
National Key Laboratory of Parallel and Distributed Computing, College of Computer Science and Technology, National University of Defense Technology, Changsha 410000, P.R. China · College of System Engineering, National University of Defense Technology, Changsha 410000, P.R. China · College of Intelligence Science and Technology, National University of Defense Technology, Changsha 410073, P.R. China +1

Apr 13, 2026J/K move · Enter open · S save

On the Use of Bi-Objective Evolutionary Algorithms for the Stochastic MKP under Dynamic Constraints

Ishara Hewa Pathiranage, Aneta Neumann

Machine Learning and Optimisation, School of Computer Science and Information Technology, Adelaide University, Adelaide, Australia

Combinatorial Optimization Constrained Optimization Multi-Objective Optimization Multi-Objective Evolutionary Optimization Chance-Constrained Optimization

Open paper AskPDF arXiv

The multiple knapsack problem (MKP) generalizes the classical knapsack problem by assigning items to multiple knapsacks subject to capacity constraints. It is used to model many real-world resource allocation and scheduling problems. In practice, these optimization problems often involve stochastic and dynamic components. Evolutionary algorithms provide a flexible framework for addressing such problems under uncertainty and dynamic changes. In this paper, we investigate a stochastic and dynamic variant of MKP with chance constraints, where the item weights are modeled as independent normally distributed random variables and knapsack capacities change during the optimization process. We formulate the problem as a bi-objective optimization formulation that balances profit maximization and probabilistic capacity satisfaction at a given confidence level. We conduct an empirical comparison of four widely used multi-objective evolutionary algorithms (MOEAs), representing both decomposition- and dominance-based search paradigms. The algorithms are evaluated under varying uncertainty levels, confidence thresholds, and dynamic change settings. The results provide comparative insights into the behavior of decomposition-based and dominance-based MOEAs for stochastic MKP under dynamic constraints.

Abstract

Chance-Constrained Optimization

Explore similar work

On the Use of Bi-Objective Evolutionary Algorithms for the Stochastic MKP under Dynamic Constraints

Optimization for One, Feasibility for Most: Decoupling Optimization from Feasibility in Chance-Constrained Programs

Ranking Constraints via Topological Dual-Directional Search in Evolutionary Multi-Objective Optimization