求解器求解过程中gap没有太大变化怎么办？

求解器求解过程中gap没有太大变化怎么办？

求解器用的是分支定界框架，准确的说用的是分支切割算法，在分支定界的框架中不断自动添加各种割cut，直到“所有”节点探测完毕。

gap体现了目前求解的状态，直观的说，gap=(上界-下界)*100%/上界(min问题)。更一般的表述是：（当前最好解-bound）*100%/bound。

从公式上可以看出，当gap下降很快，要么是上界在降低（更好的整数解），要么是下界在提升（更好的下界）。

回到一开始的问题，当gap没有太大的变化（找不到更好的解，bound改进比较慢）时，我们的方法也是从上述公式入手，要么想办法找到更好的可行解，要么想办法提升bound。具体的说，有以下几个思路可以着手：

1.考虑为什么找不到更好的整数可行解（上界）？

要么是模型特别复杂，求解器的数学启发式无法找到更好的可行解。>>>尝试启发式算法输入一个比较好的可行解；

或者是，目前解已经是最优可行解，但是optimality proof没完成，因为下界不改进了。（这个没办法，分支定界必须探索完所有节点）。

2.考虑为什么下界不改进了？

这个问题，一般是模型比较松弛，不够紧。LP的解距离整数解差距比较大，因此迭代缓慢。>>>改写模型；

另外就是分支切割算法无法找到新的有效的cut以进一步收紧下界。>>>尝试添加cut；

还有就是，模型复杂，分支后分支定界树极其不平衡。>>>尝试不同的探索策略，广度，深度，或混合策略。

注：

当问题求解很快，反应在求解器的输出日志上体现在两方面，一个是需要探测的节点在减少；一个是gap在不断下降，甚至下降的很快。前者是探测节点很快，节点所在的支被切掉（整数解，更差的非整数解，或不可行三种情形之一），此时求解会很快，反应在求解器的输出日志上就是，需要备探测的节点在减少。后者是gap下降很快，这种情况要么是找到了更好的上界，更小的整数解（最小化问题），要么是更好的下界，这种情况的本质是前者的探测节点在减少，砍掉了更多的枝。