Exact algorithms for the 0-1 Time-Bomb Knapsack Problem

We consider a stochastic version of the 0-1 Knapsack Problem in which, in addition to profit and weight, each item is associated with a probability of exploding and destroying all the contents of the knapsack. The objective is to maximise the expected profit of the selected items. The resulting problem, denoted as 0-1 Time-Bomb Knapsack Problem (01-TB-KP), has applications in logistics and cloud computing scheduling. We introduce a nonlinear mathematical formulation of the problem, study its computational complexity, and propose techniques to derive upper and lower bounds using convex optimisation and integer linear programming. We present three exact approaches based on enumeration, branch and bound, and dynamic programming, and computationally evaluate their performance on a large set of benchmark instances. The computational analysis shows that the proposed methods outperform the direct application of nonlinear solvers on the mathematical model, and provide high quality solutions in a limited amount of time.

Automated summary

Introduces a stochastic version of the 0-1 Knapsack Problem, known as the 0-1 Time-Bomb Knapsack Problem, where each item is associated with a probability of exploding. A nonlinear mathematical formulation is presented, and the computational complexity is studied. Techniques for deriving upper and lower bounds using convex optimization and integer linear programming are proposed. Three exact approaches based on enumeration, branch and bound, and dynamic programming are presented and evaluated computationally, showing superior performance compared to direct application of nonlinear solvers.