IP-MATCH: Integer Programming for Large and Complex Matching Problems

Lead Research Organisation: University of Edinburgh
Department Name: Sch of Mathematics

Abstract

Abstracts are not currently available in GtR for all funded research. This is normally because the abstract was not required at the time of proposal submission, but may be because it included sensitive information such as personal details.
 
Description In the first year of the project we have introduced a new formulation for the stable marriage problem with incomplete ties (SMTI) and its many-to-one generalisation the hospitals/residents problem with ties (HRT). We have also developed new algorithms for preprocessing instances of SMTI with ties on both sides. In this way, we can solve large problems much more efficiently. These models and algorithms can be applied to junior doctor allocation and to children adoption.

During the first half of the second year we have developed preprocessing techniques to solve faster the problems mentioned above. During the second half we have developed algorithms to solve kidney exchange problems where different objectives are optimized hierarchically.

During the third year we have developed more efficient models to solve kidney exchange problems. These models allow us to solve larger instances, which will be helpful when considering transnational programs.
Exploitation Route One charity is interested has used one of our algorithms for decisión support in allocating children to adoptive families. We are also working with the goal that our matching models will be useful for junior doctor allocation at UK level. This is ongoing research.

The kidney exchange algorithms will be of interest to NHS Blood and Transplant to analyze the efficiency of their current policies.
Sectors Communities and Social Services/Policy,Healthcare
URL https://optimalmatching.com/IP-MATCH
 
Description Algorithms arising from this project (see https://doi.org/10.1016/j.ejor.2019.03.017 in particular) have been used by the British children's charity, Coram (https://www.coram.org.uk) to construct matchings of children to adoptive families, providing decision support for social workers when making placements.
First Year Of Impact 2017
Sector Communities and Social Services/Policy
Impact Types Societal,Economic
 
Description ENCKEP: European Network for Collaboration on Kidney Exchange Programmes (COST Action CA15210)
Amount € 720,000 (EUR)
Funding ID CA15210 
Organisation European Commission 
Sector Public
Country European Union (EU)
Start 09/2016 
End 03/2021
 
Description KEP-SOFT: Software for Transnational Kidney Exchange Programmes
Amount € 124,200 (EUR)
Funding ID IG15210 
Organisation European Cooperation in Science and Technology (COST) 
Sector Public
Country Belgium
Start 11/2021 
End 10/2022
 
Title A new matheuristic and improved instance generation for kidney exchange programmes 
Description This repository contains a number of kidney exchange instances as used in http://www.optimization-online.org/DB_HTML/2021/06/8432.html These are stored in directories, where each directory corresponds to one particular generator configuration as per the published paper. Each directory contains 640 instances, and the configuration file used to generate these is contained within a config.json file also within said directory. The format for these files is explained at https://kep-solver.readthedocs.io/en/latest/source/formats.html#input, and the exact configuration used to generate each set of instances (besides size) is given in a config.json file in each directory. 
Type Of Material Database/Collection of data 
Year Produced 2021 
Provided To Others? Yes  
Impact None known yet 
URL http://researchdata.gla.ac.uk/id/eprint/1160
 
Title Improved instance generation for kidney exchange programmes 
Description Kidney exchange instances This archive contains a large number of kidney exchange instances. Each folder contains 640 instances, each of which is a JSON file as described at https://kep-solver.readthedocs.io/en/latest/source/formats.html#input Each folder corresponds to a particular experimental setup as described in the preprint paper available at http://www.optimization-online.org/DB_HTML/2021/06/8432.html 
Type Of Material Database/Collection of data 
Year Produced 2021 
Provided To Others? Yes  
Impact None known yet 
URL http://researchdata.gla.ac.uk/id/eprint/1213
 
Description ENCKEP: European Network for Collaboration on Kidney Exchange Programmes (COST Action CA15210) 
Organisation Erasmus University Rotterdam
Department Institute of Health Policy & Management (iBMG)
Country Netherlands 
Sector Academic/University 
PI Contribution Drafting the proposal for the COST Action. Vice-Chair to April 2018 and Chair from May 2018.
Collaborator Contribution Drafting the proposal for the COST Action. Vice-Chair to April 2018 and Chair from May 2018.
Impact Memorandum of Understanding published at https://e-services.cost.eu/files/domain_files/CA/Action_CA15210/mou/CA15210-e.pdf Publications listed at https://www.enckep-cost.eu/category/resources/publications Outputs / impacts listed in the final achievement report: https://e-services.cost.eu/files/domain_files/CA/Action_CA15210/final_achievement_report/final_achievement_report-CA15210.pdf
Start Year 2016
 
Description ENCKEP: European Network for Collaboration on Kidney Exchange Programmes (COST Action CA15210) 
Organisation INESC TEC
Country Portugal 
Sector Private 
PI Contribution Drafting the proposal for the COST Action. Vice-Chair to April 2018 and Chair from May 2018.
Collaborator Contribution Drafting the proposal for the COST Action. Vice-Chair to April 2018 and Chair from May 2018.
Impact Memorandum of Understanding published at https://e-services.cost.eu/files/domain_files/CA/Action_CA15210/mou/CA15210-e.pdf Publications listed at https://www.enckep-cost.eu/category/resources/publications Outputs / impacts listed in the final achievement report: https://e-services.cost.eu/files/domain_files/CA/Action_CA15210/final_achievement_report/final_achievement_report-CA15210.pdf
Start Year 2016