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

DOI 情報処理学会 Web Site 参考文献2件 オープンアクセス
  • 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

この論文をさがす

抄録

<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>

収録刊行物

参考文献 (2)*注記

もっと見る

関連プロジェクト

もっと見る

詳細情報

問題の指摘

ページトップへ