Thesis
Solution techniques for bi-level knapsack problems and application in allocation of healthcare funds problem
- Creator
- Rights statement
- Awarding institution
- University of Strathclyde
- Date of award
- 2025
- Thesis identifier
- T17297
- Person Identifier (Local)
- 201853931
- Qualification Level
- Qualification Name
- Department, School or Faculty
- 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.
- Advisor / supervisor
- Arulselvan, Ashwin
- Morton, Alec (Writer on management science)
- Resource Type
- DOI
- Date Created
- 2024
Relations
Items
| Thumbnail | Title | Date Uploaded | Visibility | Actions |
|---|---|---|---|---|
|
|
PDF of thesis T17297 | 2025-04-22 | Public | Download |