Enhancing matching size and stability in hospitals/Residents with ties problem

Abstract

The problem of Hospitals/Residents with Ties (HRT) broadens the traditional many-to-one matching model by permitting non-strict preference rankings. In this study, we investigate the MAX-HRT variant, whose objective is to identify the largest weakly stable allocation, a problem that has been proven to be NP-hard. To cope with this computational challenge, we design a stochastic optimization scheme that initializes with a random feasible matching and progressively refines it through iterative stability adjustments. During refinement, the method strategically eliminates unstable pair configurations, giving higher priority to unfilled hospitals and unmatched residents to improve convergence efficiency. Experimental results conducted on reference datasets of substantial scale demonstrate that our algorithm reliably yields larger weakly stable matchings while significantly reducing runtime when compared with advanced adaptive-search and hospital-oriented techniques.

Keywords

matching problem heuristic MAX-HRT undominated blocking pairs stable matching perfect matching

1. Introduction

The Stable Marriage Problem (SMP) (Gale & Shapley, 1962) provides a foundational model for two-sided matching and has been widely applied to tasks such as college admissions and medical resident allocation. A practical extension, the Hospitals/Residents problem with Ties (HRT) (Irving et al., 2000; Roth, 1984), allows hospitals to accept multiple residents and permits indifference in preference lists. While this better reflects real matching markets, it also increases computational complexity. Within this framework, the MAX-HRT (Irving & Manlove, 2009; Manlove, 2008) variant seeks a weakly stable matching of maximum cardinality. Because finding such a matching is NP-hard, exact optimization is generally impractical for large-scale programs. A variety of algorithms, most notably Adaptive Search (AS) and Hospital-Proposing (HP), have been developed to address MAX-HRT (Manlove et al., 2002). Although these methods provide valuable baselines, they often exhibit long runtimes or reduced matching size when preference lists contain extensive ties or when the market involves thousands of participants. Other heuristics aim to improve stability but require heavy parameter tuning or show inconsistent performance on tie-rich instances (Irving & Manlove, 2009). To overcome these limitations, this study proposes a Heuristic Search (HS) algorithm. HS starts from a feasible random assignment and iteratively enlarges the matching while maintaining weak stability. At each step, it eliminates undominated blocking pairs and prioritizes hospitals with unfilled positions and unmatched residents, a refinement strategy absent from existing approaches. This targeted mechanism enables HS to increase the matching size and accelerate convergence simultaneously. Extensive experiments on synthetic HRT instances demonstrate that HS consistently outperforms AS, HP, and other state-of-the-art methods in terms of matching size and runtime. These results highlight the practical effectiveness of the proposed heuristic framework for large-scale MAX-HRT problems. The remainder of this paper is organized as follows. Section 2 surveys relevant research; Section 3 outlines the basic definitions and preliminary notions; Section 4 elaborates on the proposed HS algorithm and analyzes its computational properties; Section 5 presents the experimental methodology and comparison results; and Section 6 concludes the paper with remarks on future extensions.

2. Related Work

The Hospitals/Residents problem with Ties (HRT) involves two main entities: hospitals and residents. Each hospital has a limited capacity and, similar to residents, provides a preference list that may contain ties. Such indifferences give rise to three commonly recognized notions of stability (Irving et al., 2000). Among them, weak stability is considered the most practical, as a weakly stable matching always exists for any HRT instance and its size may vary (Gelain et al., 2010; Irving et al., 2008; Manlove, 2008). The MAX-HRT problem aims to identify the largest weakly stable matching; however, this optimization has been proven to be NP-hard (Manlove et al., 2002), motivating the development of more efficient approximation techniques. Early studies laid the groundwork by defining key theoretical limits and algorithmic approaches. Manlove et al. (2002) demonstrated that, for any HRT instance, the maximum stable matching can be no more than twice the size of the minimal one. In a simplified scenario where ties appear solely within hospital preference lists, Irving and Manlove (2009) introduced two heuristic-based techniques. Kwanashie and Manlove (2013) later developed a mixed-integer programming formulation that filters out infeasible pairs through the hospitals-offer and residents-apply strategy (Irving & Manlove, 2009), subsequently optimized using CPLEX. Munera et al. (2015) presented the Adaptive Search (AS) framework, converting HRT instances into SMTI representations (Iwama & Miyazaki, 2008; Iwama et al., 1999; Manlove et al., 2002) and employing a dynamic search heuristic (Gelain et al., 2013; Munera et al., 2015). Király (2013) proposed a 3/2-approximation Hospital-Proposing (HP) algorithm operating in linear time, capable of resolving ties in both hospitals’ and residents’ rankings. Recent research on the Hospitals/Residents problem with Ties (HRT) has advanced both theoretical and algorithmic perspectives, including approximation guarantees, model extensions, and preprocessing techniques for large and tie-intensive instances (Balasundaram et al., 2025; Csáji et al., 2025; Pettersson et al., 2021; Ranjan et al., 2025). In parallel, several heuristic and local-search-based approaches have been proposed to address the NP-hard MAX-HRT problem with a focus on practical scalability and convergence (Qiu, 2024). More broadly, adaptive and learning-based optimization frameworks have also been explored for complex large-scale allocation problems, highlighting the growing importance of heuristic strategies in practice (Uyen et al., 2020).

While these algorithms form important baselines, they tend to face scalability challenges when dealing with large or tie-intensive datasets and often demand significant parameter tuning. To overcome such drawbacks, this study introduces a Heuristic Search (HS) framework that aims to: (i) minimize computation time on large MAX-HRT instances by concentrating on residents that can generate blocking pairs and selecting the most promising candidates at each iteration; and (ii) expand the resulting matching by reallocating unpaired residents to hospitals still below capacity under tied preferences, all without restarting the overall matching process.

