c++ - SCIP和分支机构和价格

Question

我有一个关于 SCIP 的一般性问题。我需要使用 SCIP 作为分支和价格框架来解决我的问题，我用 C++ 编写代码，所以我使用 VRP 示例作为模板。在某些情况下，代码在分数解处停止并将其作为最佳解返回，我认为出了点问题，我是否必须设置一些参数以告诉 SCIP 寻找整数解或者我犯了一个错误，我相信它不应该停止，而是在分数解上分支，直到它到达整数解(没有任何其他负的降低成本列)。我也最优地解决了子问题!有评论吗？!

Answer 1

如果你定义你的变量是连续的并且只添加一个定价器，SCIP 将解决 master 问题到最优(即，解决受限的 master，添加改进列，解决更新的受限的 master，等等，直到不再发现了改进的列)。

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 邮件列表上也有很多关于 branch-and-price 的问题 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 优化套件的一部分，可以在套件中轻松构建。