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

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.