You are not logged in.

On the kidney exchange problem: cardinality constrained cycle and chain problems on directed graphs: a survey of integer programming approaches

Mak-Hau, Vicky 2017, On the kidney exchange problem: cardinality constrained cycle and chain problems on directed graphs: a survey of integer programming approaches, Journal of combinatorial optimization, vol. 33, no. 1, pp. 35-59, doi: 10.1007/s10878-015-9932-4.

Attached Files
Name Description MIMEType Size Downloads

Title On the kidney exchange problem: cardinality constrained cycle and chain problems on directed graphs: a survey of integer programming approaches
Author(s) Mak-Hau, VickyORCID iD for Mak-Hau, Vicky orcid.org/0000-0002-9306-5780
Journal name Journal of combinatorial optimization
Volume number 33
Issue number 1
Start page 35
End page 59
Total pages 25
Publisher Springer
Place of publication Berlin, Germany
Publication date 2017-01
ISSN 1382-6905
1573-2886
Keyword(s) Kidney exchange
Integer programming
Combinational optimization
Healthcare
Summary The Kidney Exchange Problem (KEP) is a combinatorial optimization problem and has attracted the attention from the community of integer programming/combinatorial optimisation in the past few years. Defined on a directed graph, the KEP has two variations: one concerns cycles only, and the other, cycles as well as chains on the same graph. We call the former a Cardinality Constrained Multi-cycle Problem (CCMcP) and the latter a Cardinality Constrained Cycles and Chains Problem (CCCCP). The cardinality for cycles is restricted in both CCMcP and CCCCP. As for chains, some studies in the literature considered cardinality restrictions, whereas others did not. The CCMcP can be viewed as an Asymmetric Travelling Salesman Problem that does allow subtours, however these subtours are constrained by cardinality, and that it is not necessary to visit all vertices. In existing literature of the KEP, the cardinality constraint for cycles is usually considered to be small (to the best of our knowledge, no more than six). In a CCCCP, each vertex on the directed graph can be included in at most one cycle or chain, but not both. The CCMcP and the CCCCP are interesting and challenging combinatorial optimization problems in their own rights, particularly due to their similarities to some travelling salesman- and vehicle routing-family of problems. In this paper, our main focus is to review the existing mathematical programming models and solution methods in the literature, analyse the performance of these models, and identify future research directions. Further, we propose a polynomial-sized and an exponential-sized mixed-integer linear programming model, discuss a number of stronger constraints for cardinality-infeasible-cycle elimination for the latter, and present some preliminary numerical results.
Language eng
DOI 10.1007/s10878-015-9932-4
Field of Research 0101 Pure Mathematics
0102 Applied Mathematics
0103 Numerical And Computational Mathematics
010104 Combinatorics and Discrete Mathematics (excl Physical Combinatorics)
Socio Economic Objective 920119 Urogenital System and Disorders
HERDC Research category C1 Refereed article in a scholarly journal
ERA Research output type C Journal article
Copyright notice ©2015, Springer
Persistent URL http://hdl.handle.net/10536/DRO/DU:30082325

Document type: Journal Article
Collection: School of Information Technology
Connect to link resolver
 
Unless expressly stated otherwise, the copyright for items in DRO is owned by the author, with all rights reserved.

Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in TR Web of Science
Scopus Citation Count Cited 0 times in Scopus
Google Scholar Search Google Scholar
Access Statistics: 56 Abstract Views, 2 File Downloads  -  Detailed Statistics
Created: Fri, 18 Mar 2016, 13:09:11 EST

Every reasonable effort has been made to ensure that permission has been obtained for items included in DRO. If you believe that your rights have been infringed by this repository, please contact drosupport@deakin.edu.au.