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

Michele Monaci(michele.monaciunibo.it)
Ciara Pike-Burke(c.pikeburkeimperial.ac.uk)
Alberto Santini(alberto.santiniupf.edu)

Abstract: 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 maximize 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 optimization 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.

Keywords: knapsack problem, stochastic optimisation, exact algorithms

Category 1: Stochastic Programming

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Other Topics (Dynamic Programming )

Citation: 2021

Download: [PDF]

Entry Submitted: 03/30/2021
Entry Accepted: 03/30/2021
Entry Last Modified: 03/30/2021

Modify/Update this entry