Solving the Kidney Exchange Problem using Integer Programming

Specialeforsvar ved Jonas Johansen Næsby

Titel: Solving the Kidney Exchange Problem using Integer Programming

Resume: I et byttemarked forsøger agenter at bytte indbyrdes, for at kunne forøge deres   egen nytte. Disse udvekslinger kan ske indbyrdes mellem to eller i en række   af flere agenter. Da en stor del af dem, som lider af nyresvigt, står på   ventelister med lange udsigter, for at få doneret en nyre, er der blevet   oprettet forskellige programmer indenfor nyredonation, så denne ventetid kan   forkortes. Det er denne problematik, dette speciale tager op. I disse   nyredonationsprogrammer bliver der indsamlet inkompatible donor-/modtagerpar,   som samles i en byttedatabase, hvori match mellem donor og modtager begynder.   Dette bliver gjort ud fra vigtige biologiske egenskaber, så som at matche   blodtype og human leukocyte antigen, for at kunne foretage vellykkede   donationer. At parre kompatible nyrer i nyredonationsprogrammet er et   komplekst problem, som ikke bliver mindre komplekst, ved at indføre flere   inkompatible par, og derved kan problematikken ikke løses manuelt. Inden for   dette område har matematiske formuleringer og computer videnskab fået et   stort gennembrud. Der er blevet set på to forskellige formuleringer;   "edge" og "cycle", som er algoritmer, der kan bruges til   at optimere nyredonationerne. Ved større nyredonationsproblemer kan   "branch and price" algoritmen være til stor nytte, og denne er   derfor også blevet studeret. Gennem specialeforløbet er erfaringer om   problemets kompleksitet blevet opdaget, mange tanker har være vendt, da flere og flere dele af problemstillingen skulle medregnes.

Vejleder: Salvador Pineda Morente
Censor: Jesper Larsen