December 3 (Thursday) 10:00-11:00, room E.118.2 (main building, 1st floor)
Zexiao Wu (Northwestern Polytechnical University, Xi’an, China)
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. The problem of finding a stable solution is already NP-hard, therefore we developed integer programming formulations for finding stable matchings with as small capacity modifications as possible. Regarding theoretical results, Nguyen and Vohra (2018) showed that a stable solution always exists after each hospital’s capacity changes by at most two and total capacity rises by at most four. We improve this by proving that a maximum total capacity change can be limited to one, and we show with a counterexample that this result is tight regarding the total capacity change. In computational experiments, we compare the performance of our so-called Exact and Cutoff formulations. Exact is slightly faster when capacities are fixed, but Cutoff is much faster when searching for the smallest repair, cutting mean running times by factors of 41 to 55. In markets with up to 30,000 doctors, it finishes 93–95% of runs within 600 seconds, compared with about 72% for Exact. We tested 96,000 synthetic and reconstructed markets, 12,830 of which have no stable matching at their original capacities. Unit expansion repairs all 12,830, and one added position is enough in 96.4% of them. Based on these experiments, we conjecture that unit expansion is sufficient for finding a stable solution, but we leave this problem open.
The talk is based on joint work with Péter Biró and Genjiu Xu.