Online stochastic optimization in the large: Application to kidney exchange

Pranjal Awasthi, Tuomas Sandholm

Research output: Chapter in Book/Report/Conference proceedingConference contribution

54 Scopus citations

Abstract

Kidneys are the most prevalent organ transplants, but demand dwarfs supply. Kidney exchanges enable willing but incompatible donor-patient pairs to swap donors. These swaps can include cycles longer than two pairs as well, and chains triggered by altruistic donors. Current kidney exchanges address clearing (deciding who gets kidneys from whom) as an offline problem: they optimize the current batch. In reality, clearing is an online problem where patient-donor pairs and altruistic donors appear and expire over time. In this paper, we study trajectory-based online stochastic optimization algorithms (which use a recent scalable optimal of-fline solver as a subroutine) for this. We identify tradeoffs in these algorithms between different parameters. We also uncover the need to set the batch size that the algorithms consider an atomic unit. We develop an experimental methodology for setting these parameters, and conduct experiments on real and generated data. We adapt the REGRETS algorithm of Bent and van Hentenryck for the setting. We then develop a better algorithm. We also show that the AMSAA algorithm of Mercier and van Hentenryck does not scale to the nationwide level. Our best online algorithm saves significantly more lives than the current practice of solving each batch separately.

Original languageEnglish (US)
Title of host publicationIJCAI-09 - Proceedings of the 21st International Joint Conference on Artificial Intelligence
PublisherInternational Joint Conferences on Artificial Intelligence
Pages405-411
Number of pages7
ISBN (Print)9781577354260
StatePublished - 2009
Externally publishedYes
Event21st International Joint Conference on Artificial Intelligence, IJCAI 2009 - Pasadena, United States
Duration: Jul 11 2009Jul 16 2009

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
ISSN (Print)1045-0823

Conference

Conference21st International Joint Conference on Artificial Intelligence, IJCAI 2009
Country/TerritoryUnited States
CityPasadena
Period7/11/097/16/09

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Online stochastic optimization in the large: Application to kidney exchange'. Together they form a unique fingerprint.

Cite this