作者： 劉興祿，清華大學(xué)，清華-伯克利深圳學(xué)院博士在讀
歡迎關(guān)注我們的微信公眾號(hào) 運(yùn)小籌
之前有人在【運(yùn)小籌讀者2群】里問(wèn)：cplex、gurobi和COPT求解器求解出來(lái)的一定是最優(yōu)解嗎？有理論證明什么的嗎？
我給除了下面的回答，我覺(jué)得對(duì)大家會(huì)有用，因此稍加整理分享一下。
首先，對(duì)于MIP，給足求解時(shí)間，設(shè)置MIPGap的容差為0，最后得到的一定是最優(yōu)解。
cplex、gurobi和COPT等求解器使用的是通用的branch and cut算法框架，該框架是精確算法框架。
一個(gè)最小化的MIP問(wèn)題，其松弛問(wèn)題，即線(xiàn)性松弛是其下界，任意一個(gè)可行解是上界。下界和上界的相對(duì)差距，就是間隙，optimality gap，簡(jiǎn)稱(chēng)gap，也就是求解日志最后一列。
求解MIP的分支切割算法，是將精確算法割平面算法融入到另一個(gè)精確算法：分支定界框架中。
分支定界本質(zhì)上是一種分而治之的隱枚舉，通過(guò)隱枚舉，更新全局最優(yōu)上界和全局最優(yōu)下界，整個(gè)過(guò)程都可以保證最優(yōu)性，通過(guò)搜索，最后達(dá)到全局最優(yōu)。
割平面法用來(lái)割去小數(shù)最優(yōu)解，并且收緊可行域，加速求解，逼近凸包。
最終整個(gè)框架的最優(yōu)性，通過(guò)gap得到證明。gap就是當(dāng)前解距離最優(yōu)解的 最大可能的 相對(duì)差距。gap等于0，說(shuō)明當(dāng)前解一定是全局最優(yōu)解。
具體理論證明，分為這么幾個(gè)大的部分：以min問(wèn)題為例
-
一個(gè)LP，如果可行，我們是可以通過(guò)單純形法，或者內(nèi)點(diǎn)法求解到最優(yōu)解的，最優(yōu)性通過(guò)檢驗(yàn)數(shù)等相關(guān)內(nèi)容可以得到證明。具體證明見(jiàn)單純形法相關(guān)內(nèi)容。
-
一個(gè)MIP的線(xiàn)性松弛是一個(gè)LP，這個(gè)LP的最優(yōu)解，是MIP一個(gè)下界，這個(gè)MIP的最優(yōu)解不可能比這個(gè)小。
-
任意一個(gè)整數(shù)可行解，一定是MIP的一個(gè)上界。MIP的最優(yōu)解一定小于等于這個(gè)可行解。
-
分支定界算法，通過(guò)隱枚舉，更新全局上界和下界，一定可以保證最后得到最優(yōu)解。具體證明見(jiàn)分支定界的全局上界和下界的證明。
-
割平面法，不會(huì)割去任何整數(shù)可行解。因此割平面法的使用，不會(huì)影響最優(yōu)性，只是加速作用。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-459124.html
以上5個(gè)部分各自的證明，可以詳細(xì)去看，我只是說(shuō)了結(jié)論。以上5個(gè)部分，是cplex，gurobi等求解器求解MIP的算法框架branch and cut的主要內(nèi)容，這每一個(gè)內(nèi)容都有非常完善的理論證明以及最優(yōu)性保障，綜合起來(lái)，這個(gè)算法框架就是精確算法框架。如果模型有可行解，并且給足足夠的求解時(shí)間，求解器100％可以保證得到最終的最優(yōu)解。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-459124.html
到了這里，關(guān)于求解器解的最優(yōu)性 | cplex、gurobi和COPT求解器求解出來(lái)的一定是最優(yōu)解嗎？有理論證明嗎？的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
