Maximum Expected Value Partial Failure Path Problem

TL;DRAbstract

Mathematical programming formulations are developed for a problem motivated by determining chains of organ-donation exchange pairs in a compatibility graph. The objective is to maximize the expected value where pairs are known to fail with given probabilities. Historically this NP-hard problem has been solved heuristically or exactly only for limited path lengths. Although the problem appears highly nonlinear, we formulate it as a mixed-integer linear program (MILP). A computationally tractable layered formulation that approximately solves larger instances is also presented.

Chat with Paper

AI Agents for this Paper