Afficher la notice abrégée

KidneyExchange.jl: A Julia package for solving the kidney exchange problem with branch-and-price

hal.structure.identifierFormulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
dc.contributor.authorARSLAN, Ayse N
hal.structure.identifierInstitut National des Sciences Appliquées - Rennes [INSA Rennes]
hal.structure.identifierInstitut de Recherche Mathématique de Rennes [IRMAR]
dc.contributor.authorOMER, Jérémy
hal.structure.identifierInstitut National des Sciences Appliquées - Rennes [INSA Rennes]
hal.structure.identifierFormulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
dc.contributor.authorYAN, Fulin
dc.date.accessioned2024-04-04T02:31:01Z
dc.date.available2024-04-04T02:31:01Z
dc.date.issued2024-03
dc.identifier.issn1867-2949
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/190281
dc.description.abstractEnThe kidney exchange problem (KEP) is an increasingly important healthcare management problem in most European and North American countries which consists of matching incompatible patient-donor pairs in a centralized system. Despite the significant progress in the exact solution of KEP instances in recent years, larger instances still pose a challenge especially when altruistic donors are taken into account. In this article, we present a branch-and-price algorithm for the exact solution of KEP in the presence of altruistic donors. This algorithm is based on a disaggregated cycle and chains formulation where subproblems are managed through graph copies. We additionally, present a branch-and-price algorithm based on the position-indexed chain-edge formulation, as well as two compact formulations. We formalize and analyze the complexity of the resulting pricing problems and identify the conditions under which they can be solved using polynomial-time algorithms. We propose several algorithmic improvements for the branch-and-price algorithms as well as for the pricing problems. We extensively test all of our implementations using a benchmark made up of different types of instances with the largest instances considered having 10000 pairs and 1000 altruists. Our numerical results show that the proposed algorithm can be up to two orders of magnitude faster compared to the state-of-the-art. All models and algorithms presented in the paper are gathered in an open-access Julia package, KidneyExchange.jl.
dc.language.isoen
dc.publisherSpringer
dc.rights.urihttp://creativecommons.org/licenses/by/
dc.subject.enKidney exchange problem
dc.subject.enColumn-generation and Branch-and-Price
dc.subject.enDecomposition algorithms
dc.subject.enJulia Language
dc.title.enKidneyExchange.jl: A Julia package for solving the kidney exchange problem with branch-and-price
dc.typeArticle de revue
dc.identifier.doi10.1007/s12532-023-00251-7
dc.subject.halMathématiques [math]/Optimisation et contrôle [math.OC]
bordeaux.journalMathematical Programming Computation
bordeaux.page151-184
bordeaux.volume16
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.issue1
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-03830810
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-03830810v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Mathematical%20Programming%20Computation&rft.date=2024-03&rft.volume=16&rft.issue=1&rft.spage=151-184&rft.epage=151-184&rft.eissn=1867-2949&rft.issn=1867-2949&rft.au=ARSLAN,%20Ayse%20N&OMER,%20J%C3%A9r%C3%A9my&YAN,%20Fulin&rft.genre=article


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée