scip - SCIP using old code

Question

I am kind of new to the SCIP. I want to use SCIP as a branch and price framework. I have coded the problem in C++ already and also have implemented the pricer or column generation as a function. In fact I have implemented the BP algorithm for the root node by linking Cplex.dll to the project and now need to code the branching tree and decided to use SCIP for this purpose. I want to know what is the fastest way I can solve my problem using SCIP and the old codes which I have? Or maybe using GCG is a better and faster way? I have read the GCG documentation but doesn't understand if I should implement the pricer myself again or not? In fact I don't understand the difference between these two (SCIP and GCG). Thanks.

Answer 1

在 GCG 中，您不需要自己实现任何东西。它是分支和价格的通用求解器。您必须提供紧凑的公式，即在应用 Dantzig-Wolfe 重新公式后导致您正在解决的主要问题的模型。重新表述还提供了定价问题的 MIP 表述，因此 GCG 可以将其作为定价的子 MIP 来解决。但是，可以在 GCG 中插入定价求解器，将要求解的定价 MIP 传递给该求解器（目标函数对应于当前定价轮次）。然后，定价求解器可以使用任何特定于问题的算法来解决这个问题，并将解决方案传回 GCG。

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

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

总的来说，SCIP是一个branch-and-price的框架，即它提供了树管理、LP求解和更新等，但是你需要自己实现一些东西，比如reader、pricer和branching rules。GCG 是一个通用求解器，因此您只需插入一个紧凑模型，该模型以通用方式重新制定和求解。重新制定要么由您通过输入文件提供，要么您可以尝试让 GCG 检测适当的结构。你不需要实现任何东西。它已经提供了一些不错的功能，例如利用重新制定的原始启发式、自动管理何时解决哪个定价问题等等。另一方面，与 SCIP 相比，进一步扩展它的可能性（例如，通过定价求解器和分支规则）受到限制，

我会说使用 SCIP 并添加您的定价器可能是更简单的方法，并且与您已有的方法更相似（您不需要制定紧凑模型）。如果您已经知道分支应该如何工作，那么在 SCIP 中实施也不难。