求解器解的最优性 | cplex、gurobi和COPT求解器求解出来的一定是最优解吗?有理论证明吗?

这篇具有很好参考价值的文章主要介绍了求解器解的最优性 | cplex、gurobi和COPT求解器求解出来的一定是最优解吗?有理论证明吗?。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

作者: 刘兴禄,清华大学,清华-伯克利深圳学院博士在读

欢迎关注我们的微信公众号 运小筹

求解器解的最优性 | cplex、gurobi和COPT求解器求解出来的一定是最优解吗?有理论证明吗?

之前有人在【运小筹读者2群】里问:cplex、gurobi和COPT求解器求解出来的一定是最优解吗?有理论证明什么的吗?

我给除了下面的回答,我觉得对大家会有用,因此稍加整理分享一下。

首先,对于MIP,给足求解时间,设置MIPGap的容差为0,最后得到的一定是最优解。

cplex、gurobi和COPT等求解器使用的是通用的branch and cut算法框架,该框架是精确算法框架。

一个最小化的MIP问题,其松弛问题,即线性松弛是其下界,任意一个可行解是上界。下界和上界的相对差距,就是间隙,optimality gap,简称gap,也就是求解日志最后一列。

求解MIP的分支切割算法,是将精确算法割平面算法融入到另一个精确算法:分支定界框架中。

分支定界本质上是一种分而治之的隐枚举,通过隐枚举,更新全局最优上界和全局最优下界,整个过程都可以保证最优性,通过搜索,最后达到全局最优。

割平面法用来割去小数最优解,并且收紧可行域,加速求解,逼近凸包。

最终整个框架的最优性,通过gap得到证明。gap就是当前解距离最优解的 最大可能的 相对差距。gap等于0,说明当前解一定是全局最优解。

具体理论证明,分为这么几个大的部分:以min问题为例

  1. 一个LP,如果可行,我们是可以通过单纯形法,或者内点法求解到最优解的,最优性通过检验数等相关内容可以得到证明。具体证明见单纯形法相关内容。

  2. 一个MIP的线性松弛是一个LP,这个LP的最优解,是MIP一个下界,这个MIP的最优解不可能比这个小。

  3. 任意一个整数可行解,一定是MIP的一个上界。MIP的最优解一定小于等于这个可行解。

  4. 分支定界算法,通过隐枚举,更新全局上界和下界,一定可以保证最后得到最优解。具体证明见分支定界的全局上界和下界的证明。

  5. 割平面法,不会割去任何整数可行解。因此割平面法的使用,不会影响最优性,只是加速作用。

以上5个部分各自的证明,可以详细去看,我只是说了结论。以上5个部分,是cplex,gurobi等求解器求解MIP的算法框架branch and cut的主要内容,这每一个内容都有非常完善的理论证明以及最优性保障,综合起来,这个算法框架就是精确算法框架。如果模型有可行解,并且给足足够的求解时间,求解器100%可以保证得到最终的最优解。文章来源地址https://www.toymoban.com/news/detail-459124.html

