Back to search

University of Strathclyde

Solution techniques for bi-level knapsack problems and application in allocation of healthcare funds problem

Abstract

dc:description.abstract

In consideration to the significant healthcare funds given by donors, both rich countries and philanthropic organizations, it is important to allocate this aid money in an effective way. The conventional mechanism of healthcare funds allocation to the projects is based on cost-effectiveness, i.e. the projects are ranked in their profit to cost ratios and are prioritized based on this ranking. An alternative approach of allocating subsidies to projects that are just cost-ineffective to a country rather than funding entire projects that are cost-effective has been proposed in the literature. This approach will not only encourage the country to contribute its resources but it will promote ownership of projects that are subsidized from outside. ABi-level Programming Problem (BLPP) has been used to represent this approach wherein there are two participants- a leader (donor agency) and a follower (recipient country). In this specific BLPP, referred to as Donor-Recipient Bi-level Knapsack Problem (DR-BKP) in our work, the donor has choice to subsidize healthcare projects that are implemented by the recipient country and the country has choice to take these subsidies for project selection using the further funding. There is a set of healthcare projects, each one associated with a certain profit and cost, under consideration by both participants. The cost of every project is common to the participants however the profit values may differ for them. Along with the healthcare projects, the country has an external project that is of no interest to the donor in this setup. Once the donor decides on cost subsidies for the healthcare projects that are within its individual budget, the country solves a knapsack problem with the cost subsidized projects and the external project constrained by its own budget. Starting with an introduction to BLPPs and motivation of application in a healthcare economics problem, we present the DR-BKP in chapter 1. In chapter 2, we give the literature reviewed for the BLPPs and their solution algorithms. In chapter 3, we provide evidence for ?P 2-hardness by showing that the DR-BKP is both NP-hard and Co-NP hard. After showing the existence of a solution for the DR-BKP, we give a pair of finitely converging exact algorithms, an enumeration algorithm and a branching algorithm, and show the convergence of these algorithms. A set of fifteen differing data sets, each having randomly generated ten instances, have been generated and solved to evaluate the performance of the proposed algorithms. These data sets are generated such that they mimic a range of instances arising in real-life, i.e. starting from the ones that can be trivially addressed to the ones that are complex and difficult to solve. The complexity of some of these data sets is characterized firstly by the external project having higher valuation than the healthcare projects, and then by the discrepancy in the healthcare project valuation done by the two players. From the results of the computational experiments, it can be seen that the branching algorithm performs better when the instances are complex. We give a nested sequential approach in chapter 4 for addressing the DR-BKP, wherein the donor problem is solved using a genetic algorithm and the parameterized country problem is solved using a heuristic or an exact solver. This is followed by computational experiments of solving the fifteen data sets generated in chapter 3 using the genetic algorithm and its results. At the end of chapter 4, we summarize the performance of all the three algorithms over the fifteen data sets. The exact algorithms perform better to solve the data sets with external project having higher valuation than the healthcare projects, whereas the genetic algorithm performs better to solve the data sets having discrepancies in the healthcare project valuation by the two players. In chapter 5, we present generalizations of the proposed solution algorithms to other bi-level optimization frameworks that are closer to realistic scenarios of the application, like a single leader having multiple followers. Finally, we conclude the work done and give directions for future research in chapter 6.

Degree

thesis:*
Name dc:type.qualificationname
phd
Level dc:type.qualificationlevel
doctoral-pg
Grantor dc:publisher.institution
University of Strathclyde
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ghatkar, Shraddha Rahul
Advisors dc:contributor.advisor
  • Arulselvan, Ashwin
  • Morton, Alec (Writer on management science)
Author Identifier dc:creator.authoridentifier
  • 201853931

Rights

Identifiers

dc:identifier.*
Identifier
T17297

Chain of custody

source
Harvested from
University of Strathclyde
Base URL
stax.strath.ac.uk/catalog/oai
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Ghatkar, Shraddha Rahul. Solution techniques for bi-level knapsack problems and application in allocation of healthcare funds problem. doctoral-pg thesis, University of Strathclyde, 2025. https://stax.strath.ac.uk/concern/theses/d217qq156