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

• URL: http://arxiv.org/abs/2604.10930v1
• Date: Mon, 13 Apr 2026 02:59:03 GMT
• Title: On the Use of Bi-Objective Evolutionary Algorithms for the Stochastic MKP under Dynamic Constraints
• Abstract summary: The multiple knapsack problem (MKP) generalizes the classical knapsack problem by assigning items to multiple knapsacks subject to capacity constraints.<n>We formulate the problem as a bi-objective optimization formulation that balances profit and capacity satisfaction at a given confidence level.
• Score: 3.6439154309310013
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Neural Projected Quantum Dynamics: a systematic study [0.0]
  We investigate the challenge of classical simulation of unitary quantum dynamics with variational Monte Carlo approaches.<n>We provide a thorough formalization and significant improvements to the projected time-dependent Monte Carlo (p-tVMC) method.<n>This work establishes p-tVMC as a powerful framework for simulating the dynamics of large-scale two-dimensional quantum systems.
  arXiv  Detail & Related papers  (2024-10-14T17:01:33Z)
• A Stochastic Approach to Bi-Level Optimization for Hyperparameter Optimization and Meta Learning [74.80956524812714]
  We tackle the general differentiable meta learning problem that is ubiquitous in modern deep learning. These problems are often formalized as Bi-Level optimizations (BLO) We introduce a novel perspective by turning a given BLO problem into a ii optimization, where the inner loss function becomes a smooth distribution, and the outer loss becomes an expected loss over the inner distribution.
  arXiv  Detail & Related papers  (2024-10-14T12:10:06Z)
• Stability of Primal-Dual Gradient Flow Dynamics for Multi-Block Convex Optimization Problems [2.66854711376491]
  Proposed dynamics are based on the proximal augmented Lagrangian and they provide a viable alternative to ADMM.<n>We leverage various structural properties to establish global (exponential) convergence guarantees for the proposed dynamics.<n>Our assumptions are much weaker than those required to prove (exponential) stability of primal-dual dynamics.
  arXiv  Detail & Related papers  (2024-08-28T17:43:18Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
  We analyze smoothed (perturbed) policies, adding controlled random perturbations to the direction used by the linear oracle.<n>Our main contribution is a generalization bound that decomposes the excess risk into perturbation bias, statistical estimation error, and optimization error.<n>We illustrate the scope of the results on applications such as vehicle scheduling, highlighting how smoothing enables both tractable training and controlled generalization.
  arXiv  Detail & Related papers  (2024-07-24T12:00:30Z)
• Stochastic Q-learning for Large Discrete Action Spaces [79.1700188160944]
  In complex environments with discrete action spaces, effective decision-making is critical in reinforcement learning (RL) We present value-based RL approaches which, as opposed to optimizing over the entire set of $n$ actions, only consider a variable set of actions, possibly as small as $mathcalO(log(n)$)$. The presented value-based RL methods include, among others, Q-learning, StochDQN, StochDDQN, all of which integrate this approach for both value-function updates and action selection.
  arXiv  Detail & Related papers  (2024-05-16T17:58:44Z)
• Multi-Objective Evolutionary Algorithms with Sliding Window Selection for the Dynamic Chance-Constrained Knapsack Problem [2.5690340428649328]
  We propose multi-objective evolutionary approaches for the knapsack problem with profits under static and dynamic weight constraints. We consider a bi-objective formulation that maximises expected profit and minimises variance. We derive a three-objective formulation by relaxing the weight constraint into an additional objective.
  arXiv  Detail & Related papers  (2024-04-12T03:07:15Z)
• Using 3-Objective Evolutionary Algorithms for the Dynamic Chance Constrained Knapsack Problem [9.617143859697322]
  We explore the use of 3-objective evolutionary algorithms for the chance constrained knapsack problem with dynamic constraints. We introduce a 3-objective formulation that is able to deal with the dynamic components at the same time and is independent of the confidence level required for the constraint. Our analysis highlights the advantages of the 3-objective formulation over the 2-objective formulation in addressing the dynamic chance constrained knapsack problem.
  arXiv  Detail & Related papers  (2024-04-09T04:47:01Z)
• Ensemble Kalman Filtering Meets Gaussian Process SSM for Non-Mean-Field and Online Inference [47.460898983429374]
  We introduce an ensemble Kalman filter (EnKF) into the non-mean-field (NMF) variational inference framework to approximate the posterior distribution of the latent states. This novel marriage between EnKF and GPSSM not only eliminates the need for extensive parameterization in learning variational distributions, but also enables an interpretable, closed-form approximation of the evidence lower bound (ELBO) We demonstrate that the resulting EnKF-aided online algorithm embodies a principled objective function by ensuring data-fitting accuracy while incorporating model regularizations to mitigate overfitting.
  arXiv  Detail & Related papers  (2023-12-10T15:22:30Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  We propose to reformulate the result diversification problem as a bi-objective search problem, and solve it by a multi-objective evolutionary algorithm (EA) We theoretically prove that the GSEMO can achieve the optimal-time approximation ratio, $1/2$. When the objective function changes dynamically, the GSEMO can maintain this approximation ratio in running time, addressing the open question proposed by Borodin et al.
  arXiv  Detail & Related papers  (2021-10-18T14:00:22Z)
• Permutation Invariant Policy Optimization for Mean-Field Multi-Agent Reinforcement Learning: A Principled Approach [128.62787284435007]
  We propose the mean-field proximal policy optimization (MF-PPO) algorithm, at the core of which is a permutation-invariant actor-critic neural architecture. We prove that MF-PPO attains the globally optimal policy at a sublinear rate of convergence. In particular, we show that the inductive bias introduced by the permutation-invariant neural architecture enables MF-PPO to outperform existing competitors.
  arXiv  Detail & Related papers  (2021-05-18T04:35:41Z)
• Multiplicative noise and heavy tails in stochastic optimization [62.993432503309485]
  empirical optimization is central to modern machine learning, but its role in its success is still unclear. We show that it commonly arises in parameters of discrete multiplicative noise due to variance. A detailed analysis is conducted in which we describe on key factors, including recent step size, and data, all exhibit similar results on state-of-the-art neural network models.
  arXiv  Detail & Related papers  (2020-06-11T09:58:01Z)
• Single- and Multi-Objective Evolutionary Algorithms for the Knapsack Problem with Dynamically Changing Constraints [13.896724650508087]
  We investigate single- and multi-objective baseline evolutionary algorithms for the classical knapsack problem. Our results show that the multi-objective approaches using a population that caters for dynamic changes have a clear advantage on many benchmarks scenarios.
  arXiv  Detail & Related papers  (2020-04-27T03:50:24Z)
• Evolutionary Bi-objective Optimization for the Dynamic Chance-Constrained Knapsack Problem Based on Tail Bound Objectives [12.634782111072585]
  We consider the dynamic chance-constrained knapsack problem where the weight of each item is the subject of a capacity constraint. The objective is to maximize the total profit subject to the probability that total weight exceeds the capacity. We introduce an additional objective which estimates the minimal capacity bound for a given solution that still meets the chance constraint.
  arXiv  Detail & Related papers  (2020-02-17T04:36:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.