Matching Consider patient that needs a kidney transplant. A conventional kidney
transplant occurs when the kidney of a deceased donor is used in the transplant. Conventional kidney transplants have a long waiting period of up to 10 years, which is clearly not ideal'. Alternatively, if the patient has a compatible living donor, then a transplant can occur immediately. Unfortunately, while often patients have a significant other willing to donate their kidney, this donor is incompatible with the patient. In this case, a paired kidney exchange can occur? given two cou- ples, each couple conformed by an incompatible donor-recipient pair such that the
donors of each couple are compatible with the recipients of the other couples, a
"kidney exchange" can occur. a) Suppose that there is a list of m donor-recipient couples. Moreover, let ci; denote the compatibility index of the donor of couple i and the recipient of couple j (larger numbers are better). Formulate a problem that finds the optimal way to perform kidney exchanges, such that the overall compatibility
across the population is maximized. b) If, additionally, there are altruistic donors, it is possible to create kidney donor chains. Formulate an optimization problem that maximizes the overall
compatibility using kidney chains.