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.
Publications
Krysta P
(2019)
Size Versus Truthfulness in the House Allocation Problem
in Algorithmica
Delorme M
(2022)
Improved instance generation for kidney exchange programmes
in Computers & Operations Research
Pettersson W
(2021)
Improving solution times for stable matching problems through preprocessing
in Computers & Operations Research
Cechlárová K
(2018)
Pareto optimal matchings of students to courses in the presence of prerequisites
in Discrete Optimization
Dell'Amico M
(2019)
Mathematical models and decomposition methods for the multiple knapsack problem
in European Journal of Operational Research
Biró P
(2021)
Modelling and optimisation in European Kidney Exchange Programmes
in European Journal of Operational Research
Delorme M
(2021)
Solution methods for scheduling problems with sequence-dependent deterioration and maintenance events
in European Journal of Operational Research
Delorme M
(2019)
Mathematical models for stable matching problems with ties and incomplete lists
in European Journal of Operational Research
Caselli G
(2022)
Integer Linear Programming for the Tutor Allocation Problem: A practical case in a British University
in Expert Systems with Applications
Manlove D
(2018)
How Operational Research Helps Kidney Patients in the UK
in Impact
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 | 08/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 |