Optimization Online


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

Natsumi Shimada (08n.shimada***at***gmail.com)
Natsuki Yamazaki (pooh.amyny***at***gmail.com)
Yuichi Takano (ytakano***at***sk.tsukuba.ac.jp)

Abstract: 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.

Keywords: Many-to-one matching, Multi-objective optimization, Stable matching, Assignment game, Matching in groups

Category 1: Applications -- OR and Management Sciences (Finance and Economics )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 03/28/2019
Entry Accepted: 03/28/2019
Entry Last Modified: 04/05/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society