Academic Bibliography

 Search 200 years of publications by Ghent University researchers.
Advanced search
1 file | 4.26 MB
Add to list
  1. Search results
  2. Solving stable matching problems usin...

Solving stable matching problems using answer set programming

Sofie De Clercq (UGent) , Steven Schockaert, Martine De Cock (UGent) and Ann Nowé
(2016) THEORY AND PRACTICE OF LOGIC PROGRAMMING. 16(3). p.247-268
Author
Organization
Abstract
Since the introduction of the stable marriage problem (SMP) by Gale and Shapley (1962), several variants and extensions have been investigated. While this variety is useful to widen the application potential, each variant requires a new algorithm for finding the stable matchings. To address this issue, we propose an encoding of the SMP using answer set programming (ASP), which can straightforwardly be adapted and extended to suit the needs of specific applications. The use of ASP also means that we can take advantage of highly efficient off-the-shelf solvers. To illustrate the flexibility of our approach, we show how our ASP encoding naturally allows us to select optimal stable matchings, i.e. matchings that are optimal according to some user-specified criterion. To the best of our knowledge, our encoding offers the first exact implementation to find sex-equal, minimum regret, egalitarian or maximum cardinality stable matchings for SMP instances in which individuals may designate unacceptable partners and ties between preferences are allowed.
Keywords
Answer set programming, Logic rules, Stable marriage problem, Optimal stable matchings, KIDNEY EXCHANGE, MARRIAGE, ALGORITHMS

Downloads

  • Download
    SMP with ASP cwi.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 4.26 MB

Citation

Please use this url to cite or link to this publication:

MLA
De Clercq, Sofie, et al. “Solving Stable Matching Problems Using Answer Set Programming.” THEORY AND PRACTICE OF LOGIC PROGRAMMING, vol. 16, no. 3, 2016, pp. 247–68, doi:10.1017/S147106841600003X.
APA
De Clercq, S., Schockaert, S., De Cock, M., & Nowé, A. (2016). Solving stable matching problems using answer set programming. THEORY AND PRACTICE OF LOGIC PROGRAMMING, 16(3), 247–268. https://doi.org/10.1017/S147106841600003X
Chicago author-date
De Clercq, Sofie, Steven Schockaert, Martine De Cock, and Ann Nowé. 2016. “Solving Stable Matching Problems Using Answer Set Programming.” THEORY AND PRACTICE OF LOGIC PROGRAMMING 16 (3): 247–68. https://doi.org/10.1017/S147106841600003X.
Chicago author-date (all authors)
De Clercq, Sofie, Steven Schockaert, Martine De Cock, and Ann Nowé. 2016. “Solving Stable Matching Problems Using Answer Set Programming.” THEORY AND PRACTICE OF LOGIC PROGRAMMING 16 (3): 247–268. doi:10.1017/S147106841600003X.
Vancouver
1.
De Clercq S, Schockaert S, De Cock M, Nowé A. Solving stable matching problems using answer set programming. THEORY AND PRACTICE OF LOGIC PROGRAMMING. 2016;16(3):247–68.
IEEE
[1]
S. De Clercq, S. Schockaert, M. De Cock, and A. Nowé, “Solving stable matching problems using answer set programming,” THEORY AND PRACTICE OF LOGIC PROGRAMMING, vol. 16, no. 3, pp. 247–268, 2016.
@article{7171798,
  abstract     = {{Since the introduction of the stable marriage problem (SMP) by Gale and Shapley (1962), several variants and extensions have been investigated. While this variety is useful to widen the application potential, each variant requires a new algorithm for finding the stable matchings. To address this issue, we propose an encoding of the SMP using answer set programming (ASP), which can straightforwardly be adapted and extended to suit the needs of specific applications. The use of ASP also means that we can take advantage of highly efficient off-the-shelf solvers. To illustrate the flexibility of our approach, we show how our ASP encoding naturally allows us to select optimal stable matchings, i.e. matchings that are optimal according to some user-specified criterion. To the best of our knowledge, our encoding offers the first exact implementation to find sex-equal, minimum regret, egalitarian or maximum cardinality stable matchings for SMP instances in which individuals may designate unacceptable partners and ties between preferences are allowed.}},
  author       = {{De Clercq, Sofie and Schockaert, Steven and De Cock, Martine and Nowé, Ann}},
  issn         = {{1471-0684}},
  journal      = {{THEORY AND PRACTICE OF LOGIC PROGRAMMING}},
  keywords     = {{Answer set programming,Logic rules,Stable marriage problem,Optimal stable matchings,KIDNEY EXCHANGE,MARRIAGE,ALGORITHMS}},
  language     = {{eng}},
  location     = {{Prague, Czech Republic}},
  number       = {{3}},
  pages        = {{247--268}},
  title        = {{Solving stable matching problems using answer set programming}},
  url          = {{http://doi.org/10.1017/S147106841600003X}},
  volume       = {{16}},
  year         = {{2016}},
}
Altmetric
View in Altmetric
Web of Science
Times cited: