"Almost-stable" matchings in the Hospitals / Residents problem with Couples.

Area of Science:

• Operations Research
• Computer Science
• Algorithm Design

Background:

• The Hospitals/Residents problem with Couples (hrc) matches junior doctors to hospitals, allowing couples to submit joint preferences.
• Stable matching is not guaranteed, necessitating strategies to find 'as stable as possible' solutions.
• Minimizing blocking pairs (min bp hrc) is crucial for practical assignments.

Purpose of the Study:

• To investigate the computational complexity of finding minimum blocking pair matchings in the hrc problem.
• To develop efficient algorithms and models for the min bp hrc problem.
• To evaluate the performance of Integer Programming (IP) and Constraint Programming (CP) models for min bp hrc.

Main Methods:

• Proved the NP-hardness of the min bp hrc problem, even under restricted preference lists.
• Developed a polynomial-time algorithm for a specific restricted case (preference list length at most 2).
• Formulated the first Integer Programming (IP) and Constraint Programming (CP) models for min bp hrc.
• Conducted empirical evaluations of IP and CP models on randomly generated instances.

Main Results:

• The min bp hrc problem is NP-hard and difficult to approximate.
• A polynomial-time algorithm exists for instances with short preference lists (length ≤ 2).
• CP models significantly outperform IP models, especially with presolving (up to 8.14x faster).
• Solutions typically admit very few blocking pairs (≤ 2) in tested instances.

Conclusions:

• The hrc problem with couples is computationally challenging, but efficient solutions are possible for restricted cases.
• Constraint Programming offers a highly effective approach for solving the min bp hrc problem.
• Practical instances of min bp hrc yield highly stable matchings with minimal blocking pairs.