时间戳

首页 > 解决方案 > 从 Minizinc 中的加权约束求解中采样？

random - 从 Minizinc 中的加权约束求解中采样？

问题描述

我试图在 MiniZinc 中实现的稍微不寻常的约束求解问题：我有一个 CSP，它有一些硬约束和一个软约束，即解决方案中的关系应该具有与示例解决方案在统计上相似的配置文件。也就是说，如果输入有 5 个“红色”和 12 个“绿色”，则找到的解决方案不必正好有 5 和 12，但在统计上应该有类似的分布......但也允许罕见的解决方案，例如，没有红色。

虽然我可能有一个严格的约束，即分布必须与分布完全匹配，或者从中获取所有可能的解决方案和样本，但我更喜欢一种搜索策略，它可以得到一个在统计上可能具有相似分布的解决方案（但可以变化）。或者一种性能等效的方式来做到这一点。

使用indomain randomforassignmentannotation似乎可能有效，但据我了解，使用权重的唯一方法是使用多个值填充域以使用正确的权重填充域。

或者，我可以将其作为一个优化问题，并寻找一个最大化与所需分布的相似性的解决方案，但我更喜欢满足硬约束并从整个可能的解决方案空间中为软约束。

标签： randomconstraint-programmingminizinc

解决方案

对于大多数优化求解器来说，处理软约束可能是一个相当大的挑战。处理软约束的最佳方式通常取决于优化的应用。我认为对于您的问题，有两种方法：

  • 鉴于这个问题，您似乎实际上可以自己处理软约束。鉴于模型相对容易求解，您可以使用-a标志运行仅具有硬约束的模型，为您提供所有解决方案，然后使用自定义脚本选择解决方案的排名。（也许看看 MiniZinc 的 IPython 扩展，这将使处理解决方案变得容易）。这可能是最灵活的解决方案，并且真正由您决定如何使用软约束。我认为这种方法很适合您的问题，因为您的软约束似乎更像是解决方案的排名机制。
  • 使用实际的软约束建模并制定目标函数。软约束可以用松弛变量或布尔表达式建模。最近甚至出现了一种专门用于软约束的语言：MiniBrass。当使用软约束建模时，通常很难制定目标函数。决定哪种软约束组合比其他组合更好并不容易。这种技术仍然经常使用，因为它比第一种更有效。

在您的问题中，您指的是使用随机选择的搜索策略。我相信这实际上不会是您问题的答案（或者至少不是本身）。由于使用随机选择进行搜索，为了可满足性，只说明它找到的第一个解决方案，这可能不满足任何软约束，或者无论如何您都必须制定一个客观值。

就像一般建议一样，您可能需要考虑运行模型并将相似性限制为最小值，并查看这些是否给出了您正在寻找的答案。获得这些界限可能对寻找解决方案有很大帮助。（设置这个最小值也可能会大大提高第一种方法的性能）

推荐阅读