0

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

据我了解，cplex 启发式可以提高最佳值的下限，但不能提高上限。但在我的测试中，如果我关闭 cplex 启发式，它会给出非常差的上限。上限（启发式开/关）的差异非常大，不容忽视。帮我 ：-（

4

1 回答 1

0

本研究的一个基本示例，假设您的 MIP 是一个纯二进制线性程序 (BLP)，只有二进制值决策变量（没有混合连续变量）。此外，假设 CPLEX 仅使用基本的分支定界 (BAB) 来求解 MIP，而忽略了高级分支和节点选取技术。

正如您所提到的，由于您的程序是最大化程序之一，因此良好的启发式自然会影响最佳解决方案的目标函数值的下限。

在我们的简单示例中，上限将主要基于对连续松弛 BLP 子问题的当前最佳（最佳 wrt max.obj.function value）解决方案。即，您的 BAB 树中活动节点（尚未修剪分支）的 LP 解决方案，其中对您的决策变量的二元性约束（例如x_i ∈ {0, 1}^n）已被其连续松弛（例如 ）取代x_i ∈ [0, 1]^n。

在这一点上，（元）启发式可以对例如

  • 我们如何选择要在 BAB 树中处理的节点。即，在一个节点被修剪或分支之后，我们如何决定下一个选择哪个节点？
  • 此外，如果启发式算法可以在早期为我们提供良好的下限（例如，最佳现有解决方案），那么我们可能会迅速修剪（有界）树中的许多节点，否则我们可能会显式处理这些节点，以防没有良好的下限。

节点的选择对求解过程中上界（最大问题）的进度影响很大，同样如此；自然，较小的解决方案空间（由于许多修剪节点）将增加改善问题上限的可能性/“速度”。

好的启发式可以对整个求解过程产生影响的过程中的另一个点自然是在预处理阶段。在开始 BAB 树遍历之前。真正聪明的启发式方法可以大大减少解决方案空间，特别是如果我们试图解决一个允许明显重构/分解为不太复杂的问题的问题。就其本身而言，此类预处理步骤可能不是启发式方法（因此当您关闭 CPLEX 启发式方法时不会停用），但我会说它们生活在同一个家庭中。

于 2016-07-01T14:12:26.533 回答