Comparative analysis of linear programming relaxations for the robust knapsack problem

Seulgi Joung (), Seyoung Oh () and Kyungsik Lee ()
Additional contact information
Seulgi Joung: Chonnam National University
Seyoung Oh: Seoul National University
Kyungsik Lee: Seoul National University

Annals of Operations Research, 2023, vol. 323, issue 1, No 4, 65-78

Abstract: Abstract In this study, we consider the robust knapsack problem defined by the model of Bertsimas and Sim (Operations Research 52(1):35–53, 2004) where each item weight is uncertain and is defined with an interval. The problem is to choose a subset of items that is feasible for all of the cases in which up to a pre-specified number of items are allowed to take maximum weights simultaneously while maximizing the sum of profits of chosen items. Several integer optimization formulations for the problem have been proposed, however the strength of the upper bounds obtained from their LP-relaxations have not been theoretically analyzed and compared. In this paper, we establish a theoretical relationship among those formulations in terms of their LP-relaxations. Especially, we theoretically prove that previously proposed strong formulations (two extended formulations and a formulation using submodularity) yield the same LP-relaxation bound. In addition, through computational tests with benchmark instances, we analyze the trade-off between the strength of the lower bounds and the required computation time to solve the LP-relaxations. The results show that the formulation using submodularity shows competitive theoretical and computational performance.

Keywords: Robust knapsack problem; Integer optimization models; Strong formulations; Linear programming relaxations; Comparative analysis (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-022-05161-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:323:y:2023:i:1:d:10.1007_s10479-022-05161-w

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-022-05161-w

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().