A Quantum Annealing Approach for Solving Hard Variants of the Stable Marriage Problem

Christoph Roch; David Winderl; Claudia Linnhoff-Popien; Sebastian Feld

doi:10.1007/978-3-031-06668-9_21

A Quantum Annealing Approach for Solving Hard Variants of the Stable Marriage Problem

Christoph Roch^*, David Winderl, Claudia Linnhoff-Popien, Sebastian Feld

^*Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

1 Citation (Scopus)

43 Downloads (Pure)

Abstract

The Stable Marriage Problem (SMP) describes the problem, of finding a stable matching between two equally sized sets of elements (e.g., males and females) given an ordering of preferences for each element. A matching is stable, when there does not exist any match of a male and female which both prefer each other to their current partner under the matching. Finding such a matching of maximum cardinality, when ties and incomplete preference lists are allowed, is called MAX-SMTI and is an NP-hard variation of the SMP. In this work a Quadratic Unconstrained Binary Optimization (QUBO) formulation for MAX-SMTI is introduced and solved both with D-Wave Systems quantum annealing hardware and by their classical meta-heuristic QBSolv. Both approaches are reviewed against existing state-of-the-art approximation algorithms for MAX-SMTI. Additionally, the proposed QUBO problem can also be used to count stable matchings in SMP instances, which is proven to be a #P-complete problem. The results show, that the proposed (quantum) methods can compete with the classical ones regarding the solution quality and might be a relevant alternative, when quantum hardware scales with respect to the number of qubits and their connectivity.

Original language	English
Title of host publication	Innovations for Community Services - 22nd International Conference, I4CS 2022, Proceedings
Editors	Frank Phillipson, Gerald Eichler, Christian Erfurth, Günter Fahrnberger
Publisher	Springer
Pages	294-307
Number of pages	14
ISBN (Print)	9783031066672
DOIs	https://doi.org/10.1007/978-3-031-06668-9_21
Publication status	Published - 2022
Event	22nd International Conference on Innovations for Community Services, I4CS 2022 - Delft, Netherlands Duration: 13 Jun 2022 → 15 Jun 2022

Publication series

Name	Communications in Computer and Information Science
Volume	1585 CCIS
ISSN (Print)	1865-0929
ISSN (Electronic)	1865-0937

Conference

Conference	22nd International Conference on Innovations for Community Services, I4CS 2022
Country/Territory	Netherlands
City	Delft
Period	13/06/22 → 15/06/22

Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

D-wave systems
Heuristic
MAX-SMTI
Optimization
Quantum annealing
Stable marriage problem

Access to Document

10.1007/978-3-031-06668-9_21

978-3-031-06668-9_21Final published version, 407 KB

Cite this

Roch, C., Winderl, D., Linnhoff-Popien, C., & Feld, S. (2022). A Quantum Annealing Approach for Solving Hard Variants of the Stable Marriage Problem. In F. Phillipson, G. Eichler, C. Erfurth, & G. Fahrnberger (Eds.), Innovations for Community Services - 22nd International Conference, I4CS 2022, Proceedings (pp. 294-307). (Communications in Computer and Information Science; Vol. 1585 CCIS). Springer. https://doi.org/10.1007/978-3-031-06668-9_21

Roch, Christoph ; Winderl, David ; Linnhoff-Popien, Claudia et al. / A Quantum Annealing Approach for Solving Hard Variants of the Stable Marriage Problem. Innovations for Community Services - 22nd International Conference, I4CS 2022, Proceedings. editor / Frank Phillipson ; Gerald Eichler ; Christian Erfurth ; Günter Fahrnberger. Springer, 2022. pp. 294-307 (Communications in Computer and Information Science).

@inproceedings{89f54fdb511f42dab581b68157d7431a,

title = "A Quantum Annealing Approach for Solving Hard Variants of the Stable Marriage Problem",

abstract = "The Stable Marriage Problem (SMP) describes the problem, of finding a stable matching between two equally sized sets of elements (e.g., males and females) given an ordering of preferences for each element. A matching is stable, when there does not exist any match of a male and female which both prefer each other to their current partner under the matching. Finding such a matching of maximum cardinality, when ties and incomplete preference lists are allowed, is called MAX-SMTI and is an NP-hard variation of the SMP. In this work a Quadratic Unconstrained Binary Optimization (QUBO) formulation for MAX-SMTI is introduced and solved both with D-Wave Systems quantum annealing hardware and by their classical meta-heuristic QBSolv. Both approaches are reviewed against existing state-of-the-art approximation algorithms for MAX-SMTI. Additionally, the proposed QUBO problem can also be used to count stable matchings in SMP instances, which is proven to be a #P-complete problem. The results show, that the proposed (quantum) methods can compete with the classical ones regarding the solution quality and might be a relevant alternative, when quantum hardware scales with respect to the number of qubits and their connectivity.",

keywords = "D-wave systems, Heuristic, MAX-SMTI, Optimization, Quantum annealing, Stable marriage problem",

author = "Christoph Roch and David Winderl and Claudia Linnhoff-Popien and Sebastian Feld",

note = "Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.; 22nd International Conference on Innovations for Community Services, I4CS 2022 ; Conference date: 13-06-2022 Through 15-06-2022",

year = "2022",

doi = "10.1007/978-3-031-06668-9_21",

language = "English",

isbn = "9783031066672",

series = "Communications in Computer and Information Science",

publisher = "Springer",

pages = "294--307",

editor = "Frank Phillipson and Gerald Eichler and Christian Erfurth and G{\"u}nter Fahrnberger",

booktitle = "Innovations for Community Services - 22nd International Conference, I4CS 2022, Proceedings",

}

