Professor Tuomas Sandholm (Carnegie Mellon University, USA) gave a guest lecture on HIIT (Helsinki Institute of Information Technology) new lecture series "Helsinki Distinguished Lecture Series on Future Information Technology" at the Open Innovation House, Aalto University Campus.
HIIT is a joint research institute between University of Helsinki and Aalto University, Finland.
Abstract of the lecture
In kidney exchanges, patients with kidney disease can obtain compatible donors by swapping their own willing but incompatible donors. The clearing problem involves finding a social welfare maximizing set of non-overlapping short cycles. We proved this is NP-hard. It was one of the main obstacles to a national kidney exchange. We developed the first algorithm capable of clearing these exchanges optimally on a nationwide scale. The key was incremental problem formulation because the formulation that gives tight LP bounds is too large to even store. On top of the branch-and-price paradigm we developed techniques that dramatically improve runtime and memory usage. Furthermore, clearing is actually an online problem where patient-donor pairs and altruistic donors appear and expire over time. We first developed trajectory-based online stochastic optimization algorithms (that use our optimal offline solver as a subroutine) for this. Such algorithms tend to be too compute-intensive at run time, so recently we developed a general approach for giving batch algorithms guidance about the future without a run-time hit. It learns potentials of elements of the problem, and then uses them in each batch clearing. I will share experiences from using our algorithms to run the UNOS US-wide kidney exchange and two regional ones. We introduced several design enhancements to the exchanges. For one, we used our algorithms to launch the first never-ending altruistic donor chains. I will present new results - both theoretical and experimental - on the role of long chains. I will also discuss planning that is robust against last-minute execution failures.
Video by Aalto University Communications 2012.