Model-Based Approaches to Multi-attribute Diverse Matching

Jiachen Zhang; Giovanni Lo Bianco; J. Christopher Beck

doi:10.1007/978-3-031-08011-1_28

Model-Based Approaches to Multi-attribute Diverse Matching

Jiachen Zhang^*
, Giovanni Lo Bianco^*
, J. Christopher Beck^*

^*Corresponding author for this work

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

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. © 2022, Springer Nature Switzerland AG.

Original language	English
Title of host publication	Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 19th International Conference, CPAIOR 2022, Proceedings
Editors	Pierre Schaus
Publisher	Springer, Cham
Pages	424-440
Number of pages	17
ISBN (Electronic)	9783031080111
ISBN (Print)	9783031080104
DOIs	https://doi.org/10.1007/978-3-031-08011-1_28
Publication status	Published - 2022
Externally published	Yes
Event	19th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2022) - Hybrid, Los Angeles, United States Duration: 20 Jun 2022 → 23 Jun 2022 https://sites.google.com/usc.edu/cpaior-2022/home

Publication series

Name	Lecture Notes in Computer Science
Volume	13292
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	19th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2022)
Place	United States
City	Los Angeles
Period	20/06/22 → 23/06/22
Internet address	https://sites.google.com/usc.edu/cpaior-2022/home

Funding

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.

Research Keywords

Constraint programming
Digital Annealer
Diverse matching
QUBO
Specialized hardware

Access Output

10.1007/978-3-031-08011-1_28

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Zhang, J., Lo Bianco, G., & Beck, J. C. (2022). Model-Based Approaches to Multi-attribute Diverse Matching. In P. Schaus (Ed.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 19th International Conference, CPAIOR 2022, Proceedings (pp. 424-440). (Lecture Notes in Computer Science; Vol. 13292). Springer, Cham. https://doi.org/10.1007/978-3-031-08011-1_28

@inproceedings{ad50fde0c27c402a81697ed408454a35,

title = "Model-Based Approaches to Multi-attribute Diverse Matching",

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. {\textcopyright} 2022, Springer Nature Switzerland AG.",

keywords = "Constraint programming, Digital Annealer, Diverse matching, QUBO, Specialized hardware",

author = "Jiachen Zhang and \{Lo Bianco\}, Giovanni and Beck, \{J. Christopher\}",

year = "2022",

doi = "10.1007/978-3-031-08011-1\_28",

language = "English",

isbn = "9783031080104",

series = "Lecture Notes in Computer Science",

publisher = "Springer, Cham",

pages = "424--440",

editor = "Pierre Schaus",

booktitle = "Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 19th International Conference, CPAIOR 2022, Proceedings",

note = "19th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2022) ; Conference date: 20-06-2022 Through 23-06-2022",

url = "https://sites.google.com/usc.edu/cpaior-2022/home",

}

Zhang, J, Lo Bianco, G & Beck, JC 2022, Model-Based Approaches to Multi-attribute Diverse Matching. in P Schaus (ed.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 19th International Conference, CPAIOR 2022, Proceedings. Lecture Notes in Computer Science, vol. 13292, Springer, Cham, pp. 424-440, 19th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2022), Los Angeles, California, United States, 20/06/22. https://doi.org/10.1007/978-3-031-08011-1_28

Model-Based Approaches to Multi-attribute Diverse Matching. / Zhang, Jiachen; Lo Bianco, Giovanni; Beck, J. Christopher.
Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 19th International Conference, CPAIOR 2022, Proceedings. ed. / Pierre Schaus. Springer, Cham, 2022. p. 424-440 (Lecture Notes in Computer Science; Vol. 13292).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Model-Based Approaches to Multi-attribute Diverse Matching

AU - Zhang, Jiachen

AU - Lo Bianco, Giovanni

AU - Beck, J. Christopher

PY - 2022

Y1 - 2022

N2 - 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. © 2022, Springer Nature Switzerland AG.

AB - 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. © 2022, Springer Nature Switzerland AG.

KW - Constraint programming

KW - Digital Annealer

KW - Diverse matching

KW - QUBO

KW - Specialized hardware

UR - https://www.scopus.com/pages/publications/85132987393

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85132987393&origin=recordpage

U2 - 10.1007/978-3-031-08011-1_28

DO - 10.1007/978-3-031-08011-1_28

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9783031080104

T3 - Lecture Notes in Computer Science

SP - 424

EP - 440

BT - Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 19th International Conference, CPAIOR 2022, Proceedings

A2 - Schaus, Pierre

PB - Springer, Cham

T2 - 19th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2022)

Y2 - 20 June 2022 through 23 June 2022

ER -

Zhang J, Lo Bianco G, Beck JC. Model-Based Approaches to Multi-attribute Diverse Matching. In Schaus P, editor, Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 19th International Conference, CPAIOR 2022, Proceedings. Springer, Cham. 2022. p. 424-440. (Lecture Notes in Computer Science). Epub 2022 Jun 10. doi: 10.1007/978-3-031-08011-1_28

Model-Based Approaches to Multi-attribute Diverse Matching

Abstract

Publication series

Conference

Funding

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this