Exact algorithms for the 0–1 Time-Bomb Knapsack Problem
研究0-1定时炸弹背包问题，每个物品有爆炸概率会摧毁已选物品，目标是最大化期望利润。提出三种精确算法，在物流和云计算调度中有应用，实验表明算法优于直接求解非线性模型。
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.