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

Ishara Hewa Pathiranage; Aneta Neumann

cs.NEApr 13, 2026

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

Authors: Ishara Hewa Pathiranage, Aneta Neumann

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

Abstract

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.

Figures & tables

Figure 1: Mean and standard deviation of the best obtained profits for CC-MKP instances with a fixed number of items ( $n=300$ ) and varying numbers of knapsacks ( $m\in\{150,50,30\}$ ). Results are shown for variance levels $v\in\{v_{1},v_{2}\}$ across different confidence levels $\alpha$ .

Figure 2: Mean and standard deviation of the best obtained profits for CC-MKP instances with a fixed item-to-knapsack ratio $n/m=10$ and increasing problem sizes $(n,m)\in\{(100,10),(300,30),(500,50)\}$ . Results are presented for variance levels $v\in\{v_{1},v_{2}\}$ across different confidence levels $\alpha$ .

Figure 3: Mean and standard deviation of the best obtained profits for FK4 CC-MKP instances with varying item-to-knapsack ratios $n/m\in\{2,3,4,5,6,10\}$ . Results are shown for variance levels $v\in\{v_{1},v_{2}\}$ and four confidence levels $\alpha$ .

Panel of Figure 4 — Figure 4: Mean and standard deviation of the offline error for DCC-MKP instances with a fixed number of items ( $n=300$ ) and varying numbers of knapsacks ( $m\in\{150,50,30\}$ ), under dynamic capacity changes with frequencies $\nu\in\{20,50,100\}$ . Results are presented for strongly correlated and uncorrelated instances with change magnitude $\eta=0.2$ .

Panel of Figure 5 — Figure 5: Mean and standard deviation of the offline error for DCC-MKP instances with a fixed item-to-knapsack ratio $n/m=10$ and increasing problem sizes $(n,m)\in\{(100,10),(300,30),(500,50)\}$ . Results are reported under dynamic capacity changes $\nu\in\{20,50,100\}$ for strongly correlated and uncorrelated instances with $\eta=0.2$ .

Panel of Figure 6 — Figure 6: Mean and standard deviation of the offline error for FK4 DCC-MKP instances with item-to-knapsack ratios $n/m\in\{2,3,4,5,6,10\}$ . Results are shown under dynamic capacity changes $\nu\in\{20,50,100\}$ for strongly correlated and uncorrelated instances with $\eta=0.2$ .

Combinatorial Optimization

Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.

See all 382 papers

Multi-Objective Evolutionary Optimization of Chance-Constrained Multiple-Choice Knapsack Problems with Implicit Probability Distributions
Mar 9, 2026Xuanfeng Li, Shengcai Liu, Wenjie Chen +2Chance-Constrained Optimization Combinatorial Optimization
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 +1
On the use of evolutionary optimization for the dynamic chance constrained open-pit mine scheduling problem
Apr 15, 2026Ishara Hewa Pathiranage, Aneta NeumannStochastic Optimization Chance-Constrained Optimization
Machine Learning and Optimisation, School of Computer Science and Information Technology, Adelaide University, Adelaide, Australia
Multitask Pareto Optimization for Monotone Submodular Problems with Dynamic Constraints
Aug 11, 2026Liam Wigney, Frank NeumannSubmodular Optimization Evolutionary Multitask Optimization
Optimisation and Logistics School of Computer Science and Information Technology Adelaide University Adelaide, Australia

Mar 9, 2026J/K move · Enter open · S save

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

Xuanfeng Li, Shengcai Liu, Wenjie Chen, Yew-Soon Ong+1

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+1

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

Open paper AskPDF arXiv

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.

Abstract

Combinatorial Optimization

Explore similar work

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

On the use of evolutionary optimization for the dynamic chance constrained open-pit mine scheduling problem

Multitask Pareto Optimization for Monotone Submodular Problems with Dynamic Constraints