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

• URL: http://arxiv.org/abs/2603.08209v1
• Date: Mon, 09 Mar 2026 10:39:58 GMT
• Title: Multi-Objective Evolutionary Optimization of Chance-Constrained Multiple-Choice Knapsack Problems with Implicit Probability Distributions
• Abstract summary: This paper investigates a significant yet underexplored extension of the multiple-choice knapsack problem (MCKP)<n>The goal of the problem is to simultaneously minimize the total cost and maximize the confidence level of satisfying the capacity constraint.<n> Experiments on synthetic benchmarks and real-world 5G network configuration benchmarks demonstrate that NHILS consistently outperforms several state-of-the-art multi-objectives.
• Score: 40.96538452098451
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• A Hybrid Classical-Quantum Approach for Multi-Constrained Location Optimization Problem [0.19573380763700712]
  The Maximal Covering Location Problem (MCLP) aims to determine the optimal facility placements that maximize total coverage.<n>It is characterized by both equality and inequality constraints, which ensure correct coverage but significantly increase the complexity of exploring the solution space as instance size grows.<n>In this work, the MCLP is formulated as a Quadratic Unconstrained Binary Optimization model, where constraint embedding plays a critical role in solution quality.
  arXiv  Detail & Related papers  (2026-07-08T19:44:55Z)
• Lagrangian Relaxation Score-based Generation for Mixed Integer linear Programming [13.20958452268089]
  generative framework based on Lagrangian relaxation-guided differential equations (SDEs)<n>System generates diverse, high-quality solution candidates that collectively define compact and effective trust-region subproblems for standard MILP solvers.
  arXiv  Detail & Related papers  (2026-03-25T07:48:01Z)
• MMR1: Enhancing Multimodal Reasoning with Variance-Aware Sampling and Open Resources [113.33902847941941]
  Variance-Aware Sampling (VAS) is a data selection strategy guided by Variance Promotion Score (VPS)<n>We release large-scale, carefully curated resources containing 1.6M long CoT cold-start data and 15k RL QA pairs.<n> Experiments across mathematical reasoning benchmarks demonstrate the effectiveness of both the curated data and the proposed VAS.
  arXiv  Detail & Related papers  (2025-09-25T14:58:29Z)
• Multiclass Portfolio Optimization via Variational Quantum Eigensolver with Dicke State Ansatz [0.0]
  We introduce a novel quantum framework for portfolio optimization that explicitly incorporates diversification.<n>A key strength of this ansatz is that it initializes the quantum system in a superposition of only feasible states.<n>Our findings demonstrate that, when combined with the CMA-ES, the Dicke state ansatz achieves superior performance in terms of convergence rate, approximation ratio, and measurement probability.
  arXiv  Detail & Related papers  (2025-08-19T15:45:07Z)
• Stochastic Optimization with Optimal Importance Sampling [49.484190237840714]
  We propose an iterative-based algorithm that jointly updates the decision and the IS distribution without requiring time-scale separation between the two.<n>Our method achieves the lowest possible variable variance and guarantees global convergence under convexity of the objective and mild assumptions on the IS distribution family.
  arXiv  Detail & Related papers  (2025-04-04T16:10:18Z)
• Federated Conditional Stochastic Optimization [110.513884892319]
  Conditional optimization has found in a wide range of machine learning tasks, such as in-variant learning tasks, AUPRC, andAML. This paper proposes algorithms for distributed federated learning.
  arXiv  Detail & Related papers  (2023-10-04T01:47:37Z)
• Chance-Constrained Multiple-Choice Knapsack Problem: Model, Algorithms, and Applications [38.98556852157875]
  We focus on the practical scenario of CCMCKP, where the probability distributions of random weights are unknown but only sample data is available. To solve CCMCKP, we propose a data-driven adaptive local search (DDALS) algorithm.
  arXiv  Detail & Related papers  (2023-06-26T13:35:05Z)
• Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables [11.310502327308575]
  We study the scenario of components that are independent and normally distributed. We introduce a multi-objective formulation of the problem which trades off the expected cost and its variance. We prove that this approach can also be used to compute a set of optimal solutions for the chance constrained minimum spanning tree problem.
  arXiv  Detail & Related papers  (2021-09-13T09:24:23Z)
• 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)
• Distributionally Robust Bayesian Quadrature Optimization [60.383252534861136]
  We study BQO under distributional uncertainty in which the underlying probability distribution is unknown except for a limited set of its i.i.d. samples. A standard BQO approach maximizes the Monte Carlo estimate of the true expected objective given the fixed sample set. We propose a novel posterior sampling based algorithm, namely distributionally robust BQO (DRBQO) for this purpose.
  arXiv  Detail & Related papers  (2020-01-19T12:00:33Z)

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.