Capacity Modification for Matching with Couples: An Integer Programming and Computational Study

概要

We study capacity modification in the Hospitals/Residents problem with Couples, in which hospital capacities and a stable matching are jointly determined. Exact and Cutoff integer programming formulations are developed for the resulting problem. We assume that, for each couple, either both members are matched or neither is. For arbitrary strict preferences, every instance admits a stable matching after changing each hospital capacity by at most two. Total capacity increases by at most one, and this bound is tight. Under sub-responsive and sub-complete couple preferences, a stable matching exists after adding at most one position to each hospital. The total number of additions is at most the number of couples, and this bound is also tight. Computational experiments show that Exact formulations are modestly faster at fixed capacities, whereas Cutoff formulations perform substantially better in the minimum repair experiments and attain higher completion rates in markets with up to 30,000 doctors. Across 96,000 synthetic and reconstructed markets, small capacity changes restore existence whenever no stable matching exists at the original capacities.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
Capacity Modification for Matching with Couples: An Integer Programming and Computational Study

# 概要
We study capacity modification in the Hospitals/Residents problem with Couples, in which hospital capacities and a stable matching are jointly determined. Exact and Cutoff integer programming…

# 原典
https://arxiv.org/abs/2610.32793

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。