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

Source: arXiv - 2603.08209v1

Overview

The paper tackles a new, tougher variant of the classic multiple‑choice knapsack problem (MCKP) that appears in real‑world systems such as 5G network configuration. Instead of a single objective, the authors consider two competing goals: (1) keep the total cost low and (2) maximize the confidence that the chosen items will respect a capacity limit when the underlying data are uncertain. Because the probability distributions are implicit (i.e., only a black‑box sampler is available), traditional chance‑constrained methods become prohibitively slow. The authors propose a fast Monte‑Carlo evaluation scheme and a tailored evolutionary optimizer that together make this problem tractable.

Key Contributions

• Formal definition of MO‑CCMCKP – a multi‑objective, chance‑constrained version of MCKP with implicit probability distributions.
• OPERA‑MC – an order‑preserving Monte‑Carlo estimator that adaptively allocates sampling effort, preserving Pareto dominance while cutting evaluation time by up to an order of magnitude.
• NHILS – a hybrid NSGA‑II based evolutionary algorithm that adds problem‑specific initialization, a feasibility‑driven local search, and a niching strategy to cope with the extremely sparse feasible region.
• Comprehensive empirical study – synthetic benchmarks plus a realistic 5G network configuration case study, showing consistent superiority over leading multi‑objective optimizers in convergence, diversity, and feasibility ratios.
• Open resources – benchmark instances and source code released publicly to accelerate further research.

Methodology

Problem Modeling

• Each decision variable belongs to a choice group (exactly one item must be selected).
• The total weight is a random variable; the capacity constraint must hold with probability ≥ γ (the confidence level).
• Two objectives are optimized simultaneously: minimize deterministic cost and maximize γ.

OPERA‑MC (Efficient Chance‑Constraint Evaluation)

• Instead of naïvely drawing a huge number of Monte‑Carlo samples for every candidate solution, OPERA‑MC re‑uses samples across the population and allocates more samples to borderline solutions that could flip dominance relationships.
• It maintains the ordering of solutions (i.e., which one dominates the other) with high probability, which is sufficient for evolutionary selection.

NHILS (Hybrid Evolutionary Solver)

• Initialization: seeds the population with heuristic solutions that already satisfy the chance constraint at a modest confidence level, giving the algorithm a foothold in the feasible region.
• Selection & Crossover: standard NSGA‑II mechanisms, but with a bias toward preserving high‑confidence individuals.
• Local Search: a lightweight, feasibility‑oriented repair operator that tweaks a solution’s items to improve its confidence without blowing up cost.
• Niching & Diversity: adaptive crowding distance that encourages exploration of both low‑cost/high‑risk and high‑cost/low‑risk corners of the Pareto front.

Evaluation Protocol

• Benchmarks: 30 synthetic instances (varying group sizes, item counts, and distribution complexities) + 5 real‑world 5G configuration scenarios.
• Baselines: NSGA‑II, MOEA/D, SPEA2, and a recent chance‑constrained GA.
• Metrics: Hypervolume, Inverted Generational Distance (IGD), feasibility ratio, and runtime.

Results & Findings

• Faster Evaluation: OPERA‑MC reduced the number of required samples by ~70 % while keeping dominance ordering correct > 95 % of the time.
• Robust Pareto Fronts: NHILS consistently discovered a wider spread of trade‑offs, giving decision makers more flexibility between cost and reliability.
• Real‑World Impact: In the 5G case study, the algorithm identified configurations that saved up to 18 % of deployment cost while still guaranteeing a 95 % confidence of meeting bandwidth capacity—something the baselines missed entirely.

Practical Implications

• Network Planning: Telecom operators can use NHILS to automatically generate cost‑effective 5G slice configurations that respect probabilistic capacity guarantees, reducing manual tuning cycles.
• Cloud Resource Allocation: The same framework applies to any scenario where resources (CPU, memory, bandwidth) have stochastic demand—e.g., autoscaling policies that must meet SLA confidence levels.
• Supply‑Chain & Logistics: Companies can model uncertain demand or weight distributions while balancing procurement cost against risk of overload.
• Tool Integration: Because OPERA‑MC is a drop‑in estimator, existing evolutionary libraries (DEAP, jMetal, pymoo) can be extended with minimal code changes, enabling rapid prototyping.

Limitations & Future Work

• Implicit Distribution Assumption: The method relies on being able to draw samples; if only moments or bounds are known, OPERA‑MC would need adaptation.
• Scalability to Very Large Instances: Experiments capped at ~10 k items; beyond that, memory for shared samples may become a bottleneck.
• Dynamic Environments: The current formulation assumes a static problem; extending to online or time‑varying constraints (e.g., fluctuating network loads) is an open direction.
• Theoretical Guarantees: While empirical dominance preservation is high, formal probabilistic bounds on OPERA‑MC’s error are left for future analysis.

The authors have released their benchmark suite and implementation on GitHub, making it easy for practitioners to try the approach on their own chance‑constrained combinatorial problems.

Authors

• Xuanfeng Li
• Shengcai Liu
• Wenjie Chen
• Yew‑Soon Ong
• Ke Tang

Paper Information

• arXiv ID: 2603.08209v1
• Categories: cs.NE
• Published: March 9, 2026
• PDF: Download PDF