我有一个关于 SCIP 的一般性问题。我需要使用 SCIP 作为我的问题的分支和价格框架，我用 C++ 编码，所以我使用 VRP 示例作为模板。在某些情况下，代码在分数解处停止并将其作为最佳解返回，我认为出了问题，我是否必须设置一些参数才能告诉 SCIP 寻找整数解，或者我犯了一个错误，我相信它不应该停止，而是在分数解上分支，直到达到整数解（没有任何其他负降低成本列）。我也最优地解决了子问题！有什么评论吗？！
小智 5
如果您将变量定义为连续的并仅添加定价器，SCIP 将解决主问题的最优性（即，解决受限主问题，添加改进列，解决更新的受限主问题，等等，直到不再有改进列为止）成立）。
SCIP 没有理由检查解是否是整数，因为您明确表示您不介意变量的值是否是整数（通过将它们定义为连续的）。另一方面，如果将变量定义为整型（或二进制）类型，SCIP 将完全按照我之前描述的方式执行，但最后检查所有整型变量是否具有整型值，如果不是这种情况则分支。
但是，您应该注意 SCIP 中的所有分支规则都会对变量进行分支，即它们采用带有小数值的整数变量并分割其域；二进制变量在两个子节点中将固定为 0 和 1。对于分支和价格来说，这通常是一个坏主意：首先，它非常不平衡。你有大量的变量，其中只有少数变量最终值为 1，大多数为 0。因此，将变量固定为 1 会产生很大的影响，而将其固定为 0 几乎没有影响。但更重要的是，您需要在定价问题中考虑分支决策。如果将变量固定为 0，则必须阻止定价器生成禁止列的副本（这可能会改进 LP 解决方案，因为它是以前最优解决方案的一部分）。为此，您可能需要寻找第二（或之后的 k）最佳解决方案。由于您正在使用 SCIP 作为 MIP 来解决定价问题，因此您可能只需添加一个约束来禁止此解决方案（二元变量的逻辑或（线性）或一般整数变量的有界析取（非线性））。
我建议实施您自己的分支规则，该规则考虑到您正在以更平衡的方式进行分支和价格以及分支，并且不会对您的定价造成太大影响。例如，查看 Ryan&Foster 分支规则，它是具有集合分区主结构的二进制问题的标准。此规则在 Binpacking 以及 SCIP 附带的 Coloring 示例中实现。
另请查看 SCIP 常见问题解答，其中有一整个关于分支和价格的部分，其中还涵盖了主题分支（特别是，如何通过约束处理程序存储和执行分支决策，这是您需要做的事情对于 Ryan&Foster 分支）：http://scip.zib.de/doc/html/FAQ.php
SCIP 邮件列表http://listserv.zib.de/mailman/listinfo/scip/上也有很多关于分支和价格的问题 。如果你想搜索它，你可以使用谷歌并搜索“site:listserv.zib.de scip search-string”
最后，我想推荐看一下 GCG 项目：http://www.or.rwth-aachen.de/gcg/ 它是 SCIP 对通用分支切割和价格求解器的扩展，也就是说，您不需要实现任何内容，只需输入模型的原始公式，然后通过 Dantzig-Wolfe 分解重新公式化，并通过分支切割和定价来解决。您可以提供重新制定的结构，定价问题作为 MIP 解决（正如您所做的那样），并且还有不同的分支规则。GCG 也是 SCIP 优化套件的一部分，可以在套件中轻松构建。