License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2022.16
URN: urn:nbn:de:0030-drops-166450
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16645/
Go to the corresponding LIPIcs Volume Portal

Cseh, Ágnes ; Escamocher, Guillaume ; Quesada, Luis

Computing Relaxations for the Three-Dimensional Stable Matching Problem with Cyclic Preferences

pdf-format:
LIPIcs-CP-2022-16.pdf (1 MB)

Abstract

Constraint programming has proven to be a successful framework for determining whether a given instance of the three-dimensional stable matching problem with cyclic preferences (3dsm-cyc) admits a solution. If such an instance is satisfiable, constraint models can even compute its optimal solution for several different objective functions. On the other hand, the only existing output for unsatisfiable 3dsm-cyc instances is a simple declaration of impossibility.
In this paper, we explore four ways to adapt constraint models designed for 3dsm-cyc to the maximum relaxation version of the problem, that is, the computation of the smallest part of an instance whose modification leads to satisfiability. We also extend our models to support the presence of costs on elements in the instance, and to return the relaxation with lowest total cost for each of the four types of relaxation. Empirical results reveal that our relaxation models are efficient, as in most cases, they show little overhead compared to the satisfaction version.

BibTeX - Entry

@InProceedings{cseh_et_al:LIPIcs.CP.2022.16,
  author =	{Cseh, \'{A}gnes and Escamocher, Guillaume and Quesada, Luis},
  title =	{{Computing Relaxations for the Three-Dimensional Stable Matching Problem with Cyclic Preferences}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{16:1--16:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16645},
  URN =		{urn:nbn:de:0030-drops-166450},
  doi =		{10.4230/LIPIcs.CP.2022.16},
  annote =	{Keywords: Three-dimensional stable matching with cyclic preferences, 3dsm-cyc, Constraint Programming, relaxation, almost stable matching}
}

Keywords: Three-dimensional stable matching with cyclic preferences, 3dsm-cyc, Constraint Programming, relaxation, almost stable matching
Collection: 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)
Issue Date: 2022
Date of publication: 23.07.2022
Supplementary Material: Software (Source Code): https://doi.org/10.5281/zenodo.6798122

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI