专栏首页程序猿声CPLEX出现'q1' is not convex?

CPLEX出现'q1' is not convex?

不知道大家在写CPLEX的时候遇到过这个问题没有?

其实有过经验的小伙伴都知道该怎么处理了,但是小编决定还是写一下避免刚入行的小伙伴们踩坑。

这个错误呢查了ibm knowledge center显示如下:

里面讲了一堆想必大家也懒得去看了,我来讲讲这类问题的解决方案吧~出现这个错误的原因不是编程上的问题,而是建模方式上的问题。简单来说就是目标函数或者约束上出现了非线性的数学表达式。

那么什么是线性和非线性呢?我这里引一下百度知道上一个非常通俗易懂的解释:

两个变量之间的关系是一次函数关系的——图象是直线,这样的两个变量之间的关系就zhi是“线性关系”;如果不是一次函数关系的——图象不是直线,就是“非线性关系”。比如说y=kx 就是线形的 而y=x^2就是非线形的线形的图形一般是一条直线。 “非线性”的意思就是“所得非所望”。一个线性关系中的量是成比例的:十枚橘子的价钱是一枚的十倍。非线性意味着批发价格是不成比例的:一大箱橘子的价钱比一枚的价钱乘以橘子的个数要少。这里重要的观念是“反馈”——折扣的大小反过来又影响顾客购买的数量。

也就是说你的模型中很可能出现了多个变量相乘的情况,例如下面这种情景:

要解决这个问题,首先就得想你的模型给linearlized了。而最常用的做法就是“大M”法了,通过增加一个充分大的数,将多个相乘的变量给拆开,从而达到线性化的目的。

不过像上图那种情况就非常麻烦(其实是我建模建错了),今天就先不讨论。举个简单的例子,VRP的arc-flow模型中货物流常见的约束如下:

其中

Q_j^k

x_{i,j}^k

为决策变量,

Q_j^k

表示车辆

k

离开客户

j

以后的载重量,而

x_{i,j}^k

为1表示车辆走过边(

i, j

),否则为0。这条约束的含义是非常明了的,如果车辆经过边(

i, j

),那么该车辆离开客户

j

的载重量必须大于等于车辆离开客户

i

的载重量加上客户

j

的需求量,这是货物流平衡。

可以看到不等式右边出现了变量和变量相乘的情况,这就造成了我们刚刚说的“非线性”问题,那么这个模型放进cplex中肯定会报“not convex”的错误。为了让cplex能求解该模型,我们需要将非线性的约束转成线性的。

常见的一个办法是引入一个充分大的数,我们都喜欢叫它大M。当然这个数具体要多大,是不是越大越好,也不一定,后面我再讲。

先观察约束(8)右端的式子,发现只有当

x_{i,j}^k

为1时,才需要

Q_j^k \ge Q_i^k + q_i

,当

x_{i,j}^k

为0时,

Q_j^k

就无所谓了。这是一个非常明显的if else约束。因此可以考虑将

x_{i,j}^k

提取出来,和一个大M相乘:

Q_j^k \ge Q_i^k + q_j +M(x_{i,j}^k-1)

我们现在来检验上面这个约束含义是否和之前的保持一致。首先当

x_{i,j}^k

为1时,

M(x_{i,j}^k-1)=0

,约束变成

Q_j^k \ge Q_i^k + q_j

,这个没问题。然后当

x_{i,j}^k

为0时,

M(x_{i,j}^k-1)=-M

,这个约束就被松弛掉了,也就是说

Q_j^k

取其定义域内任意值都能满足,也和之前的保持一致。

这样,我们就将两个相乘的变量通过一个大M将其拆开了。将其他非线性约束改成非线性约束,就能放进CPLEX跑了。当然了,小编才疏学浅,目前只知道这种方法,不过已经够小编用了,就没继续往下深究。关于大M法将if else类的约束线性化,我这里贴一个知乎上的回答:

如果有多个变量相乘,那可能就得引入多个大M。不过呢,到这里还没有结束。下面我们聊聊关于大M的取值与CPLEX的精度可能造成的BUG。这种BUG是非常可怕的,如果不了解这一点,可能要走很多很多弯路哦,而且书本上才不会告诉你这些。

