Optimization Online


A Comparative Study of Stability Representations for Solving Many-to-One Matching Problems with Ties and Incomplete Lists via Integer Optimization

Pitchaya Wiratchotisatian(pwiratchotisatia***at***wpi.edu)
Andrew C Trapp(atrapp***at***wpi.edu)
Hoda Atef Yekta(atefyehx***at***jmu.edu)

Abstract: We consider integer optimization models for finding stable solutions to many-to-one matching problems with incomplete preference lists and ties. While traditional algorithmic approaches for the stable many-to-one matching problem, such as the deferred acceptance algorithm, offer efficient performance for the strict problem setting, adaptation to alternative settings they often require careful customization. However, optimization-based approaches are free from the need to create customized algorithms for each unique context, and can readily accommodate such extensions as (incomplete) preference lists with ties; alternative and non-traditional objective functions; and side constraints - including those that ensure stable matching outcomes. We explore the flexibility of optimization-based approaches in several ways. First, we introduce four new constraint sets that prevent justified envy, and a new system of constraints that prevents waste; taken together, they jointly ensure stable matching outcomes. Second, we create two algorithms to accelerate the generation of our proposed constraints. Third, we construct aggregate objective functions to reflect multiple hierarchical emphases by imposing a strict lexicographical order on the individual components. Fourth, we conduct comprehensive experiments to study the computational performance of our proposed optimization models and compare them with models from the extant literature under a variety of problem attributes. Our experiments reveal the circumstances under which each stability representation excels in terms of optimality criteria and computational efficiency on a variety of real and synthetic datasets. One such setting where our proposed stability representations excel includes the important context of when sufficient seats exist for applicants, such as school choice problems and hospital-residency matching.

Keywords: Many-to-One Matching, Stable Allocation, Integer Optimization, Lexicographic Optimization, Computational Study

Category 1: Applications -- OR and Management Sciences


Download: [PDF]

Entry Submitted: 02/26/2021
Entry Accepted: 02/26/2021
Entry Last Modified: 02/26/2021

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