Exact algorithms for the 0–1 Time-Bomb Knapsack Problem
Mostra el registre complet Registre parcial de l'ítem
- dc.contributor.author Monaci, Michele
- dc.contributor.author Pike-Burke, Ciara
- dc.contributor.author Santini, Alberto
- dc.date.accessioned 2023-07-17T07:05:06Z
- dc.date.available 2023-07-17T07:05:06Z
- dc.date.issued 2022
- dc.description.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 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.
- dc.format.mimetype application/pdf
- dc.identifier.citation Monaci M, Pike-Burke C, Santini A. Exact algorithms for the 0–1 Time-Bomb Knapsack Problem. Comput Oper Res. 2022;145:105848. DOI: 10.1016/j.cor.2022.105848
- dc.identifier.doi http://dx.doi.org/10.1016/j.cor.2022.105848
- dc.identifier.issn 0305-0548
- dc.identifier.uri http://hdl.handle.net/10230/57585
- dc.language.iso eng
- dc.publisher Elsevier
- dc.relation.ispartof Computers and Operations Research. 2022;145:105848.
- dc.rights © 2022 The Author(s). Published by Elsevier Ltd. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
- dc.rights.accessRights info:eu-repo/semantics/openAccess
- dc.rights.uri http://creativecommons.org/licenses/by/4.0/
- dc.subject.keyword Knapsack Problem
- dc.subject.keyword Stochastic optimisation
- dc.subject.keyword Exact algorithms
- dc.subject.keyword Computational experiments
- dc.title Exact algorithms for the 0–1 Time-Bomb Knapsack Problem
- dc.type info:eu-repo/semantics/article
- dc.type.version info:eu-repo/semantics/publishedVersion