# Evolutionary Bi-objective Optimization for the Dynamic Chance-Constrained Knapsack Problem Based on Tail Bound Objectives

arXiv: https://arxiv.org/abs/2002.06766 · HTML: https://mlsanity.com/paper/2002.06766/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2020.

## Built on by (most cited first, 4 of 4)

- [Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees](https://mlsanity.com/paper/2110.09332/) (2021)
- [Using 3-Objective Evolutionary Algorithms for the Dynamic Chance Constrained Knapsack Problem](https://mlsanity.com/paper/2404.06014/) (2024)
- [On the use of evolutionary optimization for the dynamic chance constrained open-pit mine scheduling problem](https://mlsanity.com/paper/2604.13385/) (2026)
- [Sampling-based Pareto Optimization for Chance-constrained Monotone Submodular Problems](https://mlsanity.com/paper/2404.11907/) (2024)

## Abstract (arXiv)

Real-world combinatorial optimization problems are often stochastic and dynamic. Therefore, it is essential to make optimal and reliable decisions with a holistic approach. In this paper, we consider the dynamic chance-constrained knapsack problem where the weight of each item is stochastic, the capacity constraint changes dynamically over time, and the objective is to maximize the total profit subject to the probability that total weight exceeds the capacity. We make use of prominent tail inequalities such as Chebyshev's inequality, and Chernoff bound to approximate the probabilistic constraint. Our key contribution is to introduce an additional objective which estimates the minimal capacity bound for a given stochastic solution that still meets the chance constraint. This objective helps to cater for dynamic changes to the stochastic problem. We apply single- and multi-objective evolutionary algorithms to the problem and show how bi-objective optimization can help to deal with dynamic chance-constrained problems.