1

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

4

1 回答 1

3

如果您将变量定义为连续变量并仅添加定价器，则 SCIP 将优化主问题（即解决受限主问题、添加改进列、解决更新受限主问题等，直到不再有改进列成立）。

SCIP 没有理由检查解决方案是否是整数，因为您明确表示您不介意变量的值是否是整数（通过将它们定义为连续的）。另一方面，如果您将变量定义为整数（或二进制）类型，SCIP 将完全按照我之前描述的方式执行，但最后检查是否所有整数变量都具有整数值，如果不是则分支.

但是，您应该注意 SCIP 中的所有分支规则都对变量进行分支，即它们采用带小数值的整数变量并拆分其域；在两个子节点中，二进制变量将固定为 0 和 1。对于分支和价格来说，这通常是一个坏主意：首先，它非常不平衡。您有大量变量，其中只有少数最终值为 1，大多数为 0。因此将变量固定为 1 具有很大的影响，而将其固定为 0 几乎没有影响。但更重要的是，您需要在定价问题中考虑分支决策。如果将变量固定为 0，则必须阻止定价者生成禁止列的副本（这可能会改进 LP 解决方案，因为它是前一个最佳解决方案的一部分）。为此，您可能需要寻找第二个（或更高版本的 k）最佳解决方案。由于您正在使用 SCIP 作为 MIP 解决定价问题，因此您可能只需添加一个禁止此解决方案的约束（对于二进制变量的逻辑或（线性）或对于一般整数变量的 bounddisjunction（非线性））。

我建议实施您自己的分支规则，该规则考虑到您正在以更平衡且不会过多损害您的定价的方式进行分支和价格和分支。例如，查看 Ryan&Foster 分支规则，这是具有集分区主结构的二元问题的标准。此规则在 Binpacking 以及 SCIP 附带的着色示例中实现。

另请查看 SCIP 常见问题解答，其中有一整节关于分支和价格，其中还涵盖了主题分支（特别是，如何通过约束处理程序存储和执行分支决策，这是您需要做的事情对于 Ryan&Foster 分支）：http ://scip.zib.de/doc/html/FAQ.php

SCIP 邮件列表http://listserv.zib.de/mailman/listinfo/scip/上也有很多关于分支和价格的问题 。如果要搜索，可以用google搜索“site:listserv.zib.de scip search-string”

最后，我想推荐看看 GCG 项目：http ://www.or.rwth-aachen.de/gcg/ 它是 SCIP 对通用分支切割和价格求解器的扩展，即，您不需要实现任何东西，您只需输入模型的原始公式，然后通过 Dantzig-Wolfe 分解重新公式化并通过分支切割和价格解决。您可以提供重新制定的结构，定价问题作为 MIP 解决（您也这样做），并且还有不同的分支规则。GCG 也是 SCIP 优化套件的一部分，可以在套件中轻松构建。

于 2014-07-23T09:44:10.913 回答