algorithm - CPLEX 提供具有不同目标值的不同最佳解决方案

Question

在同一 ILP 问题上运行 CPLEX 时(完全相同的输入文件):

• 使用MIPEmphasis = 3，我得到的客观值为6.81613e-06
• 使用MIPEmphasis = 4，我得到的客观值为1.03858

在这两种情况下，CPLEX 都会返回 OPTIMAL 状态。

来自 CPLEX 用户手册:

To make clear a point that has been alluded to so far: every choice of MIPEmphasis results in the search algorithm proceeding in a manner that eventually will find and prove an optimal solution, or will prove that no integer feasible solution exists. The choice of emphasis only guides CPLEX to produce feasible solutions in a way that is in keeping with the user's particular purposes, but the accuracy and completeness of the algorithm is not sacrificed in the process.

我在这里遗漏了什么吗？我不仅在使用 MIPEmphasis 参数时面临这个问题，而且在使用其他参数时也面临这个问题(例如 ScaInd)，通过改变参数，我得到不同的 OPTIMAL 质量差异很大的解决方案。

这里有一些我似乎无法破译的更多信息。

对于MIPEmphasis = 3:

Maximum condition number = 5.03484e+12, 
Attention level = 0.290111, 
Suspicious bases: 0.0111111, 
Unstable bases = 0.966667, 
Ill-posed bases = 0, 
CPLEX Status = `OptimalTol`

对于MIPEmphasis = 4:

Maximum condition number = 4.73342e+08, 
Attention level = 0.00925, 
Suspicious bases: 0.925, 
Unstable bases = 0, 
Ill-posed bases = 0, 
CPLEX Status = `Optimal`

Answer 1

这看起来像是常见的数值问题，并且很大程度上取决于您的建模(例如大 M 常量的使用)。

我从未使用过 CPLEX，但是这个 official page讨论病态 MIP 模型。

此处相关的小摘录:

You should reconsider your model if CPLEX reports any ill-posed bases or more than 5% unstable bases.

在你的案例 A 中，你得到了超过 95% 的不稳定碱基:

For MIPEmphasis = 3: .... Unstable bases = 0.966667 ...

所以 A 的结果很可能不可信。此外，我会尝试重新制定我的模型。

如果我们看 B，你会得到 > 92.5% 的可疑碱基，所以即使在这种情况下，模型也可能是在自找麻烦。

由于我不熟悉所有的调整和默认设置，因此我无法深入了解这些与您的 MIPEmphasis 和 co 有关的截然不同的计算结果的来源。 (也许由于 MIPEmphasis 生成更多切割平面会导致更稳定的问题；只是猜测)。