c++ - SCIP中的分支和价格

Question

我有一个关于使用 SCIP 在分支和价格中进行分支的问题。SCIP 通常会在原始变量上分支吗？例如，在 VRP 示例中，它是在主问题变量还是原始问题变量上分支？如果我想在原始变量上进行分支，是否需要添加自己的分支规则？

Answer 1

单独讨论 SCIP 时，默认情况下 SCIP 将仅对模型中存在的变量进行分支（在进行分支和定价时，这些变量是您的主变量）。VRP 示例只是定价者的一个非常简短的示例，并没有实现特定于问题的分支规则。但是，一般来说，强烈建议您实现自己的问题特定分支规则，就像在着色和装箱示例中所做的那样。他们都实现了 Ryan&Foster 分支。

Ben 是对的，对原始变量本身进行分支通常是一个坏主意，因为这可能会重新引入对称性。然而，主变量本身的分支通常同样糟糕，因为它们的数量很大，只有极少数是非零的，因此分支将非常不平衡。并且在将变量固定为零之后，您必须确保分支不会再次生成该变量的副本。因此，我的建议是在没有对称性或约束（源自原始问题）上分支原始变量，就像 Ryan-Foster 分支规则所做的那样。

或者，您应该看看 GCG，它已经实现了一个通用的分支和价格，包括通用的分支规则。您需要将原始模型读入 GCG，然后 GCG 将根据您可以提供的结构进行 Dantzig-Wolfe 重新制定。

Answer 2

您使用的是GCG还是 SCIP？GCG中已经有一些分支和价格的分支规则。我建议您检查这些，看看是否是您正在寻找的。