IP-MATCH

Integer Programming for Large and Complex Matching Problems (IP-MATCH) is a collaborative research project with participants from both the University of Glasgow and the University of Edinburgh. IP-MATCH is funded by two EPSRC grants ([1] and [2]) to investigate the use of integer programming techniques for solving large and complex matching problems.

What are matching problems?

Many problems in the real world involve the matching up of people, resources or items. For instance, consider finding suitable tables for groups of people arriving at a restaurant. Each group will be arriving at some particular time, wants to be sat all together, and at their own table. But the restaurant only has a limited number of tables, each with its own size, and has to take time between groups to clear the tables. The restaurant therefore has to match up each group with a table: this is a matching problem.

What are some applications of matching problems?

Matchings form a fundamental part of kidney exchange programmes. People suffering from end-stage kidney failure join such programmes with one (or more) willing kidney donors. By entering the system, the donor and patient pair join many other such pairs, and from this pool a matching algorithm determines an optimal set of donations. Without such a system, each patient would have to find a donor who is medically compatible with them. However, the system helps alleviate such troubles, and can in the process increase both the number and quality of kidney transplants.

The Kidney Exchange Game is an interactive tool to learn how computers help identify transplants within kidney exchange programmes.

Other applications include the allocation of resident (student) doctors to positions in hospitals, and the pairing of children to adoptive families.