CPLEX启发式给出了不同的计算结果

Question

当我们使用cplex解决最大化mip问题时，cplex启发式是否会影响目标值的上界？

据我所知，cplex启发式可以提高最优值的下界，但不能提高上界。但在我的测试中，如果我关闭cplex启发式，它会给出非常差的上限。上限的差异(启发式开/关)是非常巨大的，可以忽略不计。帮帮我:-(

Answer 1

本研究的一个基本示例是，假设您的MIP是一个纯二元线性规划(BLP)，其中只有二进制值的决策变量(没有连续的决策变量)。此外，假设CPLEX仅使用基本分支和绑定(BAB)来解决您的MIP，而忽略了高级分支和节点拾取技术。

由于你的程序是最大化的，正如你所提到的，一个好的启发式自然会影响到最优解的目标函数值的下界。

在我们的简单示例中，上限将主要基于当前最好的(最佳w.r.t.麦克斯。obj。函数值)解连续松弛的BLP子问题。也就是说，BAB树中活动节点(尚未修剪或分支)的LP解决方案，其中对决策变量的二元性约束(例如x_i ∈ {0, 1}^n )已被其连续松弛(例如x_i ∈ [0, 1]^n )所取代。

在这一点上，(元)启发式可以对例如

• 我们如何选择要在BAB树中处理的节点。也就是说，在一个节点被修剪或分支之后，我们如何决定下一个选择哪个节点？
• 另外，如果启发式方法可以在早期为我们提供良好的下限(例如，最佳现任者解决方案)，那么我们可能很快就能够修剪(按约束)树中的许多节点，否则我们可以显式地处理这些节点，以防没有良好的下界。

节点的选择对上界(max.同样，较小的解空间(由于许多被修剪的节点)将增加改善问题上限的可能性/“速度”。

在整个过程中，好的启发式算法可以对整个求解过程产生影响的另一个点自然是在预处理阶段；在开始BAB树遍历之前。真正聪明的启发式方法可以大大减少解空间，特别是当我们试图解决一个允许明显的重构/分解为不太复杂的问题的问题时。从本质上讲，这些预处理步骤可能不是启发式的(所以当你关闭CPLEX启发式时也不会停用)，但我想说它们属于同一个家族。