Abstract
Bipartite b-matching is a classical model that is used for utility maximization in various applications such as marketing, healthcare, education, and general resource allocation. Multi-attribute diverse weighted bipartite b-matching (MDWBM) balances the quality of the matching with its diversity. The recent paper by Ahmadi et al. (2020) introduced the MDWBM but presented an incorrect mixed integer quadra-tic program (MIQP) and a flawed local exchange algorithm. In this work, we develop two constraint programming (CP) models, a binary quadratic programming (BQP) model, and a quadratic unconstrained binary optimization (QUBO) model for both the unconstrained and constrained MDWBM. A thorough empirical evaluation using commercial solvers and specialized QUBO hardware shows that the hardware-based QUBO approach dominates, finding best-known solutions on all tested instances up to an order of magnitude faster than the other approaches. CP is able to achieve better solutions than BQP on unconstrained problems but under-performs on constrained problems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The negative submodular diversity is equivalent to the supermodular similarity.
- 2.
- 3.
- 4.
All experiments were conducted on the Digital Annealer environment prepared exclusively for the research at the University of Toronto.
References
Ahmadi, S., Ahmed, F., Dickerson, J.P., Fuge, M., Khuller, S.: An algorithm for multi-attribute diverse matching. In: Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), pp. 3–9. AAAI Press (2020)
Ahmed, F., Dickerson, J.P., Fuge, M.: Diverse weighted bipartite b-matching. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), pp. 35–41. AAAI Press (2017)
Aramon, M., Rosenberg, G., Valiante, E., Miyazawa, T., Tamura, H., Katzgraber, H.G.: Physics-inspired optimization for quadratic unconstrained problems using a digital annealer. Front. Phys. 7, 48 (2019)
Bagherbeik, M., Ashtari, P., Mousavi, S.F., Kanda, K., Tamura, H., Sheikholeslami, A.: A permutational Boltzmann machine with parallel tempering for solving combinatorial optimization problems. In: Bäck, T., Preuss, M., Deutz, A., Wang, H., Doerr, C., Emmerich, M., Trautmann, H. (eds.) PPSN 2020. LNCS, vol. 12269, pp. 317–331. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-58112-1_22
Benabbou, N., Chakraborty, M., Ho, X.V., Sliwinski, J., Zick, Y.: Diversity constraints in public housing allocation. In: 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018 (2018)
Bertsimas, D., Papalexopoulos, T., Trichakis, N., Wang, Y., Hirose, R., Vagefi, P.A.: Balancing efficiency and fairness in liver transplant access: tradeoff curves for the assessment of organ distribution policies. Transplantation 104(5), 981–987 (2020)
Carbonell, J., Goldstein, J.: The use of MMR, diversity-based reranking for reordering documents and producing summaries. In: Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 335–336 (1998)
Chen, C., Zheng, L., Srinivasan, V., Thomo, A., Wu, K., Sukow, A.: Conflict-aware weighted bipartite b-matching and its application to e-commerce. IEEE Trans. Knowl. Data Eng. 28(6), 1475–1488 (2016)
Coffrin, C., Nagarajan, H., Bent, R.: Evaluating ising processing units with integer programming. In: Rousseau, L.-M., Stergiou, K. (eds.) CPAIOR 2019. LNCS, vol. 11494, pp. 163–181. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-19212-9_11
Cohen, E., Senderovich, A., Beck, J.C.: An ising framework for constrained clustering on special purpose hardware. In: Hebrard, E., Musliu, N. (eds.) CPAIOR 2020. LNCS, vol. 12296, pp. 130–147. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-58942-4_9
D-Wave System Inc.: D-wave tabu (2021). https://docs.ocean.dwavesys.com/projects/tabu/en/latest/, Accessed 21 July 2021
Dabiri, K., Malekmohammadi, M., Sheikholeslami, A., Tamura, H.: Replica exchange MCMC hardware with automatic temperature selection and parallel trial. IEEE Trans. Parallel Distrib. Syst. 31(7), 1681–1692 (2020)
Dunning, I., Gupta, S., Silberholz, J.: What works best when? A systematic evaluation of heuristics for Max-Cut and QUBO. INFORMS J. Comput. 30(3), 608–624 (2018)
Fazliu, Z.L., Chiasserini, C.F., Malandrino, F., Nordio, A.: Graph-based model for beam management in mmwave vehicular networks. In: Proceedings of the Twenty-First International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, pp. 363–367 (2020)
Fern, X.Z., Brodley, C.E., et al.: Cluster ensembles for high dimensional clustering: an empirical study. Technical Report CS06-30-02, Oregon State University (2006)
Fujitsu Limited: The third generation of the digital annealer (2021). https://www.fujitsu.com/jp/group/labs/en/documents/about/resources/tech/techintro/3rd-g-da_en.pdf, Accessed 20 Aug 2021
de Givry, S., Schiex, T., Schutt, A., Simonis, H.: Modelling the conference paper assignment problem. In: 19th Workshop on Constraint Modeling and Reformulation, ModRef-20 (2020)
Kadıoğlu, S., Kleynhans, B., Wang, X.: Optimized item selection to boost exploration for recommender systems. In: Stuckey, P.J. (ed.) CPAIOR 2021. LNCS, vol. 12735, pp. 427–445. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-78230-6_27
Karimzadehgan, M., Zhai, C.: Constrained multi-aspect expertise matching for committee review assignment. In: Proceedings of the 18th ACM conference on Information and knowledge management, pp. 1697–1700 (2009)
Kochenberger, G., et al.: The unconstrained binary quadratic programming problem: a survey. J. Comb. Optim. 28(1), 58–81 (2014). https://doi.org/10.1007/s10878-014-9734-0
Kulesza, A., Taskar, B.: Determinantal point processes for machine learning. arXiv preprint arXiv:1207.6083 (2012)
Matsubara, S., et al.: Digital annealer for high-speed solving of combinatorial optimization problems and its applications. In: 2020 25th Asia and South Pacific Design Automation Conference, ASP-DAC, pp. 667–672. IEEE (2020)
Mohseni, M., et al.: Commercialize quantum technologies in five years. Nature News 543(7644), 171 (2017)
Palubeckis, G.: Multistart tabu search strategies for the unconstrained binary quadratic optimization problem. Ann. Oper. Res. 131(1), 259–282 (2004)
Rosenberg, G., Haghnegahdar, P., Goddard, P., Carr, P., Wu, K., De Prado, M.L.: Solving the optimal trading trajectory problem using a quantum annealer. IEEE J. Sel. Top. Signal Process. 10(6), 1053–1060 (2016)
Tran, T.T., et al.: Explorations of quantum-classical approaches to scheduling a mars lander activity problem. In: Workshops at the Thirtieth AAAI Conference on Artificial Intelligence (2016)
Zhang, J., Lo Bianco, G., Beck, J.C.: MDWBM Instances (2021). https://github.com/JasonZhangjc/mdwbm-instances, Accessed 11 Feb 2022
Acknowledgement
The authors would like to thank Fujitsu Ltd. and Fujitsu Consulting (Canada) Inc. for providing financial support and access to the Digital Annealer at the University of Toronto. Partial funding for this work was provided by Fujitsu Ltd. and the Natural Sciences and Engineering Research Council of Canada.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Zhang, J., Lo Bianco, G., Beck, J.C. (2022). Model-Based Approaches to Multi-attribute Diverse Matching. In: Schaus, P. (eds) Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2022. Lecture Notes in Computer Science, vol 13292. Springer, Cham. https://doi.org/10.1007/978-3-031-08011-1_28
Download citation
DOI: https://doi.org/10.1007/978-3-031-08011-1_28
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-08010-4
Online ISBN: 978-3-031-08011-1
eBook Packages: Computer ScienceComputer Science (R0)