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

Question

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

Answer 1

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

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

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