0

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

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

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

4

1 回答 1

7

实际上有多个问题。作为 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。它有助于在一定程度上理解求解器的工作原理。有时我也无法提前猜测哪种方法是最好的。所以我的建议是尝试。通常较短的模型表现更好。幸运的是，尝试不同版本的模型并不昂贵。

于 2019-12-16T14:18:34.677 回答