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.
Organisations
Publications
BirĂ³ P
(2019)
Building Kidney Exchange Programmes in Europe-An Overview of Exchange Practice and Activities.
in Transplantation
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
Caselli G
(2022)
Integer Linear Programming for the Tutor Allocation Problem: A practical case in a British University
in Expert Systems with Applications
Dell'Amico M
(2019)
Mathematical models and decomposition methods for the multiple knapsack problem
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
BirĂ³ P
(2021)
Modelling and optimisation in European Kidney Exchange Programmes
in European Journal of Operational Research
Pettersson W
(2019)
Multiobjective Integer Programming: Synergistic Parallel Approaches
in INFORMS Journal on Computing
| 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 |
| 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 |