|
|
Danny Blom (Eindhoven University of Technology) - Cutting plane techniques for robust kidney exchange models Supervisor: Bart Smeulders Recorded full presentation Abstract The goal of kidney exchange programs is to match recipients with a willing but incompatible donor with another compatible donor, so as to maximize total (weighted) transplants. There is significant uncertainty in this process, as planned transplants may be cancelled for a variety of reasons. Planning exchanges while considering failures, and options for recourse, is therefore crucial. In this paper, we reconsider a robust optimization model with recourse proposed in Carvalho et al. (2020) that takes into account the event that a number of donors leaves the KEP. After these donors have left the program, a new set of exchanges is identified (the recourse decision), with the aim to realize as many of the originally planned transplants. Current algorithmic considerations do not allow to find optimal solutions for the robust optimization model for realistic sized kidney exchanges with a reasonable time frame. Following the iterative framework in Carvalho et al. (2020) for solving a large-scale mixed integer programming model, we propose a new variable and constraint generation method based on a cutting plane approach. A characterization of this method is given based on two widely used integer programming models for kidney exchange programs. Furthermore, a lifting technique is proposed to obtain stronger cuts to speed up computation. Computational results show that our algorithm is very competitive, improving on the running time of the state-of-the-art method by one order of magnitude. Furthermore, our methods are able to solve a large number of previously unsolved instances within the same time limit. This is joint work with Christopher Hojny and Bart Smeulders. |
