Model-based algorithms for the 0-1 Time-Bomb Knapsack Problem
研究了0-1定时炸弹背包问题，每个物品有爆炸概率，目标是最大化期望利润。提出了两种基于部分线性化的模型算法，在文献实例上表现最佳。
A stochastic version of the 0–1 Knapsack Problem recently introduced in the literature and named the 0–1 Time-Bomb Knapsack Problem is the topic of the present work. In this problem, in addition to profit and weight, each item is characterized by a probability of exploding, and therefore destroying all the contents of the knapsack, in case it is loaded. The optimization aims at maximizing the expected profit of the selected items, which takes into account also the probabilities of explosion, while fulfilling the capacity constraint. The problem has real-world applications in logistics and cloud computing. In this work, two model-based algorithms are introduced. They are based on partial linearizations of a non-linear model describing the problem. Extensive computational results on the instances available in the literature are presented to position the new methods as the best-performing ones, while comparing against those previously proposed.