Multi-objective optimization models for many-to-one matching problems

This paper is concerned with many-to-one matching problems for assigning residents to hospitals according to their preferences. The stable matching model aims at finding a stable matching, and the assignment game model involves maximizing the total utility; however, these two objectives are incompatible in general. We also focus on a situation where there are predetermined groups of residents, and they want to be matched in groups. To pursue these conflicting objectives simultaneously, we propose multi-objective optimization models for many-to-one matching problems. We firstly derive a bi-objective optimization model for maximizing the total utility and minimizing the number of blocking pairs for stability purpose. We next introduce the small-subgroup penalty to be minimized as the third objective for the purpose of matching in groups. Our optimization models are formulated as mixed-integer optimization problems, which can be solved to optimality using optimization software. The efficacy of our method is assessed through simulation experiments by comparison with the common matching algorithms, namely, deferred acceptance algorithm and Gales's top trading cycles algorithm. Our research results highlight the potential of optimization models for computing good-quality solutions to various difficult matching problems.



View Multi-objective optimization models for many-to-one matching problems