3. Preliminaries

Consider an instance $I$ of the Hospital/Residents with Ties problem (HRT), which consists of a set of residents $R = {r_{1}, \dots, r_{n}}$ and a set of hospitals $H = {h_{1}, \dots, h_{m}}$ . Each hospital $h_{j} \in H$ is associated with a positive integer capacity $c_{j} \in Z_{> 0}$ , representing the maximum number of residents it can accept. Both sides provide preference orderings over the set of acceptable partners, where indifference among options is allowed, forming ties. The collection of all admissible resident-hospital pairs is $A \subseteq R \times H$ . To describe preferences, $rank (r_{i}, h_{j})$ denotes the position of hospital $h_{j}$ in resident $r_{i}$ ’s preference list, while $rank (h_{j}, r_{i})$ refers to the position of resident $r_{i}$ in hospital $h_{j}$ ’s ordering. A smaller rank value indicates a more preferred partner. If a resident $r_{i}$ expresses indifference between two hospitals $h_{j}$ and $h_{k}$ , then $rank (r_{i}, h_{j}) = rank (r_{i}, h_{k})$ , and a similar interpretation holds for hospitals.

An assignment $M \subseteq A$ represents acceptable resident–hospital pairs. For each $(r_{i}, h_{j}) \in M$ , let $M (r_{i}) = h_{j}$ denote the hospital assigned to resident $r_{i}$ , and $M (h_{j}) = {r_{i} ∣ (r_{i}, h_{j}) \in M}$ denote the set of residents assigned to hospital $h_{j}$ . A resident $r_{i}$ is unassigned if $M (r_{i}) = \emptyset$ . Let $| M (h_{j}) |$ be the number of residents assigned to $h_{j}$ . A hospital $h_{j}$ is under-subscribed if $| M (h_{j}) | < c_{j}$ , full if $| M (h_{j}) | = c_{j}$ , and over-subscribed if $| M (h_{j}) | > c_{j}$ . A subset $M \subseteq A$ is a matching if each resident is assigned to at most one hospital and no hospital exceeds its capacity.

| M (r_{i}) | \leq 1 \forall r_{i} \in R, | M (h_{j}) | \leq c_{j} \forall h_{j} \in H .

A pair $(r_{i}, h_{j}) \in A$ is defined to block a matching $M$ if the following conditions are satisfied:

$r_{i}$ is currently unassigned, or prefers $h_{j}$ to their present assignment $M (r_{i})$ , that is, $rank (r_{i}, h_{j}) < rank (r_{i}, M (r_{i}))$ ; and

$h_{j}$ has not yet filled all of its capacity, or there exists some $r_{k} \in M (h_{j})$ such that $rank (h_{j}, r_{i}) < rank (h_{j}, r_{k})$ .

Given two blocking pairs

(r_{i}, h_{j})

and

(r_{i}, h_{k})

associated with the same resident

r_{i}

, we say that

(r_{i}, h_{j})

dominates

(r_{i}, h_{k})

from the viewpoint of

r_{i}

whenever

rank (r_{i}, h_{j}) < rank (r_{i}, h_{k})

. A blocking pair is called undominated if no other blocking pair belonging to the same resident dominates it.

A matching $M$ is referred to as weakly stable when no blocking pair exists in $M$ ; otherwise, $M$ is regarded as unstable. The size of a matching, denoted $| M |$ , represents the total number of matched pairs, and $M$ is defined as perfect if $| M | = n$ , indicating that every resident has been assigned to a hospital.

4. Proposed Algorithm

4.1. HS Algorithm

We propose a heuristic search approach, denoted by HS, designed to address the MAX-HRT optimization problem. The central concept of HS is to iteratively refine a provisional matching by resolving instability sources. Unlike methods that process all blocking pairs indiscriminately, HS concentrates on eliminating undominated blocking pairs (UBPs) at each refinement phase, thereby ensuring a more guided and computationally efficient path toward weak stability. This approach builds upon the concept of undominated blocking pairs, previously investigated in related matching frameworks, but here it is adapted into a customized search scheme specifically aimed at handling large-scale MAX-HRT instances. The overall HS framework for solving the MAX-HRT problem is outlined in Algorithm 1. The procedure begins by constructing an initial feasible matching $M$ over the set of acceptable resident–hospital pairs $(r_{i}, h_{j}) \in A$ . This initial solution then serves as the starting point for iterative refinement throughout the heuristic search process.

HS starts by generating a random feasible matching $M$ over acceptable pairs $(r_{i}, h_{j}) \in A$ and sets this as the incumbent solution $M_{b e s t}$ . All residents $r_{i} \in R$ are initially marked as active (lines 2–4), and their status is tracked throughout the procedure. Two counters, $z (r_{i})$ and $z (h_{j})$ , are initialized to zero (lines 5–7) to record the number of assignment attempts for each resident and hospital. The original preference order ${rank}^{†} (r_{i}, h_{j})$ is stored to enable restoration whenever a temporary modification to $r_{i}$ ’s list occurs during the search for an undominated blocking pair (UBP), as utilized in Algorithms 3 and 2.

The main loop iterates up to a fixed limit $m a x_i t e r$ or stops earlier if a perfect weakly stable matching is obtained. When no residents remain active, the algorithm interprets the current state as locally stable and invokes Algorithm 3 to attempt a global improvement (lines 13–20). If this call enlarges the matching, $M$ and $M_{b e s t}$ are updated accordingly and the loop continues; otherwise, or once a perfect matching is reached, the search terminates. Before each check, the current size $| M |$ is compared to $| M_{b e s t} |$ to maintain the best solution found so far.

