Cseh Ágnes, Escamocher Guillaume, Quesada Luis
Institute of Economics, Centre for Economic and Regional Studies, Budapest, Hungary.
Department of Mathematics, University of Bayreuth, Bayreuth, Germany.
Constraints. 2023;28(2):138-165. doi: 10.1007/s10601-023-09346-3. Epub 2023 Jun 3.
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.
约束编程已被证明是一个成功的框架，用于确定具有循环偏好的三维稳定匹配问题（3dsm-cyc）的给定实例是否有解。如果这样的实例是可满足的，约束模型甚至可以针对几个不同的目标函数计算其最优解。另一方面，对于不可满足的3dsm-cyc实例，现有的唯一输出只是一个简单的不可能声明。在本文中，我们探索了四种方法，将为3dsm-cyc设计的约束模型应用于该问题的最大松弛版本，即计算实例中修改后可导致可满足性的最小部分。我们还扩展了我们的模型，以支持实例中元素存在成本，并针对四种类型的松弛中的每一种返回总成本最低的松弛。实证结果表明，我们的松弛模型是有效的，因为在大多数情况下，与可满足版本相比，它们的开销很小。