到了这里,关于求解器解的最优性 | cplex、gurobi和COPT求解器求解出来的一定是最优解吗?有理论证明吗?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 优化| 手把手教你学会杉树求解器(COPT)的安装、配置与测试

    作者: 刘兴禄,清华大学,清华伯克利深圳学院博士在读 欢迎关注我们的微信公众号 运小筹 最近杉数求解器发布了4.0.2版本。著名的优化求解器benchmark测评的官网也更新了最近的榜单。 网址如下: Benchmarks for Optimization Software - Hans Mittelmann http://plato.asu.edu/bench.html 线性规划

    2023年04月13日
    浏览(78)
  • 风光柴储微电网最优化经济调度模型(Matlab+Yalmip+Cplex)——附代码

    目录 摘要: 1.微电网模型 2.微电网经济调度的目标函数 3.微电网经济调度的约束条件 3.1设备自身约束: 3.2功率平衡约束: 4.Yalmip+Cplex 4.1 Yalmip 4.2 Cplex 5.运行图片: 6.本文Matlab代码实现 微电网优化调度作为智能电网优化的重要组成部分,对降低能耗、环境污染具有重要 意义

    2024年02月02日
    浏览(61)
  • 【运筹优化】拉格朗日松弛 & 次梯度算法求解整数规划问题 + Java调用Cplex实战

    当遇到一些很难求解的模型,但又不需要去求解它的精确解,只需要给出一个次优解或者解的上下界,这时便可以考虑采用松弛模型的方法加以求解。 对于一个整数规划问题,拉格朗日松弛放松模型中的部分约束。这些被松弛的约束并不是被完全去掉,而是利用拉格朗日乘子

    2024年02月11日
    浏览(48)
  • 【数学建模】Python+Gurobi求解非线性规划模型

    目录 1 概述 2 算例  2.1 算例 2.2 参数设置 2.3 Python代码实现 2.4 求解结果 如果目标函数或约束条件中包含非线性函数,就称这种规划问题为非线性规划问题。 参考:(非线性规划Python)计及动态约束及节能减排环保要求的经济调度 2.1 算例 2.2 参数设置 求解NLP/非凸问题时,

    2024年02月09日
    浏览(43)
  • 优化求解器 | Gurobi的MVar类:矩阵建模利器、求解对偶问题的备选方案 (附详细案例+代码)

    作者:刘兴禄,清华大学,清华-伯克利深圳学院博士在读 修宇璇,清华大学,清华-伯克利深圳学院博士在读 欢迎关注我们的微信公众号 运小筹 本文涉及到的模型(LP, MIP)均是为了说明问题,即使是MIP,我们也将其当做LP看待。 LP: linear programming , 线性规划; MIP: mixed integer

    2023年04月08日
    浏览(47)
  • 【数学建模】二次规划求解约束极值问题(Python+Gurobi实现)

    目录 1 概述 2 算例及Python代码实现 2.1 算例 2.2 方法1 2.3 方法1求解结果 2.4 方法2         根据约束条件的不同,二次规划可分为等式约束二次规划问题和不等式约束二次规划问题。等式约束二次规划问题即只含有等式约束,常见的解法有直接消去法、广义消去法、拉格朗日

    2024年02月08日
    浏览(63)
  • 电力系统强大的Gurobi 求解器的学习(Python&Matlab)

      到底有多强大,看看就知道,必须👍👍👍:  目录 1 概述   2 算例理解【Python】 2.1 算例1——详细入门  2.2 算例2——一般线性规划问题  2.3 算例3——非凸问题   3 算例升级【Matlab】 3.1 模型 3.2 电力系统经济调度(Matlab代码实现)[Yalmip + Gurobi]  4 致谢  我们经常提到

    2023年04月21日
    浏览(40)
  • 独立任务的最优调度问题(动态规划)

    问题描述: 用2台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间ai,若由机器B来处理,则需要时间bi。由于各作业的特点和机器的性能关系,很可能对于某些i,有aibi,而对于某些j,j≠i,有ajbj。既不能将一个作业分开由2台机器处理,也没有一台机器能同时处理

    2024年02月04日
    浏览(45)
  • 【最优化算法】基于【MATLAB】的最速下降仿真

    无约束问题的求解过程一般都是通过一系列的一维搜索来实现,搜索方向的不同,形成了不同的最优化方法。这篇文章从最速下降法入手,来进行搜索。 最速下降法又叫梯度法,通过梯度下降法来一步步的迭代求解,得到最小化的损失函数和模型参数值。如果我们需要求解损

    2024年02月05日
    浏览(41)
  • Ubuntu服务器上的最优WordPress方案

    WordPress是一个经典而又强大的博客程序,并且易于安装与搭建,在OpenShift上不花半分钟就可以免费建起一个WordPress博客,Ubuntu上只需要使用apt-get install wordpress就能快速安装。 不过问题在于WordPress的程序非常不科学,以致于百度WordPress贴吧的加精帖都是在吐槽它如何的没前途

    2023年04月18日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包