If active residents exist, one is chosen, say $r_{i}$ , and Algorithm 2 is called to locate a hospital $h_{k}$ that forms a UBP with $r_{i}$ . If such $h_{k}$ is found, $r_{i}$ is reassigned from their current hospital $h_{j}$ to $h_{k}$ :

M \leftarrow M ∖ {(r_{i}, h_{j})} \cup {(r_{i}, h_{k})} .

Resident

r_{i}

is then marked inactive. This move can trigger two follow-up actions: (i) if

h_{k}

exceeds capacity

c_{k}

, its lowest-ranked resident

r_{w}

is removed and marked active for later reassignment; (ii) the vacancy at

h_{j}

may enable waiting residents to reapply, so all such residents

r_{l}

are reactivated and their stored rank for

h_{j}

is restored. If Algorithm 2 finds no hospital for

r_{i}

, the resident is simply marked inactive. The process repeats until the stopping condition is met, and the algorithm outputs the best matching

M_{b e s t}

Algorithm 2 identifies an UBP $(r_{i}, h_{k})$ for a given matching $M$ and a waiting list $W (r_{i})$ that stores candidate hospitals for resident $r_{i}$ . Initially, the algorithm computes a score $y (h_{t})$ for every $h_{t} \in H$ (lines 2–4). If $(r_{i}, h_{t})$ is acceptable, then $1 \leq rank (r_{i}, h_{t}) \leq m$ ; otherwise $rank (r_{i}, h_{t}) = 0$ . Since $0 \leq | M (h_{t}) | \leq c_{t}$ , it follows that

