CP Optimizer 与其他约束规划求解器相比如何/

Question

In 最近使用 CP Optimizer（CPLEX 约束编程求解器）解决了几个调度项目，并且能够使用它获得一些非常好的结果。但是，与Cplex相比，CP Optimizer对我来说仍然是一个大黑箱。通常可以用不同的方式来表述一个问题，而小的变化可能会导致性能的巨大差异。在我看来，缺乏文档和示例，这使得它很难使用。也没有所有约束编程求解器共享的标准化约束集，甚至没有一种导出格式可以让我解决 CP Optimizer 和替代求解器（Xpress Kalis 或像 Gecode 这样的开源替代方案）陈述的问题， 例如）。

虽然我知道商业 MIP 求解器比开源替代方案强大得多，但我还没有看到任何比较不同约束编程求解器的研究。

我想知道其他约束编程求解器与 CP Optimizer 相比如何。我对调度应用程序特别感兴趣，CP Optimizer 对此具有一组特殊的变量（间隔和序列）和许多有用的约束（优先级、无重叠等）。我不介意使用整数变量代替区间变量并以更复杂的方式制定约束，但我想知道是否有任何开源约束编程求解器可以与商业求解器竞争。

Answer 1

其实有很多问题。作为 CP Optimizer 开发人员，我尝试回答一些与 CP Optimizer 直接相关的问题。

在 CP Optimizer 之前，有 ILOG Solver 和 ILOG Scheduler。调度问题由调度程序中的“活动”建模，活动由几个整数变量组成。Scheduler 取得了成功，但越来越难跟上客户的需求。工业问题通常包含某种替代方案、替代资源、可选目标等。很难使用活动对它们进行建模（例如，未执行活动的长度是多少？）。解决这些模型也很困难。

出于这个原因，ILOG 调度程序已停止使用。相反，我们创建了带有可选区间变量的 CP Optimizer。我们为调度问题设计了全新的语言，我们认为可以用更简单的方式描述调度问题。它为求解器提供了更有效地解决问题所需的信息。如果你想了解更多，我推荐以下论文：

• Laborie, Rogerie：有条件时间间隔的推理
• Laborie、Rogerie、Shaw、Vilim：有条件时间间隔的推理，第二部分：资源的代数模型

因此与其他求解器相比，调度语言大多不同。如果您来自不同的求解器，则必须从头开始编写（调度）模型。但我们相信这是值得的，因为替代方案是“类似调度程序”的模型。这就是没有通用导出格式的原因。

关于 CP Optimizer 的效率。是的，没有直接的比较。恐怕你必须自己试验。由于语言不同，请两次编写您的模型。如果我只能给出一个为什么值得尝试的理由，那么例如，CP Optimizer 能够解决数十年来一直存在的调度问题：

• Vilim、Laborie、Shaw：针对基于约束的调度的故障导向搜索

最后关于模型的微小变化会对性能产生巨大影响的事实。是的，这是常态。而且我不认为只有 CP Optimizer 会受到影响。它有助于在某种程度上理解求解器的工作原理。有时我也无法提前猜测什么方法是最好的。所以我的建议是尝试。通常较短的模型表现更好。幸运的是，尝试不同版本的模型并没有那么昂贵。