我有一个关于SCIP的一般问题 . 我需要使用SCIP作为我的问题的分支和价格框架，我在c中编码所以我使用VRP示例作为模板 . 在一些实例中，代码停在分数解决方案并返回作为最佳解决方案，我认为有些错误，我是否必须设置一些参数以告知SCIP寻找整数解决方案或我犯了一个错误，我相信它不应该停止，而是分支到分数解决方案，直到它达到整数解决方案（没有任何其他负减少成本列） . 我也最佳地解决了子问题！任何纪念活动？！
如果您定义变量是连续的并且只是添加一个价格，SCIP将解决主要问题的最优性（即，解决受限制的主数据，添加改进列，解决更新的受限主数据等，直到没有更多的改进列为找到） .
SCIP没有理由检查解决方案是否是完整的，因为您明确表示您不介意变量的值是否为整数（通过将它们定义为连续） . 另一方面，如果您将变量定义为整数（或二进制）类型，SCIP将完全按照我之前描述的方式执行，但最后检查所有积分变量是否具有整数值并且如果不是这样则分支 .
但是，您应该注意SCIP中的所有分支规则都对变量进行分支，即它们采用具有小数值的整数变量并拆分其域;二进制变量将固定为两个子节点中的0和1 . 对于分支机构而言，这通常是一个坏主意：首先，它是非常不 balancer 的 . 你有大量的变量，其中只有少数最终会有值1，大多数都是0.因此将变量修改为1具有很大的影响，而将其修改为0几乎没有影响 . 但更重要的是，您需要在定价问题中考虑分支决策 . 如果将变量固定为0，则必须使pricer不生成禁用列的副本（这可能会改进LP解决方案，因为它是前一个最佳解决方案的一部分） . 为此，您可能需要寻找第二个（或更晚的k）最佳解决方案 . 由于您使用SCIP解决了作为MIP的定价问题，您可能只需添加约束来禁止此解决方案（二进制变量的逻辑或（线性）或一般整数变量的bounddisjunction（非线性）） .
我建议实施您自己的分支规则，该规则考虑到您正在以更加 balancer 的方式进行分支价格和分支，并且不会过多地损害您的定价 . 例如，查看Ryan＆Foster分支规则，该规则是具有集合分区主结构的二进制问题的标准 . 此规则在Binpacking以及SCIP附带的着色示例中实现 .
还请查看SCIP FAQ，其中有关于分支和价格的整个部分，其中还包括主题分支（特别是，如何通过约束处理程序存储和强制执行分支决策，这是您需要做的事情为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优化套件的一部分，可以在套件中轻松构建 .
1 回答
如果您定义变量是连续的并且只是添加一个价格，SCIP将解决主要问题的最优性（即，解决受限制的主数据，添加改进列，解决更新的受限主数据等，直到没有更多的改进列为找到） .
SCIP没有理由检查解决方案是否是完整的，因为您明确表示您不介意变量的值是否为整数（通过将它们定义为连续） . 另一方面，如果您将变量定义为整数（或二进制）类型，SCIP将完全按照我之前描述的方式执行，但最后检查所有积分变量是否具有整数值并且如果不是这样则分支 .
但是，您应该注意SCIP中的所有分支规则都对变量进行分支，即它们采用具有小数值的整数变量并拆分其域;二进制变量将固定为两个子节点中的0和1 . 对于分支机构而言，这通常是一个坏主意：首先，它是非常不 balancer 的 . 你有大量的变量，其中只有少数最终会有值1，大多数都是0.因此将变量修改为1具有很大的影响，而将其修改为0几乎没有影响 . 但更重要的是，您需要在定价问题中考虑分支决策 . 如果将变量固定为0，则必须使pricer不生成禁用列的副本（这可能会改进LP解决方案，因为它是前一个最佳解决方案的一部分） . 为此，您可能需要寻找第二个（或更晚的k）最佳解决方案 . 由于您使用SCIP解决了作为MIP的定价问题，您可能只需添加约束来禁止此解决方案（二进制变量的逻辑或（线性）或一般整数变量的bounddisjunction（非线性）） .
我建议实施您自己的分支规则，该规则考虑到您正在以更加 balancer 的方式进行分支价格和分支，并且不会过多地损害您的定价 . 例如，查看Ryan＆Foster分支规则，该规则是具有集合分区主结构的二进制问题的标准 . 此规则在Binpacking以及SCIP附带的着色示例中实现 .
还请查看SCIP FAQ，其中有关于分支和价格的整个部分，其中还包括主题分支（特别是，如何通过约束处理程序存储和强制执行分支决策，这是您需要做的事情为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优化套件的一部分，可以在套件中轻松构建 .