想问下这个MIP/GapRel,MIP/GapAbs的数学定义是啥?
在混合整数规划(MIP)问题的求解过程中,MIP/GapRel
和 MIP/GapAbs
是两个用来衡量求解进展和解质量的重要指标:
MIP/GapRel(相对差距):这是当前找到的最好整数解(通常是 relaxation 解,即放松整数约束得到的解)的目标函数值与已知的最优目标函数值(如果已知的话,或者是最优下界)之间的相对差异。其数学表达式为[1]:
[
\text{GapRel} = \left| \frac{Z{best} - Z{best_known}}{Z_{best_known}} \right| \times 100\%
]
其中,(Z{best}) 是当前找到的最佳解的价值,而 (Z{best_known}) 是当前已知的最佳(或下界)解的价值。这个值越接近0%,表示当前解越接近已知或推断的最佳解。
MIP/GapAbs(绝对差距):则是指上述两者的绝对值差异,不考虑比例,直接衡量数值上的差距。其数学表达式为:
[
\text{GapAbs} = |Z{best} - Z{best_known}|
]
绝对差距提供了关于解之间实际数值差异的直观量度,不受解的大小影响。
这两个指标常用于评估MIP求解器的收敛情况和解的质量,尤其是在求解器报告解的状态或决定何时停止搜索时非常关键。求解器通常会设定一个可接受的Gap阈值,一旦达到这个阈值,算法就会终止,认为找到了足够好的解。
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。