Multi-objective Optimization Models for Many-to-one Matching Problems

DOI IPSJ Web Site 2 References Open Access
  • Shimada Natsumi
    Graduate School of Systems and Information Engineering, University of Tsukuba
  • Yamazaki Natsuki
    Graduate School of Systems and Information Engineering, University of Tsukuba
  • Takano Yuichi
    Faculty of Engineering, Information and Systems, University of Tsukuba

Search this article

Abstract

<p>This paper is concerned with many-to-one matching problems for assigning resident physicians (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. These two objectives however are generally incompatible. We focus on a case involving predetermined groups of residents who want to be matched in groups. To pursue these conflicting objectives simultaneously, we propose several multi-objective optimization models for many-to-one matching problems. We first derive a bi-objective optimization model for maximizing the total utility while minimizing the number of blocking pairs to promote stability. We next introduce a small-subgroup penalty, which will be minimized as the third objective for the purpose of matching in groups. Our multi-objective optimization models are formulated by means of the ε-constraint method as scalar objective mixed-integer optimization problems, which can be solved to optimality by using optimization software. The efficacy of our method is assessed through simulation experiments via comparison with the outcomes of two common matching algorithms: the deferred acceptance algorithm and Gale's top trading cycles algorithm. Our results highlight the potential of optimization models for computing good-quality solutions to a variety of difficult matching problems.</p>

Journal

References(2)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top