Solution techniques for Bi-level Knapsack Problems
Ghatkar, Shraddha and Arulselvan, Ashwin and Morton, Alec (2023) Solution techniques for Bi-level Knapsack Problems. Computers & Operations Research, 159. 106343. ISSN 0305-0548 (https://doi.org/10.1016/j.cor.2023.106343)
Preview |
Text.
Filename: Ghatkar_etal_COR_2023_Solution_techniques_for_bi_level_knapsack_problems.pdf
Final Published Version License: Download (836kB)| Preview |
Abstract
Traditional funding mechanisms for healthcare projects involve ranking the projects and awarding funds based on their cost to benefit ratio. An alternative funding mechanism based on Bi-level programming was proposed in the literature. We refer to this as Donor-Recipient Bi-level Knapsack Problem (DR-BKP), which we explore further in this work. There are two participants, a leader (a donor agency) and a follower (recipient country) in this problem. Both the participants have their individual budgets. There is a set of projects, each having a certain cost and profit associated. The cost of projects are common to both the participants however the profits can be different for them. There is an external project that is of exclusive interest to the follower. The leader decides on cost subsidies to provide for the projects that is within her budget, while the follower solves a knapsack problem with the cost subsidised projects and the external project. Two enumerative algorithms were proposed in the literature for Bi-level problems with discrete upper level variables. We adapt them for DR-BKP that has continuous upper level variables having non-linear interaction with lower level variables. We first show the existence of a solution for DR-BKP and show the convergence of these algorithms. We provide evidence for -hardness by showing that the problem is both NP-hard and Co-NP hard. Finally, we have implemented these two enumerative algorithms and shared the results and analyses of the computational experiments. A set of fifteen differing data sets each having randomly generated 10 instances have been solved to evaluate the performance of the proposed algorithms.
ORCID iDs
Ghatkar, Shraddha, Arulselvan, Ashwin ORCID: https://orcid.org/0000-0001-9772-5523 and Morton, Alec ORCID: https://orcid.org/0000-0003-3803-8517;-
-
Item type: Article ID code: 86077 Dates: DateEvent30 November 2023Published4 July 2023Published Online30 June 2023AcceptedSubjects: Social Sciences > Industries. Land use. Labor > Management. Industrial Management
Science > MathematicsDepartment: Strathclyde Business School > Management Science
Strategic Research Themes > Health and WellbeingDepositing user: Pure Administrator Date deposited: 07 Jul 2023 15:11 Last modified: 06 Sep 2024 01:11 URI: https://strathprints.strath.ac.uk/id/eprint/86077