开发者社区> 问答> 正文

想问下这个MIP/GapRel,MIP/GapAbs的数学定义是啥?

想问下这个MIP/GapRel,MIP/GapAbs的数学定义是啥?

展开
收起
三分钟热度的鱼 2024-07-07 08:35:52 57 0
1 条回答
写回答
取消 提交回答
  • 在混合整数规划(MIP)问题的求解过程中,MIP/GapRelMIP/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阈值,一旦达到这个阈值,算法就会终止,认为找到了足够好的解。

    2024-07-13 20:12:20
    赞同 1 展开评论 打赏
问答地址:
归属于问产品:
MindOpt优化求解器
进入专区
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载