作者: 刘兴禄,清华大学,清华-伯克利深圳学院博士在读
欢迎关注我们的微信公众号 运小筹
之前有人在【运小筹读者2群】里问:cplex、gurobi和COPT求解器求解出来的一定是最优解吗?有理论证明什么的吗?
我给除了下面的回答,我觉得对大家会有用,因此稍加整理分享一下。
首先,对于MIP,给足求解时间,设置MIPGap的容差为0,最后得到的一定是最优解。
cplex、gurobi和COPT等求解器使用的是通用的branch and cut算法框架,该框架是精确算法框架。
一个最小化的MIP问题,其松弛问题,即线性松弛是其下界,任意一个可行解是上界。下界和上界的相对差距,就是间隙,optimality gap,简称gap,也就是求解日志最后一列。
求解MIP的分支切割算法,是将精确算法割平面算法融入到另一个精确算法:分支定界框架中。
分支定界本质上是一种分而治之的隐枚举,通过隐枚举,更新全局最优上界和全局最优下界,整个过程都可以保证最优性,通过搜索,最后达到全局最优。
割平面法用来割去小数最优解,并且收紧可行域,加速求解,逼近凸包。
最终整个框架的最优性,通过gap得到证明。gap就是当前解距离最优解的 最大可能的 相对差距。gap等于0,说明当前解一定是全局最优解。
具体理论证明,分为这么几个大的部分:以min问题为例
-
一个LP,如果可行,我们是可以通过单纯形法,或者内点法求解到最优解的,最优性通过检验数等相关内容可以得到证明。具体证明见单纯形法相关内容。
-
一个MIP的线性松弛是一个LP,这个LP的最优解,是MIP一个下界,这个MIP的最优解不可能比这个小。
-
任意一个整数可行解,一定是MIP的一个上界。MIP的最优解一定小于等于这个可行解。
-
分支定界算法,通过隐枚举,更新全局上界和下界,一定可以保证最后得到最优解。具体证明见分支定界的全局上界和下界的证明。
-
割平面法,不会割去任何整数可行解。因此割平面法的使用,不会影响最优性,只是加速作用。文章来源:https://www.toymoban.com/news/detail-459124.html
以上5个部分各自的证明,可以详细去看,我只是说了结论。以上5个部分,是cplex,gurobi等求解器求解MIP的算法框架branch and cut的主要内容,这每一个内容都有非常完善的理论证明以及最优性保障,综合起来,这个算法框架就是精确算法框架。如果模型有可行解,并且给足足够的求解时间,求解器100%可以保证得到最终的最优解。文章来源地址https://www.toymoban.com/news/detail-459124.html
到了这里,关于求解器解的最优性 | cplex、gurobi和COPT求解器求解出来的一定是最优解吗?有理论证明吗?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!