y (h_{t}) = {\begin{cases} rank (r_{i}, h_{t}) + \frac{| M (h_{t}) |}{c_{t} + 1}, & (r_{i}, h_{t}) \in A, \\ \frac{| M (h_{t}) |}{c_{t} + 1}, & (r_{i}, h_{t}) \notin A . \end{cases}

Thus,

1 \leq y (h_{t}) \leq m + \frac{c_{t}}{c_{t} + 1}

when

(r_{i}, h_{t})

is acceptable, and

0 \leq y (h_{t}) < 1

otherwise. Dividing by

c_{t} + 1

guarantees that the load-dependent component is strictly smaller than one, ensuring that the resident preference rank remains the dominant term in the score, while the hospital load acts only as a bounded tie-breaking criterion favoring less-loaded hospitals. For three acceptable pairs

(r_{i}, h_{j})

(r_{i}, h_{k})

, and

(r_{i}, h_{t})

with

rank (r_{i}, h_{k}) = rank (r_{i}, h_{j}) < rank (r_{i}, h_{t})

, the ordering

1 \leq y (h_{k}) \leq y (h_{j}) < y (h_{t})

holds whenever

| M (h_{k}) | \leq | M (h_{j}) |

. Hence minimizing

y (h_{k})

naturally selects a hospital that

r_{i}

prefers most and that currently accommodates the fewest residents.

Each iteration proceeds as follows. The algorithm first chooses a hospital $h_{l}$ minimizing $y (h_{l})$ among $r_{i}$ ’s acceptable pairs (line 7). This ensures $h_{l}$ has both the best available rank for $r_{i}$ and the smallest current load, so an under-subscribed $h_{l}$ can accept additional residents without destabilizing $M$ . Next, it checks whether $h_{l}$ ties with $M (r_{i})$ in $r_{i}$ ’s ranking; if so, the search halts with no output (lines 8–9). If $(r_{i}, h_{l})$ forms a blocking pair, then $h_{l}$ is returned as the desired UBP (lines 11–14). Otherwise, $h_{l}$ is appended to the waiting list $W (r_{i})$ and removed from $r_{i}$ ’s active preference list (lines 14–16). The set $W (r_{i})$ allows $r_{i}$ to be reactivated once some $h_{k}$ in that list becomes under-subscribed (see lines 27–30 of Algorithm 1). At each iteration, HS selects and removes an undominated blocking pair (UBP) $(r_{i}, h_{k})$ from the current unstable matching $M$ to reduce the total number of blocking pairs. Because ties may appear in both $r_{i}$ ’s and $h_{k}$ ’s preference lists, several alternative UBPs can coexist, for example $(r_{i}, h_{t})$ with $rank (r_{i}, h_{t}) = rank (r_{i}, h_{k})$ , or $(r_{u}, h_{k})$ with $rank (h_{k}, r_{u}) = rank (h_{k}, r_{i})$ . Removing different UBPs can yield different outcomes: eliminating $(r_{i}, h_{k})$ might lead to a non-perfect matching, whereas removing $(r_{i}, h_{t})$ or $(r_{u}, h_{k})$ can produce a perfect one. Thus, Algorithm 3 serves as a repair procedure within HS to escape local optima. The procedure handles two distinct cases, detailed below.

Case (i): For every unassigned resident $r_{u} \in R$ , the algorithm searches for a pair $(r_{i}, h_{k}) \in M$ where $r_{i}$ shares the same tie level as $r_{u}$ in $h_{k}$ ’s preference list. If such a pair exists and $z (r_{u}) \geq z (r_{i})$ , the algorithm replaces $r_{i}$ with $r_{u}$ to obtain a stable pair $(r_{u}, h_{k}) \in M$ . It then increments $z (r_{u})$ , marks $r_{u}$ inactive, marks $r_{i}$ reactive, and restores $h_{k}$ ’s original rank in $r_{u}$ ’s list (lines 2–9). The inequality $z (r_{u}) \geq z (r_{i})$ gives priority to an unassigned resident who has experienced at least as many hospital changes as $r_{i}$ .

Case (ii): For each under-subscribed hospital $h_{t} \in H$ , the algorithm looks for a pair $(r_{i}, h_{k}) \in M$ such that $h_{k}$ ties with $h_{t}$ in $r_{i}$ ’s original ranking. If such a pair exists and $z (h_{t}) \geq z (h_{k})$ , $h_{k}$ is replaced by $h_{t}$ , forming $(r_{i}, h_{t}) \in M$ . Next, $z (h_{t})$ is increased and $h_{t}$ ’s rank in $r_{i}$ ’s list is restored (lines 11–14). Finally, for any resident $r_{w}$ with $W (r_{w}) = h_{k}$ , all original ranks are recovered and $r_{w}$ is marked reactive (lines 15–18).

The repair procedure is defined through Cases (i) and (ii), which selectively update matched pairs under tie-consistent and counter-based conditions. Such updates are permitted only when the corresponding rank relationships and $z (\cdot)$ inequalities are satisfied, thereby restricting modifications to admissible candidates within the current matching. Through these structured reallocations, the algorithm explores alternative feasible configurations and may enlarge the matching.

In the worst case, detecting blocking pairs in HRT may require $O (n m)$ time. However, HS avoids exhaustive scanning by restricting attention to active residents, undominated blocking pairs, and dynamically maintained waiting lists. In practice, this significantly reduces the effective search space and leads to fast convergence well before the iteration limit. Nevertheless, HS does not provide worst-case optimality guarantees and has not been evaluated on extremely large instances where memory and input size dominate.

4.2. Example

This subsection demonstrates the step-by-step execution of the HS algorithm for finding a maximum stable matching in the HRT instance of Table 1.

Table 1.
An HRT Instance.

Residents’ Preferences Hospitals’ Preferences

$r_{1}$ : $h_{1}, h_{3}$ $h_{1}$ : $r_{3}$ , $(r_{2}, r_{5})$ , $(r_{1}, r_{7}, r_{8})$

$r_{2}$ : $(h_{1}, h_{4})$ $h_{2}$ : $r_{3}, r_{8}$ , $(r_{5}, r_{6})$ , $r_{7}, r_{4}$

$r_{3}$ : $h_{1}, h_{2}$ $h_{3}$ : $(r_{1}, r_{4}, r_{6})$ , $r_{5}$

$r_{4}$ : $(h_{2}, h_{3}, h_{4})$ $h_{4}$ : $r_{2}, r_{6}, r_{4}$

$r_{5}$ : $(h_{1}, h_{2}), h_{3}$

$r_{6}$ : $h_{4}, h_{2}, h_{3}$

$r_{7}$ : $h_{1}, h_{2}$

$r_{8}$ : $(h_{1}, h_{2})$

Capacities: $c_{1} = 2$ , $c_{2} = 2$ , $c_{3} = 2$ , $c_{4} = 2$

Residents’ Preferences	Hospitals’ Preferences
$r_{1}$ : $h_{1}, h_{3}$	$h_{1}$ : $r_{3}$ , $(r_{2}, r_{5})$ , $(r_{1}, r_{7}, r_{8})$
$r_{2}$ : $(h_{1}, h_{4})$	$h_{2}$ : $r_{3}, r_{8}$ , $(r_{5}, r_{6})$ , $r_{7}, r_{4}$
$r_{3}$ : $h_{1}, h_{2}$	$h_{3}$ : $(r_{1}, r_{4}, r_{6})$ , $r_{5}$
$r_{4}$ : $(h_{2}, h_{3}, h_{4})$	$h_{4}$ : $r_{2}, r_{6}, r_{4}$
$r_{5}$ : $(h_{1}, h_{2}), h_{3}$
$r_{6}$ : $h_{4}, h_{2}, h_{3}$
$r_{7}$ : $h_{1}, h_{2}$
$r_{8}$ : $(h_{1}, h_{2})$
Capacities: $c_{1} = 2$ , $c_{2} = 2$ , $c_{3} = 2$ , $c_{4} = 2$

The algorithm begins with the random initial matching $M_{0}$ = ${(r_{1}, h_{1})$ , $(r_{2}, h_{1})$ , $(r_{3}, h_{2})$ , $(r_{4}, h_{3})$ , $(r_{5}, \emptyset)$ , $(r_{6}, h_{4})$ , $(r_{7}, h_{2})$ , $(r_{8}, \emptyset)}$ . All residents are marked active, and $M_{0}$ is stored as the current best matching $M_{best}$ .

At each iteration, HS selects an active resident. If an undominated blocking pair (UBP) exists, the resident moves to the corresponding hospital; otherwise the resident becomes inactive. When all residents are inactive but the current matching is still unstable, Algorithm 3 is invoked to escape the local minimum. Table 2 highlights the principal actions.

Table 2.

Key Iterations of HS on the Instance in Table 1.

Iteration	Action	Matching Update
1-2	$r_{1}, r_{2}$ have no UBP	set inactive
3	$r_{3}$ forms $(r_{3}, h_{1})$	$r_{3}$ moves to $h_{1}$ ; $r_{1}$ reactivated
5	$r_{5}$ forms $(r_{5}, h_{2})$	$r_{5}$ assigned to $h_{2}$
8	$r_{8}$ forms $(r_{8}, h_{2})$	$r_{8}$ joins $h_{2}$ ; $r_{7}$ reactivated
9	$r_{1}$ moves to $h_{3}$	-
11	Call Alg. 3	reset $r_{1}, r_{7}, r_{8}$
12	$r_{1}$ moves to $h_{1}$	-
15	Call Alg. 3	reset $r_{1}$
16	$r_{1}$ moves to $h_{3}$	stable matching reached

The detailed logic is as follows in Table 3. Residents $r_{1}$ and $r_{2}$ are checked first, but since they form no blocking pairs they become inactive. Resident $r_{3}$ is then matched to $h_{1}$ , which displaces $r_{1}$ and reactivates $r_{1}$ . After $r_{4}$ causes no change, $r_{5}$ moves to $h_{2}$ . Residents $r_{6}$ and $r_{7}$ remain inactive until $r_{8}$ joins $h_{2}$ , which in turn reactivates $r_{7}$ . Subsequently, $r_{1}$ moves to $h_{3}$ . Two calls to Algorithm 3 reset certain residents, allowing $r_{1}$ to alternate between $h_{1}$ and $h_{3}$ . Finally, the algorithm converges to the maximum stable matching: $M_{best}$ = ${(r_{1}, h_{3}), (r_{2}, h_{4}), (r_{3}, h_{1}), (r_{4}, h_{3}), (r_{5}, h_{2}),$ $(r_{6}, h_{4}), (r_{7}, h_{1}), (r_{8}, h_{2})}$ .

Table 3.

Full Execution Trace of HS.

Iter.	Update / Action	Matching $M_{i}$
0	Initialize	$M_{0} = {(r_{1}, h_{1}), (r_{2}, h_{1}), (r_{3}, h_{2}), (r_{4}, h_{3}), (r_{5}, \emptyset), (r_{6}, h_{4}), (r_{7}, h_{2}), (r_{8}, \emptyset)}$
1	$r_{1}$ proposes $\emptyset$ , no change	$M_{1} = M_{0}$
2	$r_{2}$ proposes $\emptyset$ , no change	$M_{2} = M_{1}$
3	$r_{3}$ moves to $h_{1}$ (replacing $r_{1}$ )	$M_{3} = {(r_{1}, \emptyset), (r_{2}, h_{1}), (r_{3}, h_{1}), (r_{4}, h_{3}), (r_{5}, \emptyset), (r_{6}, h_{4}), (r_{7}, h_{2}), (r_{8}, \emptyset)}$
4	$r_{4}$ proposes $\emptyset$ , no change	$M_{4} = M_{3}$
5	$r_{5}$ moves to $h_{2}$	$M_{5} = {(r_{1}, \emptyset), (r_{2}, h_{1}), (r_{3}, h_{1}), (r_{4}, h_{3}), (r_{5}, h_{2}), (r_{6}, h_{4}), (r_{7}, h_{2}), (r_{8}, \emptyset)}$
6	$r_{6}$ proposes $\emptyset$ , no change	$M_{6} = M_{5}$
7	$r_{7}$ proposes $\emptyset$ , blocked by $h_{2}$	$M_{7} = M_{6}$
8	$r_{8}$ moves to $h_{2}$ (replacing $r_{7}$ )	$M_{8} = {(r_{1}, \emptyset), (r_{2}, h_{1}), (r_{3}, h_{1}), (r_{4}, h_{3}), (r_{5}, h_{2}), (r_{6}, h_{4}), (r_{7}, \emptyset), (r_{8}, h_{2})}$
9	$r_{1}$ moves to $h_{3}$	$M_{9} = {(r_{1}, h_{3}), (r_{2}, h_{1}), (r_{3}, h_{1}), (r_{4}, h_{3}), (r_{5}, h_{2}), (r_{6}, h_{4}), (r_{7}, \emptyset), (r_{8}, h_{2})}$
10	$r_{7}$ proposes $\emptyset$ , no change	$M_{10} = M_{9}$
11	HS calls Alg. 3: reset $r_{1}, r_{7}, r_{8}$	$M_{11} = {(r_{1}, h_{3}), (r_{2}, h_{4}), (r_{3}, h_{1}), (r_{4}, h_{3}), (r_{5}, h_{2}), (r_{6}, h_{4}), (r_{7}, \emptyset), (r_{8}, h_{2})}$
12	$r_{1}$ moves to $h_{1}$	$M_{12} = {(r_{1}, h_{1}), (r_{2}, h_{4}), (r_{3}, h_{1}), (r_{4}, h_{3}), (r_{5}, h_{2}), (r_{6}, h_{4}), (r_{7}, \emptyset), (r_{8}, h_{2})}$
13	$r_{7}$ proposes $\emptyset$ , no change	$M_{13} = M_{12}$
14	$r_{8}$ proposes $\emptyset$ , no change	$M_{14} = M_{13}$
15	HS calls Alg. 3: reset $r_{1}$	$M_{15} = {(r_{1}, \emptyset), (r_{2}, h_{4}), (r_{3}, h_{1}), (r_{4}, h_{3}), (r_{5}, h_{2}), (r_{6}, h_{4}), (r_{7}, h_{1}), (r_{8}, h_{2})}$
16	$r_{1}$ moves to $h_{3}$	$M_{16} = {(r_{1}, h_{3}), (r_{2}, h_{4}), (r_{3}, h_{1}), (r_{4}, h_{3}), (r_{5}, h_{2}), (r_{6}, h_{4}), (r_{7}, h_{1}), (r_{8}, h_{2})}$
17	$M_{16}$ stable	$M_{best} = M_{16}$

5. Experiments

In this section, we evaluate the proposed HS algorithm through a series of computational experiments. Its average runtime and matching quality are compared with those of the AS algorithm (Munera et al., 2015) and the HP algorithm (Király, 2013). All implementations were developed in MATLAB 2019a and executed on a workstation equipped with an Intel(R) Xeon(R) E5-2678 v3 CPU (2.50 GHz), 32 GB RAM, and Windows 10.¹

5.1. Datasets

To generate test instances, we adapted the random SMTI instance generator of Gent and Prosser (Gent & Prosser, 2002) to the HRT setting. Each instance is defined by five parameters: the number of residents $n$ , the number of hospitals $m$ , the incompleteness probability $p_{1}$ , the tie probability $p_{2}$ , and the hospital capacities ${c_{1}, c_{2}, \dots, c_{m}}$ . On average, a resident ranks $m (1 - p_{1})$ hospitals and a hospital ranks $n (1 - p_{1})$ residents. Because stable matchings in HRT involve only acceptable pairs, we ensured that all generated preference lists contain exclusively acceptable pairs. Table 1 illustrates a representative instance with parameters $(8, 4, 0.5, 0.5, {2, 2, 2, 2})$ , where ties in the preference lists are shown in brackets.

5.2. Comparison with AS

In this section, we present a series of experiments conducted to evaluate and compare both the average execution time and the quality of solutions obtained by our HS approach against those produced by the AS algorithm (Munera et al., 2015). The HRT instances were systematically generated by varying $p_{1}$ within the interval $[0.1, 0.8]$ and $p_{2}$ within $[0.0, 1.0]$ , with increments of 0.1.

5.2.1. Experiment 1

We generated $100$ random HRT instances for every combination of $n = 200$ , $m = 20$ , $p_{1} \in {0.1 k ∣ k = 1, \dots, 8}$ , and $p_{2} \in {0.1 k ∣ k = 0, \dots, 10}$ , yielding $8800$ instances in total. For each instance, hospital capacities were fixed at $c_{j} = n / m = 10$ $(j = 1, \dots, m)$ so that $\sum_{j = 1}^{m} c_{j} = n$ , ensuring that a perfect matching is feasible. As $p_{1}$ decreases from $0.8$ to $0.1$ , each resident ranks on average $4$ – $18$ hospitals and each hospital ranks roughly $40$ – $180$ residents. Both HS and AS were limited to $5000$ iterations. Figure 1 summarizes the outcomes.

Figure 1.

HS vs. AS for $n = 200$ , $m = 20$ and $c_{j} = n / m$ $(j = 1, 2, \dots, m)$ . (a) Percentage of perfect matchings, (b) Average number of unassigned residents , (c) Average execution time and (d) Average number of iterations

Figure 1(a) shows the proportion of perfect matchings when $p_{1} \in {0.6, 0.7, 0.8}$ and $p_{2} \in {0.1 k ∣ k = 0, \dots, 10}$ . For $p_{1} \leq 0.5$ , both algorithms consistently attain $100 %$ perfect matchings, so those cases are omitted. As $p_{1}$ grows, the proportion of perfect matchings declines for both algorithms because residents rank fewer hospitals, reducing the pool of acceptable pairs. At $p_{2} = 0$ , where no ties exist, HS and AS achieve identical matching rates, consistent with the fact that all stable matchings have equal size (Irving & Manlove, 2009). For $p_{2} \in (0, 1]$ , however, HS achieves a markedly higher proportion of perfect matchings than AS.

Figure 1(b) reports the average number of unmatched residents. When $p_{2} = 0$ , both methods again yield identical results. For $p_{2} > 0$ , HS consistently leaves fewer residents unmatched, demonstrating that it produces larger stable matchings and thus higher solution quality.

Figure 1(c) compares average execution times. As $p_{1}$ rises from $0.6$ to $0.8$ , both algorithms exhibit a slight increase in runtime, while increasing $p_{2}$ from $0.0$ to $0.9$ yields a moderate decrease. At $p_{2} = 1.0$ , HS maintains nearly the same runtime as at $p_{2} = 0.9$ , whereas AS shows a sharp reduction. Overall, HS runs about one to three orders of magnitude faster ( $\approx 12$ – $1000$ times) than AS, with runtimes ranging from $10^{- 2.5}$ to $10^{- 2.1}$ seconds versus $10^{- 1.4}$ to $10^{0.9}$ seconds for AS.

Finally, Figure 1(d) presents the average number of iterations. For $p_{2} \in (0, 1]$ , HS requires nearly constant iterations, whereas AS shows a pronounced decline as $p_{2}$ approaches $1.0$ . This explains the substantial runtime advantage of HS observed in Figure 1(c).

5.2.2. Experiment 2

This experiment follows the parameter settings of Experiment 1 but introduces heterogeneous hospital capacities to model more realistic and constrained allocation environments. For each instance, the capacity of every hospital $h_{j}$ was drawn as a random integer from the interval $[0.1 q, 0.4 q]$ , where $q$ is the number of residents ranked by $h_{j}$ . Thus, while each hospital may rank $q$ residents, it can admit only $10 %$ – $40 %$ of them, reflecting limited and uncertain resources and posing a stricter test of algorithmic performance. A total of $100$ random HRT instances was generated for each combination of $n$ , $m$ , $p_{1}$ , and $p_{2}$ .

Figure 2 summarizes the results. Across all metrics proportion of perfect matchings, number of unmatched residents, execution time, and iteration count of HS consistently outperforms AS. Specifically, HS attains larger stable matchings, completes in significantly less time, and requires fewer iterations. These outcomes underscore the robustness and scalability of HS in practical scenarios where hospital capacities are both limited and unpredictable.

Figure 2.

HS vs. AS for $n = 200$ , $m = 20$ and $c_{j} \in [0.1 q, 0.4 q]$ $(j = 1, 2, \dots, m)$ . (a) Percentage of perfect matchings, (b) Average number of unassigned residents, (c) Average execution time and (d) Average number of iterations.

5.2.3. Experiment 3

This experiment evaluates how the number of hospitals influences algorithmic performance while keeping the resident population fixed. We set $n = 300$ and varied the number of hospitals as $m \in {15, 20, 25}$ . The incompleteness parameter was fixed at $p_{1} = 0.7$ , and the tie probability $p_{2}$ ranged from $0.0$ to $1.0$ in increments of $0.1$ , thereby spanning a broad spectrum of preference structures. For each value of $m$ , every resident listed on average about $5$ , $6$ , and $8$ hospitals, respectively, while each hospital ranked roughly $90$ residents. Hospital capacities were set to $c_{j} = n / m$ for all $h_{j} \in H$ ( $j = 1, \dots, m$ ), ensuring that the total capacity matched the resident population exactly. By holding $n$ constant and varying $m$ , these instances capture different densities: when $m$ is small, residents compete for fewer positions, whereas larger $m$ yields more acceptable pairs and a richer set of potential stable matchings.

Figure 3(a) shows that HS consistently achieves a higher proportion of perfect matchings than AS across all tested $m$ and $p_{2}$ values, demonstrating superior matching capability. As depicted in Figure 3(b), HS also runs substantially faster, and the gap in execution time widens as the number of hospitals increases, confirming its scalability in larger and denser settings.

Figure 3.

HS vs. AS for $n = 300$ and $p_{1} = 0.7$ . (a) Percentage of perfect matchings, (b) Average execution time.

5.3. Comparison with HP

In this section, we conduct experiments to compare the percentage of perfect matchings and the average execution time achieved by our HS algorithm with those of the Hospital-Proposing algorithm (Király, 2013), denoted as HP, on HRT instances.

5.3.1 Experiment 4

This experiment compares the proposed HS algorithm with HP using the instance sets from Experiments 1 and 2, which respectively employ uniform hospital capacities $c_{j} = n / m$ and heterogeneous capacities $c_{j} \in [0.1 q, 0.4 q]$ . The evaluation focuses on two key metrics: the proportion of perfect matchings and average execution time.

Figures 4(a) and (c) show that HS attains a consistently higher percentage of perfect matchings than HP for all values of $p_{2}$ , with the performance gap widening as $p_{1}$ increases or capacity constraints tighten. In terms of computational efficiency, Figures 4(b) and (d) reveal that HS executes significantly faster, often by one or more orders of magnitude, and its runtime declines steadily as $p_{2}$ grows. These findings underscore the robustness of HS, which delivers both superior matching quality and markedly lower computational cost across diverse capacity settings.

Figure 4.

HS vs. HP for $n = 200$ , $m = 20$ . (a) Perfect matching $(c_{j} = n / m)$ , (b) Execution time $(c_{j} = n / m)$ , (c) Perfect matchings $(c_{j} \in [0.1 q, 0.4 q])$ and (d) Execution time $(c_{j} \in [0.1 q, 0.4 q])$ .

5.3.2 Experiment 5

This experiment evaluates the scalability of HS and HP on larger instances. We set $n = 1000$ residents and $m = 25$ hospitals, with $p_{1} \in {0.7, 0.8, 0.9}$ and $p_{2}$ varying from $0.0$ to $1.0$ in increments of $0.1$ . Under these settings, each resident ranks on average $m (1 - p_{1})$ hospitals about $8$ , $5$ , and $3$ when $p_{1} = 0.7$ , $0.8$ , and $0.9$ , respectively, while each hospital ranks roughly $300$ , $200$ , and $100$ residents. For each parameter combination, we generated $100$ random HRT instances with capacities $c_{j} = n / m$ and another $100$ instances with $c_{j}$ sampled uniformly from $[30, 55]$ . The maximum number of iterations for HS was capped at $10 000$ .

Figures 5(a) and (c) show that the proportion of perfect matchings declines as $p_{1}$ increases, reflecting the smaller set of acceptable pairs, but rises steadily with larger $p_{2}$ values because ties expand feasible matchings without introducing additional blocking pairs. Figures 5(b) and (d) report average execution time: HS exhibits only a mild runtime increase as $p_{1}$ grows and benefits from shorter runtimes when $p_{2}$ is higher, whereas HP shows nearly stable runtimes except for a noticeable drop at $p_{2} = 1.0$ .

Figure 5.

HS vs. HP for $n = 1000$ , $m = 25$ . (a) Perfect matching $c_{j} = n / m$ ( $j = 1, 2, \dots, m$ ), (b) Execution time $c_{j} = n / m$ ( $j = 1, 2, \dots, m$ ), (c) Perfect matching $c_{j} \in [30, 55]$ ( $j = 1, 2, \dots, m$ ) and (d) Execution time $c_{j} \in [30, 55]$ ( $j = 1, 2, \dots, m$ ).

Overall, HS consistently delivers more perfect matchings and significantly faster computation than HP, regardless of whether capacities are balanced ( $c_{j} = n / m$ ) or randomly distributed in $[30, 55]$ , demonstrating strong scalability and robustness on large problem instances.

5.3.3 Experiment 6

This experiment examines the impact of increasing the number of hospitals on the relative performance of HS and HP. We fixed the number of residents at $n = 1000$ and varied $m \in {50, 75, 100}$ , with $p_{1} = 0.9$ and $p_{2}$ ranging from $0.0$ to $1.0$ in increments of $0.1$ . Each hospital $h_{j}$ was assigned capacity $c_{j} = n / m$ to maintain total capacity equal to the number of residents.

Figure 6(a) shows that the proportion of perfect matchings rises steadily as $p_{2}$ increases, with HS consistently surpassing HP across all values of $m$ . For example, when $m = 100$ , HS achieves over $80 %$ perfect matchings at $p_{2} \geq 0.4$ , while HP requires much higher tie densities to approach similar performance. Figure 6(b) reports the average execution time: HS maintains stable and in many cases decreasing runtimes as $p_{2}$ grows, particularly for larger $m$ , whereas HP exhibits higher and more variable computational cost.

Figure 6.

HS vs. HP for $n = 1000$ , $m = 50, 75, 100, p_{1} = 0.9, c_{j} = n / m$ $(j = 1, 2, \dots, m)$ . (a) Percentage of perfect matchings and (b) Average execution time.

6. Conclusions

This paper introduces HS, a heuristic algorithm for the MAX-HRT problem that combines simplicity with strong empirical performance. HS begins from a randomly generated matching and iteratively eliminates undominated blocking pairs while strategically repairing incomplete matchings to enlarge the stable set. The procedure terminates with a perfect matching when possible, or otherwise returns the best stable matching found within the iteration limit.

Comprehensive experiments across diverse parameter settings demonstrate that HS consistently achieves higher rates of perfect matchings and requires significantly less computation time than established methods such as AS and HP. These results highlight both the efficiency and scalability of the proposed approach. Beyond synthetic benchmarks, HS is well suited for real-world many-to-one allocation systems in which indifference and incomplete preferences naturally arise, including hospital–resident assignment, school choice, and centralized matching platforms.

Future work could extend HS to more complex preference structures, incorporate dynamic or online settings, and explore theoretical bounds on approximation quality. Overall, the proposed algorithm provides a practical and effective framework for large-scale hospital-resident allocation problems.

Footnotes

ORCID iDs

Uyen T Nguyen

Sang X Tran

Funding

The author(s) received no financial support for the research, authorship and/or publication of this article.

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Notes

References

Balasundaram

Krishnashree

J. B.

Limaye

Nasre

(2025). Stability notions for hospital residents with sizes. In Proceedings of the 45th IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS 2025) (Vol. 360, pp. 11:1–11:18). LIPIcs.