Roch, C, Winderl, D, Linnhoff-Popien, C & Feld, S 2022, A Quantum Annealing Approach for Solving Hard Variants of the Stable Marriage Problem. in F Phillipson, G Eichler, C Erfurth & G Fahrnberger (eds), Innovations for Community Services - 22nd International Conference, I4CS 2022, Proceedings. Communications in Computer and Information Science, vol. 1585 CCIS, Springer, pp. 294-307, 22nd International Conference on Innovations for Community Services, I4CS 2022, Delft, Netherlands, 13/06/22. https://doi.org/10.1007/978-3-031-06668-9_21

A Quantum Annealing Approach for Solving Hard Variants of the Stable Marriage Problem. / Roch, Christoph; Winderl, David; Linnhoff-Popien, Claudia et al.
Innovations for Community Services - 22nd International Conference, I4CS 2022, Proceedings. ed. / Frank Phillipson; Gerald Eichler; Christian Erfurth; Günter Fahrnberger. Springer, 2022. p. 294-307 (Communications in Computer and Information Science; Vol. 1585 CCIS).

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

T1 - A Quantum Annealing Approach for Solving Hard Variants of the Stable Marriage Problem

AU - Roch, Christoph

AU - Winderl, David

AU - Linnhoff-Popien, Claudia

AU - Feld, Sebastian

N1 - Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

PY - 2022

Y1 - 2022

N2 - The Stable Marriage Problem (SMP) describes the problem, of finding a stable matching between two equally sized sets of elements (e.g., males and females) given an ordering of preferences for each element. A matching is stable, when there does not exist any match of a male and female which both prefer each other to their current partner under the matching. Finding such a matching of maximum cardinality, when ties and incomplete preference lists are allowed, is called MAX-SMTI and is an NP-hard variation of the SMP. In this work a Quadratic Unconstrained Binary Optimization (QUBO) formulation for MAX-SMTI is introduced and solved both with D-Wave Systems quantum annealing hardware and by their classical meta-heuristic QBSolv. Both approaches are reviewed against existing state-of-the-art approximation algorithms for MAX-SMTI. Additionally, the proposed QUBO problem can also be used to count stable matchings in SMP instances, which is proven to be a #P-complete problem. The results show, that the proposed (quantum) methods can compete with the classical ones regarding the solution quality and might be a relevant alternative, when quantum hardware scales with respect to the number of qubits and their connectivity.

AB - The Stable Marriage Problem (SMP) describes the problem, of finding a stable matching between two equally sized sets of elements (e.g., males and females) given an ordering of preferences for each element. A matching is stable, when there does not exist any match of a male and female which both prefer each other to their current partner under the matching. Finding such a matching of maximum cardinality, when ties and incomplete preference lists are allowed, is called MAX-SMTI and is an NP-hard variation of the SMP. In this work a Quadratic Unconstrained Binary Optimization (QUBO) formulation for MAX-SMTI is introduced and solved both with D-Wave Systems quantum annealing hardware and by their classical meta-heuristic QBSolv. Both approaches are reviewed against existing state-of-the-art approximation algorithms for MAX-SMTI. Additionally, the proposed QUBO problem can also be used to count stable matchings in SMP instances, which is proven to be a #P-complete problem. The results show, that the proposed (quantum) methods can compete with the classical ones regarding the solution quality and might be a relevant alternative, when quantum hardware scales with respect to the number of qubits and their connectivity.

KW - D-wave systems

KW - Heuristic

KW - MAX-SMTI

KW - Optimization

KW - Quantum annealing

KW - Stable marriage problem

UR - http://www.scopus.com/inward/record.url?scp=85132938696&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-06668-9_21

DO - 10.1007/978-3-031-06668-9_21

M3 - Conference contribution

AN - SCOPUS:85132938696

SN - 9783031066672

T3 - Communications in Computer and Information Science

SP - 294

EP - 307

BT - Innovations for Community Services - 22nd International Conference, I4CS 2022, Proceedings

A2 - Phillipson, Frank

A2 - Eichler, Gerald

A2 - Erfurth, Christian

A2 - Fahrnberger, Günter

PB - Springer

T2 - 22nd International Conference on Innovations for Community Services, I4CS 2022

Y2 - 13 June 2022 through 15 June 2022

ER -

Roch C, Winderl D, Linnhoff-Popien C, Feld S. A Quantum Annealing Approach for Solving Hard Variants of the Stable Marriage Problem. In Phillipson F, Eichler G, Erfurth C, Fahrnberger G, editors, Innovations for Community Services - 22nd International Conference, I4CS 2022, Proceedings. Springer. 2022. p. 294-307. (Communications in Computer and Information Science). doi: 10.1007/978-3-031-06668-9_21