- | ||||
|
![]()
|
Branch-and-cut-and-price for the Cardinality-constrained Multi-cycle Problem in Kidney Exchange
Edward Lam(edward.lam Abstract: The establishment of kidney exchange programs has dramatically improved rates for kidney transplants by matching donors to compatible patients who would otherwise fail to receive a kidney for transplant. Rather than simply swapping kidneys between two patient-donor pairs, having multiple patient-donors pairs simultaneously donate kidneys in a cyclic manner enables all participants to receive a kidney for transplant. For practicality reasons, the cycles must be limited to short lengths. Finding these cycles can be accomplished by solving the Cardinality-constrained Multi-cycle Problem, which generalizes the Prize-collecting Assignment Problem with constraints that bound the length of the subtours. This paper presents a series of additions to existing works---new constraints, some polyhedral results, new separation algorithms and a new pricing algorithm---and integrates them in the first branch-and-cut-and-price model of the problem. The model is shown to empirically outperform the state-of-the-art by solving 149 of 160 standard benchmarks, compared to 115 by the position-indexed chain-edge formulation and 114 by the position-indexed edge formulation. Keywords: kidney exchange, subtour, cycle, separation, pricing, column generation, facet, branch-and-cut-and-price Category 1: Combinatorial Optimization (Branch and Cut Algorithms ) Category 2: Combinatorial Optimization (Graphs and Matroids ) Category 3: Applications -- Science and Engineering (Biomedical Applications ) Citation: Monash University, September 2019 Download: [PDF] Entry Submitted: 10/03/2019 Modify/Update this entry | ||
Visitors | Authors | More about us | Links | |
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
![]() |