模型中的非线性——处理方法1


Note: This blog article is to my newly-born son. A gift for your one-month old celebration, ORson (Is it a nice name?)!





很多人发邮件让我帮其review数学模型,有来自老师的,有来自学生的,有来自公司的,其中问的一个比较多的问题是:我的模型中有这些非线性,Cplex/Gurobi/Mosek能求解么?(本篇博文中的非线性主要不是指二次,指的是general nonlinear)

首先,我们必须明确:优秀的solvers本身也不是万能的! Cplex可以求解(MI)LP/QCQP/SOCP,至于新版本宣称也可求解nonconvex QP,也仅限于采用一阶导数等方法求驻点(局部最优,控制学科中称为stable points);Gurobi也是一个(MI)LP/QCQP的solver;MOSEK除了是一个
(MI)LP/QCQP/SOCP

solver外,对Separable Optimization Problem,Geometric Programming,Entropy Optimization Problem也可以求解。其它商业优化软件我不再评述了,但基本都是限于Convex Optimization Problem(什么?不知道模型是否convex? YALMIP中的export命令可以帮助您检测:
[aa,bb,cc] = export([],exp(x),sdpsettings(‘
allownonconvex’,1)),cc就包含了是否convex的信息
)。啰嗦了这么多,我的意思是:想用这些软件,就必须将模型中的非线性处理称这些solver能接受的形式。

本篇博文中介绍第一种处理非线性的方式:巧用0-1变量和辅助决策变量,避免在模型中引入非线性。下面我们通过两个例子说明:

【例1】
问题描述:工件j在机器i上实际需要加工的时间为l_ij小时,机器i每天工作的时间为L小时,在调度中我们希望必要的时候压缩工时(当然需要成本),使工件在机器上加工时间为整天计数。决策变量y_ij=1,表示压缩工件j在机器i上的加工时间,具体压缩的量为u_ij小时(也为一个决策变量),工件j在机器i上实际加工的天数用决策变量t_ij表示。

【分析】
:粗糙的建模方式:u_ij = (l_ij-L*t_ij)*y_ij;把这样一个式子引入模型,就可能引入高度的非线性甚至nonconvexity。注意到:y_ij=0时,u_ij=0,t_ij=ceil(l_ij/L);y_ij=1时,t_ij = floor(l_ij/L),u_ij=l_ij-L*t_ij,则通过下面约束可以反映上述决策变量间的关系:

(Constraint 1)0<=u_ij<=bigM*y_ij;

(Constraint 2)l_ij-L*t_ij-
bigM*(1-y_ij)
<=u_ij<=
l_ij-L*t_ij+bigM*(1-y_ij);

(Constraint 3)l_ij/L-y_ij<=t_ij<=l_ij/L+(1-y_ij)

Is it an elegant formulation?这样,就能避免了在模型中人为地引入nonlinearity和nonconvexity,我们再次提醒大家:Carefully Modeling,尽量避免一切非线性的东西。




【例2】
目标函数中的交叉项:f1*x1,其中,x1=0时,这一项为0,x1=1时,目标中这一项为f1。假设是minimize问题。




【分析】
:相信很多人在建模时为目标函数中的决策变量交叉乘积苦恼过,尤其是其中一个是0-1变量。我们不妨增加辅助决策变量p1来代替f1*x1。这时目标函数变为min p1,同时通过增加下面的约束来刻画你的逻辑:

(Constraint 4)f1<=p1+bigM*(1-x1)
(Constraint 5)0<=p1+bigM*x1

【注】
很多人是不是为不知如何建模piecewise linear function苦恼过?很多solver,如cplex中提供了piecewise linear function的建模命令,可以直接用;那么,如果在没有这些命令的情况下,我们如何去建模呢?第一种方法就是自己增加0-1变量,比如某函数有3段,就可以增加2个0-1变量,用他们的取值来反映变量具体落在哪一段,在建模过程中,你如果没有经验的话,就会碰到【例2】中的问题,看了本篇博文,相信你无所畏惧了;第二种方法是,你可以采用SOS2(Special Ordered Set Type 2)变量来帮助你建模,cplex/ Gurobi/ Lpsolve等solver都提供了这种功能,具体的方法,你可以参考:

http://lpsolve.sourceforge.net/5.0/SOS.htm

无论哪种方法,最后在solver内部都转化为MIP问题了,所以,对于我这种能
熟练地耍binary variables的人,从来都是自己添加binary variables,而不用提供好的piecewise linear建模功能和SOS2变量。



希望这篇文章在一定程度上帮助你!我知道我现在回家洗尿布更能表达对ORson的父爱,但作为对ORson的满月礼物是不是很Cool?

ORson,Dad loves you! 爸爸也希望你将来成为能够帮助别人的人!



请关注关于处理模型中非线性的方法的
后续
博文!



稿源:Chinese OR Tea (源链) | 关于 | 阅读提示

本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。
酷辣虫 » 移动互联 » 模型中的非线性——处理方法1

喜欢 (0)or分享给?

专业 x 专注 x 聚合 x 分享 CC BY-NC-SA 4.0

使用声明 | 英豪名录