CP Optimizer与其他约束编程求解器的比较/ [关闭]

问题描述 投票:-1回答:1

In最近使用CP Optimizer(CPLEX约束编程求解器)解决了几个调度项目,并能够获得一些非常好的结果。但是,与Cplex相比,CP Optimizer对我来说仍然是一个很大的黑匣子。通常有可能以不同的方式提出问题,而小的更改可能会在性能上产生巨大差异。我认为缺少文档和示例,这使其很难使用。也没有所有约束编程求解器共享的标准化约束集,甚至没有导出格式都无法让我解决CP Optimizer和替代求解器(Xpress Kalis或Gecode等开源替代方案)提出的问题。 (例如)。

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

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

optimization constraints cplex cp-optimizer
1个回答
3
投票

实际上有多个问题。作为CP Optimizer开发人员,我尝试回答一些与CP直接相关的问题优化器。

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

因此,ILOG Scheduler已终止。相反,我们创建了带有可选间隔变量的CP Optimizer。我们为排程问题设计了全新的语言,据我们所知,它可以描述排程问题以更简单的方式。并且它为求解器提供了更有效地解决问题所需的信息。如果你想了解更多我推荐以下论文:

  • Laborie,Rogerie:根据条件时间间隔进行推理
  • Laborie,Rogerie,Shaw,Vilim:有条件时间间隔的原因,第二部分:资源的代数模型

因此与其他求解器相比,调度语言大部分不同。如果你来自不同的地方求解器,您必须从头开始编写(调度)模型。但是我们认为,由于替代方案是“类调度程序”模型。这就是没有通用导出格式的原因。

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

  • Vilim,Laborie,Shaw:基于约束的计划的故障定向搜索

最后要考虑的事实是,模型中的微小变化会对性能产生巨大影响。是的通常。而且我认为受此困扰的不是CP Optimizer。这有助于在某种程度上了解求解器工作。有时我还是无法预先猜测哪种方法是最好的。所以我的建议是实验。通常,较短的模型性能较好。幸运的是,没有尝试使用不同版本的模型那贵。

© www.soinside.com 2019 - 2024. All rights reserved.