1) LP-Relaxations of Kidney Exchange Problem formulations
The kidney exchange problem (KEP) is the problem of, given a set of patient-donor pairs and possibly non-directed donors, finding the maximum number of transplants that can be performed under the constraints that i) whenever the donor in a pair donates his kidney, the patient must receive one in return, ii) the length of cycles and chains respect a given upper bound. Around the world, many kidney exchange programs have been established, which use (variants of) the KEP problem to allocate donor kidneys. While this problem is NP-hard in general, real-life instances can usually be solved extremely quickly using standard IP-solvers. One reason for this is that IP-formulations for this problem have very tight LP-relaxations in practice.
Goals of the bachelor project:
*) Investigate the scientific literature on KEP formulations.
*) Investigate the integrality gaps of various known formulations.