Kidney Exchange with Inhomogeneous Edge Existence Uncertainty
This work addresses a critical bottleneck in organ transplantation by enabling more efficient and robust kidney matching under realistic uncertainty, though it is incremental as it builds on existing methods.
The paper tackles the kidney exchange problem with nonidentical edge failure probabilities, proposing a tractable mixed-integer linear programming reformulation and a robust CVaR-based model, achieving better performance than state-of-the-art approaches like PICEF with the same running time and substantial improvements in worst-case performance.
Motivated by kidney exchange, we study a stochastic cycle and chain packing problem, where we aim to identify structures in a directed graph to maximize the expectation of matched edge weights. All edges are subject to failure, and the failures can have nonidentical probabilities. To the best of our knowledge, the state-of-the-art approaches are only tractable when failure probabilities are identical. We formulate a relevant non-convex optimization problem and propose a tractable mixed-integer linear programming reformulation to solve it. In addition, we propose a model that integrates both risks and the expected utilities of the matching by incorporating conditional value at risk (CVaR) into the objective function, providing a robust formulation for this problem. Subsequently, we propose a sample-average-approximation (SAA) based approach to solve this problem. We test our approaches on data from the United Network for Organ Sharing (UNOS) and compare against state-of-the-art approaches. Our model provides better performance with the same running time as a leading deterministic approach (PICEF). Our CVaR extensions with an SAA-based method improves the $α\times 100\%$ ($0<α\leqslant 1$) worst-case performance substantially compared to existing models.