使用旧代码的SCIP

Question

我对SCIP很陌生。我想用SCIP作为分支和价格框架。我已经用C++编写了这个问题，并且已经实现了价值或列生成功能。事实上，我已经通过将Cplex.dll链接到项目来实现根节点的BP算法，现在需要编码分支树并决定使用SCIP来实现此目的。 我想知道什么是使用SCIP和我拥有的旧代码解决我的问题的最快方法？或者，也许使用GCG是一种更好更快的方式？ 我已阅读GCG文档，但不明白我是否应该再次实施定价机制？实际上我不了解这两者（SCIP和GCG）之间的区别。 谢谢。

Answer 1

在GCG中，您不需要自己执行任何操作。它是分支和价格的通用求解器。您必须提供紧凑的配方，即应用了Dantzig-Wolfe配方后的模型会导致您正在解决的主要问题。重新配置还提供了定价问题的MIP制定，因此GCG可以将其作为定价的子MIP来解决。然而，有可能在GCG中插入一个定价解算器，要求解决的定价MIP将通过（其目标函数对应于当前定价轮次）。然后定价求解器可以用任何问题特定的算法解决这个问题，并将解决方案传递回GCG。

另一方面，在SCIP中，您创建了您想要解决的主要问题并实现了一个从LP获得双重价值的价格，并解决了相应的定价问题。这可能与您已经非常相似。

此外，如果你想要做分支和价格，你需要一个分支规则。 GCG带有一些通用的，在SCIP中，您必须自己实施一个（因为分支决策必须在您的定价过程中考虑）。总的来说，SCIP是一个分支和价格的框架，也就是说，它提供了树管理，LP解决和更新等，但是你需要像阅读器，定价器和分支规则。 GCG是一种通用解算器，因此您可以插入一个紧凑型模型，该模型将以一种通用的方式进行重新配置和解决。重新配制由您通过输入文件提供，或者您可以尝试让GCG检测适当的结构。你不需要执行任何操作。它已经提供了一些很好的功能，例如使用重构的原始启发式，自动管理何时解决哪些定价问题等等。另一方面，与SCIP相比，例如通过定价求解器和分支规则进一步扩展的可能性受到限制，因为您必须坚持GCG定义的结构。

我会说，使用SCIP和添加您的价格是可能的更简单的方法，更类似于你已有的（你不需要制定紧凑型号）。如果你已经知道你的分支应该如何工作，那么在SCIP中实现也不会太难。