A Learning-Based Framework for Fair and Scalable Solution Generation in Kidney Exchange Problems

Abstract

Reinforcement learning and Generative Flow Networks, known as GFlowNets, present an exciting possibility for neural networks to model distributions across various data structures. In this paper, we broaden their applicability to data structures consisting of optimal solutions for a combinatorial problem. Concretely, we propose using Q-learning and various policy gradient methods, as well as GFlowNets to learn the distribution of optimal solutions for kidney exchange problems (KEPs). This could provide a useful tool for decision-making authorities, policymakers and clinicians, as it offers them multiple optimal or near-optimal solutions, and provides a complementary landscape to their traditional integer programming-based toolbox for promoting fairness and societal benefits. Our reinforcement learning-based framework trained on KEP instances provides an effective addition to computationally expensive exact approaches, notably mixed-integer programming. Our experiments thoroughly evaluate the quality of the solution sets sampled from the trained neural networks in terms of optimality, their scalability when dealing with real-sized KEP instances, and their capability to generate a diverse pool of solutions. We also cover the use of their efficient solution generation capabilities to improve fairness and simulate the evolution of the KEP pool in a dynamic setting. Our contribution is thus: 1) methodological, as it introduces a novel setting for reinforcement learning in addition to GFlowNets, 2) implementational, as it delves beyond the theory and details how to use conditional information, and 3) of practical significance, as it considers a specific combinatorial problem in the healthcare domain.