Csáji

Király

Yokoi

(2025). A simple 1.5-approximation algorithm for a wide range of maximum-size stable matching problems. Mathematics of Operations Research. Epub ahead of print 2025. https://doi.org/10.1287/moor.2024.0725

Gale

Shapley

L. S.

(1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9–15.

Gelain

Pini

M. S.

Rossi

Venable

K. B.

Walsh

(2010). Local search for stable marriage problems with ties and incomplete lists. In Proceedings of 11th Pacific rim international conference on artificial intelligence (pp. 64–75). Daegu, Korea.

Gelain

Pini

M. S.

Rossi

Venable

K. B.

Walsh

(2013). Local search approaches in stable matching problems. Algorithms, 6(4), 591–617.

Gent

I. P.

Prosser

(2002). An empirical study of the stable marriage problem with ties and incomplete lists. In Proceedings of the 15th European conference on artificial intelligence (pp. 141–145). Lyon, France.

Irving

R. W.

Manlove

D. F.

(2009). Finding large stable matchings. Journal of Experimental Algorithmics, 14(2), 1.2–1.2:30.

Irving

R. W.

Manlove

D. F.

Scott

(2000). The hospitals/residents problem with ties. In Proceedings of the 7th scandinavian workshop on algorithm theory (pp. 259–271). Bergen, Norway.

Irving

R. W.

Manlove

D. F.

Scott

(2008). The stable marriage problem with master preference lists. Discrete Applied Mathematics, 156(15), 2959–2977.

10.

Iwama

Miyazaki

(2008). A survey of the stable marriage problem and its variants. In Proceedings of the international conference on informatics education and research for knowledge-circulating society (pp. 131–136). Washington, DC, USA.

11.

Iwama

Miyazaki

Morita

Manlove

(1999). Stable marriage with incomplete lists and ties. In Proceedings of international colloquium on automata, languages, and programming (pp. 443–452). Prague, Czech Republic.

12.

Király

(2013). Linear time local approximation algorithm for maximum stable marriage. Algorithms, 6(1), 471–484.

13.

Kwanashie

Manlove

D. F.

(2013). An integer programming approach to the hospitals/residents problem with ties. In Proceedings of the international conference on operations research (pp. 263–269). Erasmus University Rotterdam.

14.

Manlove

D. F.

(2008). The hospitals/Residents problem. In M. Y. Kao (Eds), Encyclopedia of algorithms . Boston, MA: Springer.

15.

Manlove

D. F.

Irving

R. W.

Iwama

Miyazaki

Morita

(2002). Hard variants of stable marriage. Theoretical Computer Science, 276(1-2), 261–279.

16.

Munera

Diaz

Abreu

Rossi

Saraswat

Codognet

(2015). A local search algorithm for SMTI and its extension to HRT problems. In Proceedings of the 3rd international workshop on matching under preferences (pp. 66–77). Glasgow, United Kingdom.

17.

Munera

Diaz

Abreu

Rossi

Saraswat

Codognet

(2015). Solving hard stable matching problems via local search and cooperative parallelization. In Proceedings of the Twenty-Ninth AAAI conference on artificial intelligence (pp. 1212–1218). Austin, Texas.

18.

Pettersson

Delorme

Garcia

Gondzio

Kalcsics

Manlove

(2021). Improving solution times for stable matching problems through preprocessing. Computers & Operations Research, 128, 105128.

19.

Qiu

(2024). A tie-breaking based local search algorithm for stable matching problems. preprint, arXiv:2409.10575.

20.

Ranjan

Nasre

Nimbhorkar

(2025). Optimal capacity modification for stable matchings with ties. In Proceedings of the Thirty-Fourth international joint conference on artificial intelligence (IJCAI-25) (pp. 4023–4031). International Joint Conferences on Artificial Intelligence Organization.

21.

Roth

A. E.

(1984). The evolution of the labor market for medical interns and residents: A case study in game theory. Journal of Political Economy, 92(6), 991–1016.

22.

Uyen

N. T.

Giang

N. L.

Nguyen

T. T.

Viet

H. H.

(2020). A min-conflicts algorithm for maximum stable matchings of the hospitals/residents problem with ties. In Proceedings of 2020 RIVF international conference on computing and communication technologies (pp. 1–6). Ho Chi Minh City, Vietnam.