Investigation of matching problems using constraint programming and optimisation methods

Simple item page
dc.availability.bitstreamopenaccess
dc.contributor.advisorO'Sullivan, Barryen
dc.contributor.advisorexternalMilano, Michelaen
dc.contributor.authorChisca, Danuta Sorina
dc.contributor.funderScience Foundation Irelanden
dc.contributor.funderEuropean Regional Development Funden
dc.date.accessioned2020-05-12T10:00:09Z
dc.date.available2020-05-12T10:00:09Z
dc.date.issued2019-11
dc.date.submitted2019-11
dc.description.abstractThis thesis focuses on matching under ordinal preferences, i.e. problems where agents may be required to list other agents that they find acceptable in order of preference. In particular, we focus on two main cases: the popular matching and the kidney exchange problem. These problems are important in practice and in this thesis we develop novel algorithms and techniques to solve them as combinatorial optimisation problems. The first part of the thesis focuses on one-sided matching on a bipartite graph, specifically the popular matching. When the participants express their preferences in a cardinal order, the most common desire is to maximise a utility function, for example finding the maximum weight or minimum cost matching. If preferences are ordinal in nature, one might want to guarantee that no two applicants are inclined to form a coalition in order to maximise their welfare, thus finding a stable matching is needed. Therefore, negotiating the size and the optimality of the matching with respect to agents’ preferences is a problem that occurs naturally. Popularity is a concept that offers an attractive trade- off between these two notions. In short, a popular matching is a matching in which the majority of the participants will decide on a matching M . In particular, we examine the popular matching in the context of constraint programming using global constraints. We discuss the possibility to find a popular matching even for the instances that does not admit one. The second part of the thesis focuses on non-bipartite graphs, i.e. the kidney exchange problem, a recent innovation that matches patients in need of a kidney to willing living donors. Kidney transplant is the most effective treatment to cure end-stage renal disease, affecting one in every thousand European citizens. Chronic kidney disease is a life threatening health issue that affects millions of people worldwide. Motivated by the observation that the kidney exchange is inherently a stochastic online problem, first, we give a stochastic online method. This methos is more general and provides an expected value estimation that is correct within the limit of sampling errors. Sec- ond, we show that by taking into consideration a probabilistic model of future arrivals and drop-offs, we can get reduce sampling scenarios, and we can even construct a sampling-free probabilistic model, called the Abstract Exchange Graph (AEG). A final contribution of this thesis is related to finding robust solutions when uncertainty occurs. Uncertainty is inherent to most real world problems. For instance in the case of Kidney Exchange Problem (KEP), if a pair pools out from the solution we need to find a repair solution quickly to limit the impact to other pairs. We propose a method that exploits a Logic-Based Benders Decomposition to find super solutions to an optimisation problem.en
dc.description.statusPeer revieweden
dc.format.mimetypeapplication/pdfen
dc.identifier.citationChisca, D. S. 2019. Investigation of matching problems using constraint programming and optimisation methods. PhD Thesis, University College Cork.en
dc.identifier.endpage153en
dc.identifier.urihttps://hdl.handle.net/10468/9921
dc.language.isoenen
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/en
dc.rights© 2019, Danuta Sorina Chisca.en
dc.rights.urihttps://creativecommons.org/licenses/by-nc-nd/4.0/en
dc.subjectOptimisationen
dc.subjectKidney exchanges problemen
dc.subjectMatching problemsen
dc.subjectStochastic optimisationen
dc.titleInvestigation of matching problems using constraint programming and optimisation methodsen
dc.typeDoctoral thesisen
dc.type.qualificationlevelDoctoralen
dc.type.qualificationnamePhD - Doctor of Philosophyen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
ChiscaDS_PHD2019.pdf
Size:
4.6 MB
Format:
Adobe Portable Document Format
Description:
Full Text E-thesis
Download
License bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
license.txt
Size:
5.2 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Thumbnail Image
Name:
3.11415538-Danuta Sorina Chisca-Softbound Submission.pdf
Size:
127.46 KB
Format:
Adobe Portable Document Format
Description:
Submission for Examination Form
Collections
Research Theses Submission
College of Science, Engineering and Food Science - Doctoral Theses
Computer Science - Doctoral Theses
Insight Centre for Data Analytics - Doctoral Theses