CP优化器与其他约束编程求解器比较如何？

Question

In最近解决了几个使用CP优化器( CPLEX约束编程解决程序)的调度项目，并且能够获得一些非常好的结果。然而，与Cplex相比，CP优化器对我来说仍然是一个大的黑匣子。通常情况下，以不同的方式提出问题是可能的，而小的变化会在性能上造成巨大的差异。在我看来，由于缺乏文档和示例，因此很难使用它。也没有所有约束编程解决程序共享的标准化约束集，甚至连允许我使用CP Optimizer和替代解决器(例如Xpress Kalis或像Gecode这样的开源替代程序)都能解决的问题的导出格式都没有。

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

我想知道其他约束编程解决程序与CP优化器相比如何。我特别感兴趣的是调度应用程序，对于这些应用程序，CP优化器有一组特殊的变量(区间和序列)和许多有用的约束(优先级、无重叠等)。我不介意使用整数变量而不是区间变量，并以更复杂的方式构造约束，但我想知道是否有任何开源约束编程解决程序可以与商业程序竞争。

Answer 1

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

在CP优化器之前，有ILOG求解器和ILOG调度器。调度问题采用Scheduler中的活动建模，一个由多个整数变量组成的活动。调度程序是一个成功，但它越来越难跟上客户的需求。工业问题通常包括某种替代食谱、替代资源、可选目标等。很难用活动来模拟它们(例如，什么是未完成的活动的长度？)。解决这些模型也很困难。

因此，ILOG计划程序被终止。相反，我们创建了带有可选区间变量的CP优化器。我们为调度问题设计了全新的语言，我们认为它允许以更简单的方式描述调度问题。并给出了求解者所需的信息，以更有效地解决问题。如果你想知道更多，我推荐以下文件：

Time-intervals

• Laborie，
• Laborie，
  • Laborie:用条件
  • Rogerie，Shaw，Vilim进行推理:带条件时间间隔的推理，第二部分:资源

  的代数模型

因此，与其他求解器相比，调度语言有很大的不同。如果您来自不同的求解者，则必须从头开始编写(调度)模型。但是我们相信它是有回报的，因为另一种选择是“Scheduler样的”模式。这就是为什么没有通用的导出格式。

关于CP优化器的效率。是的，没有直接的比较。恐怕你得自己做实验。写两遍你的模型，因为语言是不同的。例如，如果我只给出一个理由，说明为什么值得一试，那么CP优化器就能够解决几十年来一直未解决的调度问题：

• Vilim，Laborie，Shaw:对基于约束的调度

的失败定向搜索

最后，对于模型中的小改动会对性能产生巨大影响这一事实。是的，这是平常的事。我不认为只有CP优化器才会受到它的影响。在某种程度上，它有助于理解求解者是如何工作的。尽管如此，有时我也无法事先猜出哪种方法会是最好的。所以我的建议是做实验。通常较短的模型表现更好。幸运的是，尝试不同版本的模型并不昂贵。