还是下面这条式子:

Q_j^k \ge Q_i^k + q_j +M(x_{i,j}^k-1)

关键就在于CPLEX可能会存在精度损失,比如为0-1的决策变量有可能求解之后是这样的:

也就是说当

x=0.9999999995343387

或者当

x=1.0000000004656613

,本应该为0的

M(x_{i,j}^k-1)

此刻都不是0了。那么这就很有可能造成约束失效,从而使模型无法满足所有约束。

不过注意,我上面说的是有可能造成约束失效,而非一定。

x=0.9999999995343387

x=1.0000000004656613

,它们和1相差的值都在小数点的后九位。也就是说当M设置得足够大的时候(比如

10^{10}

),

M(x_{i,j}^k-1)

也会足够大,大到影响约束原本的作用。而当M不那么大的时候(比如

10^{5}

),

M(x_{i,j}^k-1)

也是小数点后4位,对原约束可以认为是没有影响的。

当然这个没有影响是相对于

Q_j^k

q_j

而言,因为他们要求为整数并且大于等于0,就相当于你有1000万,那么丢几块钱对你来说除了有点小小的不爽以外,基本上也是没影响的。

那么M取什么值比较合适呢,这就需要大家去做一个简单的bound了,简单判断下影响约束的一个upper bound或者lower bound,只需要大致估算一个值即可。比如上面那个货物流平衡,可以取

M = 2V_{cap}

,其中

V_{cap}

为车辆的容量。

好了,以上就是今天分享的内容了。可以关注我们,不定时分享一下小编踩过的雷,这样你就不会在漫漫科研路上踩到相同的雷啦。

来都来了,不点个在看吗?

记得点个在看支持下哦~

本文分享自微信公众号 - 程序猿声(ProgramDream),作者:邓发珩

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-11-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 手把手教你用CPLEX求解一个数学模型(Java版)

    小编有个小伙伴,隔三差五就过来跟我说:这个模型CPLEX怎么写呢?我说我不是给你讲过好多次?他说CPLEX太复杂了,俺没学过学不会呢。其实对于很多刚入行的小伙伴...

    短短的路走走停停
  • Control is important! model predictive control mpc.pytorch lib

    Optimal control is a widespread field that involve finding an optimal sequence o...

    用户1908973
  • 干货 | 运筹学、数学规划、离散优化求解器大PK,总有一款适合你

    CPLEX 是IBM公司的一个优化引擎。软件IBM ILOG CPLEX Optimization Studio中自带该优化引擎。该软件具有执行速度快、其自带的...

    用户1621951
  • Computational Geometry in Python

    This post is a simplified version of the accompanying notebook to chapter 6 of m...

    周星星9527
  • 出现Uncaught ReferenceError: $ is not defined错误

    今天在写ajax请求的时候,出现了Uncaught ReferenceError: $ is not defined报错;$未定义是为什么呢?

    meihuasheng
  • 干货 | Branch and Price算法求解VRPTW问题(附JAVA代码分享)

    前两天小编刚忙完手头上的事情,闲了下来,然后顺便研究了一下Branch and Price的算法。刚好,国内目前缺少这种类型算法的介绍和代码实现,今天就给大家分...

    用户1621951
  • 为什么局部方法解决非凸问题?(CS)

    非凸优化是现代机器学习中普遍存在的问题。研究人员设计非凸目标函数,并使用现成的优化器进行优化,如随机梯度下降及其变量,利用局部几何和迭代更新。尽管在最坏的情况下...

    用户8440711
  • POJ 2007--Scrambled Polygon(计算凸包,点集顺序)

    Scrambled Polygon Time Limit: 1000MS Memory Limit: 30000K Total Submiss...

    Enterprise_
  • 重磅独家 | 腾讯AI Lab AAAI18现场陈述论文:用随机象限性消极下降算法训练L1范数约束模型

    前言:腾讯 AI Lab共有12篇论文入选在美国新奥尔良举行的国际人工智能领域顶级学术会议 AAAI 2018。腾讯技术工程官方号独家编译了论文《用随机象限性消...

    腾讯技术工程官方号

扫码关注云+社区

领取腾讯云代金券