时间折叠：求解器在什么情况下会选择打破硬约束

Question

在什么情况下，当存在软分数较高的合适解时，求解器会选择打破硬约束。 我们创建以下解决方案： 我们使用 FIRST_FIT 和 Tabu Search 算法来构建这个解决方案，并运行它一段时间，然后我们得到一个打破了许多硬约束的结果，并且我们发现存在一个不打破任何硬约束的解决方案。

我们让求解器解释我们找到的解决方案，求解器还显示它很难突破 0。

我们想知道是什么原因导致这个问题。是运行时间造成的吗？有没有办法让求解器不尝试打破硬约束的解决方案？

Answer 1

时间折叠求解器在底层使用了本地搜索。局部搜索的特点之一是它不保证一定能达到最优解。从理论上讲，这是一个缺点 - 在实践中，对于大问题，没有已知的算法可以在现实的时间范围内提供这种保证，而本地搜索至少会给你一个像样的解决方案。

您能够手动找到更好的解决方案的事实告诉我您正在处理一个非常小的问题。如上所述，本地搜索并不详尽，有时它找不到对人类来说似乎显而易见的东西。一旦你开始缩放问题规模，你将不再能够手动找到更好的解决方案，而求解器肯定会为你提供比你自己找到的更好的解决方案。 （特别是如果您包含许多自定义约束，这就是我们的优势。）

可能还有其他原因导致求解器无法很好地解决您的问题。也许您已经引入了分数陷阱。也许您需要在动作中引入更多多样性，或者完全创建自定义动作。我无法帮助你，因为我不具备你的领域知识。