Efficient Algorithms with Performance Guarantees for the Stochastic Multiple-Choice Knapsack Problem

Long Tran-Thanh, Yingce Xia, Tao Qin, Nicholas R. JenningsIJCAI 2015 · OpenReview

Abstract

We study the stochastic multiple-choice knapsack problem, where a set of $K$ items, whose value and weight are random variables, arrive to the system at each time step, and a decision maker has to choose at most one item to put into the knapsack without exceeding its capacity. The goal of the decision-maker is to maximise the total expected value of chosen items with respect to the knapsack capacity and a finite time horizon. We provide the first comprehensive theoretical analysis of the problem. In particular, we propose OPT-S-MCKP, the first algorithm that achieves optimality when the value-weight distributions are known. This algorithm also enjoys $O(\sqrt{T})$ performance loss, where $T$ is the finite time horizon, in the unknown value-weight distributions scenario. We also further develop two novel approximation methods, FR-S-MCKP and G-S-MCKP, and we prove that FR-S-MCKP achieves $O(\sqrt{T})$ performance loss in both known and unknown value-weight distributions cases, while enjoying polynomial computational complexity per time step. On the other hand, G-S-MCKP does not have theoretical guarantees, but it still provides good performance in practice with linear running time.

1. Introduction

The classic knapsack problem is a cornerstone of combinatorial optimization. However, real-world applications often involve uncertainty and sequential decision-making. This paper addresses the Stochastic Multiple-Choice Knapsack Problem (S-MCKP), where items arrive over a finite time horizon $T$. At each step, a decision-maker is presented with a set of $K$ candidates, each with random values and weights, and must select at most one item to maximize total expected utility without exceeding a fixed capacity $C$.

This model fits critical real-world scenarios such as autonomous rescue robots managing limited battery life while selecting tasks, or online advertising platforms choosing the optimal ad to display from a candidate pool in real-time.

2. Proposed Algorithms

We introduce three distinct algorithms to tackle S-MCKP under varying computational and informational constraints:

  • OPT-S-MCKP (Optimal): Utilizes Bellman equations and Dynamic Programming to find the mathematically optimal strategy when distributions are known. While optimal, its $O(KTC)$ complexity makes it computationally expensive for large-scale problems.
  • FR-S-MCKP (Fractional Relaxation): A more efficient approach that relaxes the discrete selection constraint to allow fractional choices in a simplified model. It solves this relaxed problem at each step to guide real-world decisions, offering polynomial computational cost and a guaranteed $O(\sqrt{T})$ performance loss.
  • G-S-MCKP (Greedy): A fast, linear-time heuristic. At each step, it identifies the item that would provide the highest total value if chosen for all remaining time steps. While it currently lacks a formal theoretical bound, it performs remarkably well in practice.

For scenarios where distributions are unknown, we integrate these algorithms with an estimation phase. By using empirical data from observed items to estimate means and probabilities, we prove that the performance loss remains sub-linear ($O(\sqrt{T})$), effectively learning the optimal strategy on the fly.

3. Experimental Evaluation

The algorithms were evaluated using synthetic numerical simulations featuring 50 items per time step ($K=50$). Values and weights were sampled from discrete sets, and the knapsack capacity was set to 10,000. Results were averaged over 100 independent runs to ensure robustness.

4. Results and Analysis

Our analysis confirms that both OPT-S-MCKP and FR-S-MCKP achieve $O(\sqrt{T})$ performance loss, the "gold standard" in online learning. This indicates that as time progresses, the average mistake per time step converges to zero.

4.1 Performance under Uncertainty

Empirical results demonstrate that the algorithms are highly robust to information gaps. As shown in the figure below, there is only a marginal performance dip when moving from known to unknown distributions, validating the effectiveness of the empirical estimation method.

Performance in the unknown distributions case.

4.2 Computational Efficiency

The trade-off between optimality and speed is significant. G-S-MCKP emerged as the clear winner in efficiency, running approximately four orders of magnitude faster than the optimal DP solution and significantly faster than the fractional relaxation method.

Computational cost comparison (log scale).

5. Conclusion

This work provides the first comprehensive theoretical framework and efficient algorithms for S-MCKP. We demonstrate that near-optimal performance is achievable even with unknown distributions and limited computational budgets. Future work will explore non-stationary environments where item distributions shift over time and seek to provide formal theoretical guarantees for the greedy heuristic.

Summary updated

Abstract

We study the stochastic multiple-choice knapsack problem, where a set of K items, whose value and weight are random variables, arrive to the system at each time step, and a decision maker has to choose at most one item to put into the knapsack without exceeding its capacity. The goal of the decision-maker is to maximise the total expected value of chosen items with respect to the knapsack capacity and a finite time horizon. We provide the first comprehensive theoretical analysis of the problem. In particular, we propose OPT-S-MCKP, the first algorithm that achieves optimality when the value-weight distributions are known. This algorithm also enjoys O(√T) performance loss, where T is the finite time horizon, in the unknown value-weight distributions scenario. We also further develop two novel approximation methods, FR-S-MCKP and G-S-MCKP, and we prove that FR-S-MCKP achieves O(√T) performance loss in both known and unknown value-weight distributions cases, while enjoying polynomial computational complexity per time step. On the other hand, G-S-MCKP does not have theoretical guarantees, but it still provides good performance in practice with linear running time.
BibTeX
@inproceedings{tranthanh2015efficient,
  author = {Long Tran-Thanh and Yingce Xia and Tao Qin and Nicholas R. Jennings},
  title = {{Efficient Algorithms with Performance Guarantees for the Stochastic Multiple-Choice Knapsack Problem}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=SkNksXM_WH},
}
Figure