使用旧代码的SCIP

Question

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

Answer 1

在GCG中，您不需要自己实现任何东西。这是一个通用的解决方案的分支和价格。你必须提供紧凑的公式，也就是说，一个模型，在应用了丹茨格-沃尔夫公式后，导致了你正在解决的主要问题。重构还提供了定价问题的MIP公式，因此GCG可以作为定价的子MIP来解决这一问题。但是，有可能在GCG中插入一个定价求解器，将求解的定价MIP传递给它(目标函数对应于当前的定价周期)。然后，定价求解者可以使用任何特定于问题的算法来解决这个问题，并将解决方案传递给GCG。

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

此外，如果您想要做分支和价格，您需要一个分支规则。GCG附带了一些通用的，在SCIP中，您必须自己实现一个(因为分支决策必须在您的定价过程中考虑)。

总的来说，SCIP是一个分支和价格的框架，也就是说，它提供了树管理、LP解决和更新等功能，但是您需要自己实现一些东西，比如读取器、价格和分支规则。GCG是一个通用的求解器，所以您只需插入一个紧凑的模型，该模型将被重新定义并以通用的方式求解。重构要么由您通过输入文件提供，要么您可以尝试让GCG检测到一个适当的结构。您不需要实现任何东西。它已经提供了一些很好的特性，比如利用重新制定的原始启发式，一个自动管理的定价问题得到解决，以及更多。另一方面，与SCIP相比，进一步扩展它的可能性(例如通过定价求解器和分支规则)受到限制，因为您必须坚持GCG定义的结构。

我想说的是，使用SCIP和增加您的价格可能是更容易的方式，并且更类似于您已经拥有的(您不需要制定紧凑的模型)。如果您已经知道分支应该如何工作，那么在SCIP中也应该不难实现。