Runtime analysis of RLS and the (1+1) EA for the chance-constrained knapsack problem with correlated uniform weights

Yue Xie, Aneta Neumann, Frank Neumann, Andrew M. Sutton

Abstract

This paper presents the first theoretical runtime analysis of Randomized Local Search (RLS) and the (1+1) Evolutionary Algorithm (EA) for the chance-constrained knapsack problem (CCKP) featuring correlated item weights. We consider a model where items are partitioned into groups with intra-group weight correlation and inter-group independence. By utilizing a surrogate fitness function based on Chebyshev’s inequality and applying multiplicative drift analysis, we demonstrate that these randomized heuristics can efficiently navigate the trade-offs between profit maximization and risk constraint satisfaction. Our results establish that optimal solutions can be reached in $O(n^3)$ expected time for specific profit instances, proving that simple evolutionary strategies remain effective even under complex risk structures.

1. Introduction

The Knapsack Problem (KP) is a fundamental challenge in combinatorial optimization. In its classic form, one seeks to maximize the total profit of selected items without exceeding a fixed weight capacity. However, real-world scenarios often involve uncertainty, leading to the "chance-constrained" version of the problem. In a chance-constrained knapsack problem (CCKP), the weight constraint is not absolute; instead, the probability of violating the capacity must remain below a specified threshold $\alpha$.

While previous theoretical studies have largely assumed that item weights are independent, practical applications—such as logistics or financial portfolio optimization—frequently encounter correlated risks. This paper addresses this gap by analyzing how correlation impacts the runtime of simple evolutionary algorithms.

2. Problem Model and Correlation Structure

We investigate a CCKP where $n$ items are divided into $K$ groups, each containing $m$ items ($n = K \times m$). The weights within each group are correlated with a covariance $c$, while weights between different groups are independent. All items share the same expected weight and variance.

To handle the probabilistic constraint, we employ a surrogate fitness function. Since calculating the exact probability of a constraint violation is often computationally intensive, we use the one-sided Chebyshev’s inequality to provide an upper bound on the risk. The optimization process uses a lexicographic fitness function that prioritizes:

  1. Feasibility: Reducing the risk surrogate until it meets the threshold $\alpha$.
  2. Profit: Maximizing the total value of the items.
  3. Risk Minimization: Further reducing the risk surrogate for solutions with the same profit.

3. Algorithms

Two fundamental randomized search heuristics are analyzed:

  • Randomized Local Search (RLS): This algorithm explores the search space by flipping one or two bits in the bitstring representation of a solution at each step.
  • The (1+1) Evolutionary Algorithm (EA): This algorithm employs a global mutation operator, where each bit is flipped independently with a probability of $1/n$.

4. Theoretical Analysis and Key Insights

The primary analytical tool used in this study is multiplicative drift analysis, which measures the expected progress of the algorithm toward the optimal solution in each iteration.

4.1 The Importance of Balanced Solutions

A critical finding is the role of "balanced solutions." Due to the intra-group correlation, selecting many items from the same group significantly increases the total variance (and thus the risk). To minimize risk for a given number of items, the algorithms must distribute their selections across as many groups as possible. We prove that both RLS and the (1+1) EA naturally drift toward these balanced configurations, as they offer a lower risk profile for the same profit level.

4.2 Runtime Bounds

We analyze the algorithms across two primary instances:

  • Uniform Profits (Instance 4.1): Where all items have a profit of 1. This isolates the difficulty of managing the weight correlations.
  • Mirrored Arbitrary Profits (Instance 5.1): Where each group contains an identical set of items with diverse profit values, testing the algorithm's ability to balance high-value items against their associated risks.

The expected runtimes are summarized below:

Objective RLS Runtime (1+1) EA Runtime
Finding a Feasible Solution $O(n \log n)$ $O(n^2 \log n)$
Optimality (Uniform Profits) $O(n^3)$ $O(n^3 \log n)$
Optimality (Mirrored Profits) $O(n^3)$ $O(n^3 (\log n + \log p_{max}))$

5. Discussion and Conclusion

Our analysis reveals that while correlation introduces additional complexity compared to the independent weight setting, it does not render the problem intractable for simple evolutionary heuristics. The $O(n^3)$ bounds indicate that these algorithms can effectively "shuffle" items between groups to find the optimal balance of profit and risk.

Future work should expand these findings to non-uniform weights and variances, as well as more intricate correlation structures. Additionally, investigating the performance of multi-objective evolutionary algorithms (MOEAs) could provide further insights into navigating the Pareto front of profit versus risk in chance-constrained optimization.

Summary updated

BibTeX
@inproceedings{xie2021runtime,
  author = {Yue Xie and Aneta Neumann and Frank Neumann and Andrew M. Sutton},
  title = {{Runtime analysis of RLS and the (1+1) EA for the chance-constrained knapsack problem with correlated uniform weights}},
  booktitle = {GECCO},
  year = {2021},
  url = {https://openreview.net/forum?id=GRG5X8Bbvh},
}
Figure