计算 MIP 问题 GAMS 中的相对最优性差距

Question

我想计算 MIP 问题的相对最优性差距，我还想在某个运行时间中止运行s。这个方法：

F(1)    
abs(mymodel.objest - mymodel.objval)/max(abs(mymodel.objest),abs(mymodel.objval))

与GAMS计算的对数gap不一致。 GAMS 使用“最佳整数”来寻找差距而不是当前 objective 值。哪个是正确的？以及如何将当前“最佳整数”保存到参数中（如 .objval）。

最后在 benders 算法中计算相对最优 Gap 是这样吗？

rgap = (upperBound - lowerBound)/(1 + abs(upperBound));

GAMS 使用“MIP 解”计算什么

MIP Solution:   3334501534.000555    (1625 iterations, 0 nodes)
Final Solve:      56330158.829040    (2561 iterations)

Best possible:    48915652.476336
Absolute gap:   3285585881.524219
Relative gap:            0.985330

F(1) 使用 mymodel.objval（mymodel.objval return“最终求解”）计算出的差距因此计算出的差距为 %13，mymodel.objval 值为 5.633016E+ 7（GAMS 计算的差距为 %98）。所以我需要将“MIP 解决方案”保存到一个参数中以将其导出到 excel 文件。

Answer 1

计算相对最优差距有不同的公式。这取决于您使用的求解器，应用了哪一个。有关此的一些信息可以在 GAMS 选项 optCR 的描述中找到。您使用的求解器的求解器手册可能包含有关实际应用的公式的更多详细信息。

问题更新后编辑：

如您所写 mymodel.objval returns Final Solve 值。如果您想改为查看 MIP Solution 值（因为 Cplex link 在内部执行此操作），您可以停用最终求解。但是，如果 Final Solve 和 MIP Solution 与您的示例中的差异如此之大，这通常表明存在某些问题（通常，它们（几乎）相同）。通常，这表明模型缩放比例不佳。也许您可以通过收紧 Cplex 容差（参见 Cplex 选项 epopt、eprhs、epint）和激活积极缩放（Cplex 选项 scaind 2）来改善这种情况。激活 mipkappastats (https://www.gams.com/latest/docs/S_CPLEX.html#CPLEXmipkappastats) and quality (https://www.gams.com/latest/docs/S_CPLEX.html#CPLEXquality) could give you more information. DataCheck=2 (https://www.gams.com/latest/docs/S_CPLEX.html#CPLEXdatacheck) 可能会出现一些问题。

计算 MIP 问题 GAMS 中的相对最优性差距

Calculate relative optimality Gap in MIP Problem GAMS

gams-math

mixed-integer-programming