Computing relaxations for the three-dimensional stable matching problem with cyclic preferences
Ágnes Cseh, Guillaume Escamocher, Luis Quesada
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.
Keywords Three-dimensional stable matching with cyclic preferences · 3dsm- cyc ·
Constraint Programming · Relaxation · Almost stable matching
