Improving solution times for stable matching problems through preprocessing. (English) Zbl 1510.91109
Summary: We present new theory, heuristics, and algorithms for preprocessing instances of the Stable Marriage problem with Ties and Incomplete lists (SMTI) and the Hospitals/Residents problem with Ties (HRT). Instances of these problems can be preprocessed by removing from the preference lists of some agents entries such that the set of stable matchings is not affected. Removing such entries reduces the problem size, creating smaller models that can be more easily solved by integer programming (IP) solvers. The new theorems are the first to describe when preference list entries can be removed from instances of HRT when ties are present on both sides, and also extend existing results on preprocessing instances of SMTI. A number of heuristics, as well as an IP model and a graph-based algorithm, are presented to find and perform this preprocessing. Experimental results show that our new graph-based algorithm achieves a 44% reduction in the average running time to find a maximum weight stable matching in real-world instances of SMTI compared to existing preprocessing techniques, and 80% compared to not using preprocessing. We also show that, when solving MAX-HRT instances with ties on both sides, our new techniques can reduce runtimes by up to 55%.
MSC:
| 91B68 | Matching models |
Keywords:
preprocessing; stable marriage problem; hospital/residents problem; ties and incomplete listsReferences:
| [1] | Abdulkadirogˇlu, A., Pathak, P.A., Roth, A.E., Sönmez, T., 2006. Changing the Boston school-choice mechanism. NBER working paper 11965. |
| [2] | Abraham, D. J.; Levavi, A.; Manlove, D. F.; O’Malley, G., The stable roommates problem with globally-ranked pairs, Internet Math., 5, 4, 493-515 (2008) · Zbl 1194.91133 |
| [3] | Balinski, M.; Sönmez, T., A tale of two mechanisms: student placement, J. Econ. Theory, 84, 1, 73-94 (1999) · Zbl 0916.90008 |
| [4] | Biró, P.; Kiselgof, S., College admissions with stable score-limits, Central Eur. J. Oper. Res., 23, 4, 727-741 (2015) · Zbl 1339.91082 |
| [5] | Biró, P.; Klijn, F., Matching with couples: a multidisciplinary survey, Int. Game Theory Rev., 15, 2 (2013), article number 1340008 · Zbl 1274.91329 |
| [6] | Deligkas, A.; Mertzios, G. B.; Spirakis, P. G., The computational complexity of weighted greedy matching, (Proceedings of AAAI 2017: The 31st AAAI Conference on Artificial Intelligence (2017)), 466-474 |
| [7] | Delorme, M.; García, S.; Gondzio, J.; Kalcsics, J.; Manlove, D.; Pettersson, W., Mathematical models for stable matching problems with ties and incomplete lists, Eur. J. Oper. Res., 277, 2, 426-441 (2019) · Zbl 1431.91252 |
| [8] | Gale, D.; Shapley, L. S., College admissions and the stability of marriage, Am. Math. Mon., 69, 9-15 (1962) · Zbl 0109.24403 |
| [9] | Gale, D.; Sotomayor, M., Some remarks on the stable matching problem, Discr. Appl. Math., 11, 223-232 (1985) · Zbl 0596.90054 |
| [10] | Gusfield, D.; Irving, R. W., The Stable Marriage Problem: Structure and Algorithms (1989), MIT Press · Zbl 0703.68046 |
| [11] | Irving, R. W., Stable marriage and indifference, Discr. Appl. Math., 48, 261-272 (1994) · Zbl 0796.05078 |
| [12] | Irving, R. W., Matching medical students to pairs of hospitals: a new variation on a well-known theme, (Proceedings of ESA ’98: The 6th European Symposium on Algorithms, Volume 1461 of Lecture Notes in Computer Science (1998), Springer), 381-392 · Zbl 0929.90074 |
| [13] | Irving, R.W., Manlove, D.F., 2009. Finding large stable matchings. ACM J. Exp. Algorithmics 14. Section 1, article 2, 30 pages. · Zbl 1284.68670 |
| [14] | Irving, R.W., Manlove, D.F., Scott, S., 2000. The Hospitals/Residents problem with Ties. In: Proceedings of SWAT ’00: The 7th Scandinavian Workshop on Algorithm Theory, Volume 1851 of Lecture Notes in Computer Science. Springer. pp. 259-271. · Zbl 0966.91500 |
| [15] | Irving, R.W., Manlove, D.F., Scott, S., 2003. Strong stability in the Hospitals/Residents problem. In: Proceedings of STACS ’03: The 20th Annual Symposium on Theoretical Aspects of Computer Science, Volume 2607 of Lecture Notes in Computer Science. Springer. pp. 439-450. Full version available as IMS02. · Zbl 1036.90511 |
| [16] | Irving, R. W.; Manlove, D. F.; O’Malley, G., Stable marriage with ties and bounded length preference lists, J. Discr. Algorithms, 7, 2, 213-219 (2009) · Zbl 1187.68346 |
| [17] | Kavitha, T.; Mehlhorn, K.; Michail, D.; Paluch, K. E., Strongly stable matchings in time O(nm))and extension to the Hospitals-Residents problem, ACM Trans. Algorithms, 3, 2 (2007) · Zbl 1321.05207 |
| [18] | Kwanashie, A., 2015. Efficient Algorithms for Optimal Matching Problems under Preferences (Ph.D. thesis). University of Glasgow. |
| [19] | Kwanashie, A.; Manlove, D. F., An integer programming approach to the Hospitals/Residents problem with ties, (Proceedings of OR 2013: The International Conference on Operations Research (2014), Springer), 263-269 |
| [20] | Lawler, E. L., Combinatorial Optimization: Networks and Matroids (1976), Halt, Rinehart and Winston · Zbl 0413.90040 |
| [21] | Manlove, D. F., Algorithmics of Matching Under Preferences (2013), World Scientific · Zbl 1283.68018 |
| [22] | Manlove, D. F.; Irving, R. W.; Iwama, K.; Miyazaki, S.; Morita, Y., Hard variants of stable marriage, Theor. Comput. Sci., 276, 1-2, 261-279 (2002) · Zbl 1050.68171 |
| [23] | Manlove, D.F., O’Malley, G., Prosser, P., Unsworth, C., 2007. A constraint programming approach to the Hospitals/ Residents problem. In: Proceedings of CP-AI-OR ’07: The 4th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization, Volume 4510 of Lecture Notes in Computer Science. Springer. pp. 155-170. · Zbl 1214.90102 |
| [24] | Podhradský, A., 2010. Stable marriage problem algorithms. Master’s thesis, Faculty of Informatics, Masaryk University. Available from URL:http://is.muni.cz/th/172646/fi_m (accessed 25.05.2012). |
| [25] | Romero-Medina, A., Implementation of stable solutions in a restricted matching market, Rev. Econ. Design, 3, 2, 137-147 (1998) |
| [26] | Roth, A. E., Stability and polarization of interests in job matching, Econometrica, 52, 1, 47-57 (1984) · Zbl 0526.90012 |
| [27] | Roth, A. E.; Peranson, E., The redesign of the matching market for American physicians: some engineering aspects of economic design, Am. Econ. Rev., 89, 4, 748-780 (1999) |
| [28] | Roth, A.E., Sotomayor, M.A.O., 1990. Two-sided matching: a study in game-theoretic modeling and analysis. In: Volume 18 of Econometric Society Monographs. Cambridge University Press. · Zbl 0726.90003 |
| [29] | https://foundationprogramme.nhs.uk/programmes/2-year-foundation-programme/ (UKFP 2021 Applicants’ Presentation). Accessed 12 June 2020. |
| [30] | Vande Vate, J. E., Linear programming brings marital bliss, Oper. Res. Lett., 8, 3, 147-153 (1989) · Zbl 0675.90058 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
