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.
http://www.hiit.fi/
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.
