混合整数非线性规划的算法软件及最新进展资料下载.pdf
- 文档编号:5975740
- 上传时间:2023-05-05
- 格式:PDF
- 页数:20
- 大小:310.01KB
混合整数非线性规划的算法软件及最新进展资料下载.pdf
《混合整数非线性规划的算法软件及最新进展资料下载.pdf》由会员分享,可在线阅读,更多相关《混合整数非线性规划的算法软件及最新进展资料下载.pdf(20页珍藏版)》请在冰点文库上搜索。
数学2016年第46卷第1期:
120SCIENTIASINICAMathematicac2016中国科学杂志社混合整数非线性规划的算法软件及最新进展刘明明x,崔春风y,童小娇zx,戴彧虹yx湘潭大学数学与计算科学学院,湘潭411105;
y中国科学院数学与系统科学研究院,北京100190;
z湖南第一师范学院数学与计算科学学院,长沙410000E-mail:
,xjtong-,收稿日期:
2014-12-29;
接受日期:
2015-06-18;
网络出版日期:
2015-12-21;
*通信作者国家自然科学基金(批准号:
11171095,71371065,11331012和81173633)和国家杰出青年科学基金(批准号:
11125107)资助项目摘要混合整数非线性规划(mixedintegernonlinearprogramming,MINLP)已经渗入到了实际生活中的各个领域,其研究有着重要的现实意义.为有效求解不同类型的MINLP问题,研究者们不断提出新的算法和有效软件.本文致力于介绍求解MINLP问题的基本算法与相应的优化软件,并介绍MINLP问题的研究进展.关键词混合整数非线性规划分支定界割平面软件MSC(2010)主题分类01-02,90C11,97N801引言科学与工程等领域中的很多优化决策问题都包括影响最终设计质量的离散变量和非线性系统.混合整数非线性规划(mixedintegernonlinearprogramming,MINLP)就是包含这两大挑战的一类问题.最近几十年,应用领域对MINLP的需求促使其研究十分受欢迎,其应用领域包括:
水资源管理和共享1,设计、组合及控制相互作用领域2,在不定条件下的过程组合和设计应用3,4,物流基地布局优化5,电力市场机组组合问题6,化工生产的计划和调度问题等.关于MINLP在实际生活中的应用,参见文献7.可见如何有效求解MINLP问题颇有现实意义.MINLP是一类包含连续与离散变量的非线性规划(nonlinearprogramming,NLP)问题.一般情形下,MINLP模型可以表述为以下形式:
ZMINLP=minf(x,y),s.t.gj(x,y)60,j=1,.,m,xX,yYZp,(1.1)其中函数f:
RnpR,gj:
RnpR,n和p分别是连续变量x和整数变量y的维数,X和Y分别是Rn和Rp中的多面体子集,Y是有界的.本文假设f和g是二次连续可微分的,但不对函数f和g刘明明等:
混合整数非线性规划的算法软件及最新进展的凸性作过多假设.为了更清楚表达,定义向量值函数g(x,y)=(g1(x,y),g2(x,y),.,gm(x,y)T,下面称它为MINLP原问题.MINLP的研究可以说是在混合整数线性规划(mixedintegerlinearprogramming,MILP)研究成果的基础上发展起来的,其中包括MILP812和0-1MINLP1315,以及MIQCP(mixedintegerquadraticconstrainedprogramming)等特殊形式问题.我国学者孙小玲与李端在混合整数规划方面有一些理论与综述性文章,如文献16,17.但本文仅侧重介绍一般MINLP.MINLP是规划领域中最难求解的问题之一,属于NP-难问题18.由于MINLP含有整数变量,使得求解NLP的很多优秀算法都不能直接求解MINLP.因此,虽然自20世纪80年代开始(参见文献9,16),尤其是在越来越多实际问题中的应用,使得MINLP受到了国内外很多学者的广泛关注.但是相对于MILP问题,在理论和算法上还有较大的差距,且仍然有很多瓶颈,如很难判断当前解是否最优.关于MINLP的发展情形,感兴趣的读者可参见文献1922.近年来,MINLP算法理论的研究及相关软件的开发有了很大的进展,参见文献2325.本文致力于为求解MINLP问题提供强有力的工具,即提供有助于找到高质量可行解的算法和软件.首先,第2节阐述了求解凸MINLP问题常用的六种确定型算法与两种启发式算法.第3节介绍了求解非凸MINLP问题的两种工具,以及直接求解非凸MINLP问题的算法.确定型算法是将求解困难的MINLP问题分解为简单易处理的问题.而启发式算法是在可接受时间与占用空间等前提下快速找到可行解,但不保证可行解的最优性.对于更难求解的非凸MINLP问题(如其约束是双线性、三线性),我们首先提供了两种常用处理非凸性的方法:
完全重构与凸性化.在处理非凸MINLP时需要注意的是对整数变量进行松弛后的非凸NLP.因为在求解这类NLP问题时,(可能)通常只能得到局部最优解.经过处理的非凸MINLP问题就可以选择凸MINLP的算法进行求解.然后给出了可以直接求解非凸MINLP问题的算法(如-分支定界算法(-branch-and-bound,-BB).第4节分开源软件与商业软件两大类概括MINLP的计算软件,包括常用的开源软件BONMIN,COUENNE,LaGO,SCIP及商业软件ECP,BARON,DICOPT,KNITRO;
包括这些软件的开发者,可以执行的算法,软件的统一资源定位符(uniformresourcelocator,缩写为URL),在使用中依赖的其他软件.最后,第5节对MINLP发展进行简单总结并对未来研究发展趋势进行展望.2凸混合整数非线性规划的算法凸MINLP要求目标函数及约束条件均是凸的,即对整数变量进行松弛后得到连续凸问题.一方面,凸NLP子问题可以求得全局最优解;
另一方面,凸约束的线性近似恰为其外逼近,使得凸MINLP有较好的理论性质.本节重点介绍求解凸MINLP的六种确定型算法和两种常用启发式算法.确定型算法是将求解困难的MINLP问题分解为简单易处理的问题,通常采用迭代法和分支定界两种基本思想.启发式算法是在可接受时间、内存空间等前提下快速找到可行解,但并不保证可行解的最优性.事实上,二者并非独立,很多确定型算法往往需要利用启发式算法帮助快速找到可行解.这里需要指明的是,在求解MINLP问题的过程中,对问题进行预处理是相当重要的.预处理的目的是得到与原问题等价且更紧凑更容易处理的问题.一般容易扩展到MINLP的预处理方法包括系数和变量的上下界的缩紧处理、删除冗余变量和冗余约束等.在此不再详细介绍,读者可参见文献19,26.2中国科学:
数学第46卷第1期2.1子问题求解MINLP问题的算法的基本思想是产生和改善最优解的界限.MINLP最优解的下界(对偶界)由MINLP的松弛子问题提供.常见的松弛策略包括对整型变量松弛到连续空间(NLP子问题)和非线性约束的线性化(MILP子问题).最优解的上界(原始界)由MINLP的可行解提供.虽然不同的算法构造的子问题、提供上下界的方式不尽相同,然而其中一些算法具有共同的基本理论,下面进行详细描述.2.1.1MILP子问题如果MINLP原问题(1.1)的目标函数是非线性的,它的最优解有可能是可行域凸包中的内点,这类问题不宜直接求解.常用的处理方法是引入辅助变量,将非线性目标函数转化为线性目标函数,并将目标函数转移到约束中,得到与(1.1)等价的MINLP问题ZMINLP=min,s.t.f(x,y)6,g(x,y)60,xX,yYZp,R.求解MINLP的很多算法都依赖于MINLP的目标函数与约束函数的线性逼近.设当前点为(x,y),由于f和g都是凸函数,故不等式f(x,y)+f(x,y)T(xxyy)6f(x,y),g(x,y)+g(x,y)T(xxyy)6g(x,y)成立.因此,非线性约束条件f(x,y)6,g(x,y)60在(x,y)点处可分别松弛为线性不等式f(x,y)+f(x,y)T(xxyy)6,(2.1)g(x,y)+g(x,y)T(xxyy)60.(2.2)此时,可得(1.1)的一种MILP子问题ZMINLP=min,s.t.f(x,y)+f(x,y)T(xxyy)6,g(x,y)+g(x,y)T(xxyy)60,xX,yYZp,R.(2.3)值得指出的是,对g(x,y)线性化是外逼近可行域,对f(x,y)线性化是对目标函数进行了低估.因此,通常称(2.1)和(2.2)为(1.1)的外逼近割平面.3刘明明等:
混合整数非线性规划的算法软件及最新进展2.1.2NLP子问题MINLP的另一种松弛子问题是将整数变量松弛到连续空间.假设yi的每个分量满足界限li6yi6ui.为了便于描述,令I=1,.,p,(lI,uI)=(li,ui)|iI,得(1.1)的一种NLP松弛子问题ZNLPR(lI,uI)=minf(x,y),s.t.g(x,y)60,xX,lI6y6uI.(2.4)若(lI,uI)是初始问题(1.1)可行域的上下界限,则求解(2.4)得到的ZNLPR(lI,uI)是ZMINLP的有效下界,而(1.1)的上界由可行解提供.在算法执行过程中,若相信整数点y是原问题的一个好点,则固定整数变量y=y,得NLP子问题ZNLP(y)=minxf(x,y),s.t.g(x,y)60,xX.(2.5)如果(2.5)是可行的,则(2.5)为(1.1)提供上界;
否则NLP求解器一般会求解一个相关可行子问题.可行子问题的一种构造方式为ZNLPF(y)=minmi=1i,s.t.g(x,y)6,0,xX,Rm,(2.6)其中i表示约束gi(x,y)的违反度.一般情形下,若ZNLPF(y)=0,则(2.6)的解为(1.1)的可行解.当子问题(2.5)不可行时,NLP求解器就会返回(2.6)的解.2.2凸混合整数非线性规划问题的确定型算法求解凸MINLP的算法通常采用迭代法和分支定界法(branch-and-bound,BB)两种思想.迭代法是不断更新子问题和迭代点列,直到算法收敛.由于NLP子问题是凸的,可以求得全局最优解,MILP的BB算法稍加修改就可以推广到MINLP,并且取得了较好的数值效果.BB算法的基本思想是生成分支定界树和上下界序列.在树的每个节点处,都要求解一个子问题.对应的解将与上下界序列比较,若不能产生更好的解,则进行剪枝.直到上下界相等或者没有更多的节点时,算法终止.本节将介绍六种主要确定型算法.
(1)非线性规划-分支定界算法.该算法于1965年由Dakin27首次应用到求解凸MINLP问题.
(2)广义Benders分解算法.该算法是1972年Geoffrion28首次利用非线性凸对偶理论对Benders分解进行推广,将其用于求解MINLP.4中国科学:
数学第46卷第1期(3)外逼近算法.该算法于1986年由Duran和Grossmann29提出,并且求解了一类特殊类型MINLP问题.(4)基于线性/非线性-分支定界算法.该算法是1992年Quesada和Grossmann30为了改善0-1MINLP问题提出的.(5)扩展割平面算法.1995年,Westerlund和Petterson31将割平面进行扩展,并求解了凸MINLP问题.(6)混合算法.2008年,Bonami等人32提出将基于线性/非线性-分支定界算法与外逼近算法结合到一起形成了混合算法.2.2.1非线性规划-分支定界算法非线性规划-分支定界算法(NLP-branch-and-bound,NLP-BB)是求解MILP的分支定界算法(BB)在MINLP问题中的直接推广.1960年,Land和Doig33首次将BB算法应用到MILP问题.1965年,Dakin27第一个提出BB算法可以应用到凸MINLP问题,推动了BB算法的发展.但只给出了算法理论,没有给出计算实例.1985年,Gupta和Ravindran34也将此算法应用到了凸MINLP问题,并且研究了算法可行性,给出了运算过程.NLP-BB算法首先要对分支定界树初始化,一般仅包含一个根节点,即将整数变量yYZp松弛到lI6y6uI.第1步节点选择.搜索分支定界树,选择某一节点,在此节点处求解NLP问题.若此问题不可行,删除此节点并重新搜索分支定界树;
否则,设得到解(x,y).第2步剪枝.若在此点处的目标函数大于当前上界,这部分可行域显然不包含最优解,则剪枝.第3步分支.主要对整数约束变量y进行检验.若点y不满足整数约束条件,不妨设yi为小数,则问题分支为左右两个子节点,分别添加左分支约束yi6yi及右分支约束yiyi+1;
否则,若y满足整数约束条件,且目标函数值小于当前的最优值,则更新上界,并且剪掉目标函数值大于当前上界的分支.第4步检查分支定界树是否为空.若分支定界树非空,返回第1步;
否则,算法终止并输出当前最优解.NLP-BB算法有三个关键步骤:
分支、节点选择和剪枝.所谓的分支就是将可行域逐次分割为越来越小的子集,通常采用的分支准则包括强分支、伪费用分支、可信性分支和混合分支等(参见文献3437).常用的节点选择策略包括深度优先搜索、最佳优先搜索、最佳估计搜索以及它们的结合策略12,34,35.剪枝就是当算法满足当前目标函数值大于当前最好上界时,或者NLP子问题的解y恰好是整数等情形,不需要对当前节点进一步分支时进行的操作.NLP-BB算法的基本思想与用BB算法求解MILP问题类似.但是在每个节点处都要求解NLP问题,需要很大的计算代价.这也表明了求解MINLP比MILP有本质上的困难:
求解MILP问题时,所有的连续松弛子问题都是线性规划(linearprogramming,LP),而MINLP的连续松弛子问题都是NLP,其求解速度和解的质量依赖于NLP求解.近几十年,在分支定界算法框架的基础上诞生了数个变体,如空间分支定界算法38,39、分支下降算法40,41和分支定价算法42.这些算法被应用于各个领域,使BB算法得到更加广泛的利用.2.2.2外逼近算法外逼近(outerapproximation,OA)算法的理论基础是凸MINLP问题可以等价于一个有限维的5刘明明等:
混合整数非线性规划的算法软件及最新进展MILP问题.1986年,Duran和Grossmann29提出用OA算法求解特殊类型的MINLP问题,并给出了算法的收敛性和最优性证明.1994年,Fletcher和Leyffer43将OA算法应用于工程领域,并给出新颖而简单的有限终止定理.他们的研究进一步推进了OA算法理论发展并将其成功推广到了应用中.OA算法主要利用的数学工具是映射、外逼近和松弛.它属于迭代算法,首先在根节点求解MINLP的连续松弛问题(2.4)并初始化线性化点集T.它在每个迭代步都要求解NLP问题和MILP问题:
(1)固定整数变量yk得到NLP子问题(2.5)或(2.6),求解NLP问题得到连续变量xk并试图更新上界.
(2)用(xk,yk)更新T,即T=T(xk,yk),构造和求解MILP问题ZOA=min,s.t.f(x,y)+f(x,y)T(xxyy)6,(x,y)T,g(x,y)+g(x,y)T(xxyy)60,(x,y)T,xX,yYZp,(2.7)得到整数解yk+1并更新下界.(3)若上下界的差值满足给定的容忍度,则终止;
否则,返步
(1).由文献32中的相关定理证明可知,假设(2.5)或(2.6)满足KKT条件,则上述算法要么收敛到(1.1)的最优解,要么表明(1.1)不可行.值得指出的是,在每次迭代中,上界和下界只是可能会得到改善.因为只有当(2.5)可行并且它的最优值小于当前上界时,(1.1)的上界才会得到更新;
否则,若(2.5)不可行,求解(2.6)并不能为原问题提供有效界.另外,由于在每一次迭代中添加新的OA割使(2.7)的定义发生了变化,导致上一次迭代产生的解不可行,故利用当前解对界限进行更新.OA算法已经用到IDCOPT和BONMIN等软件包中.此外,OA也可用于求解随机最短路径中的锥二次规划模型44,通过一系列赋值等处理后,数值试验结果表明OA算法要比标准整数规划算法好很多.这推动了OA算法在理论及应用方面的进展.2.2.3广义Benders分解广义Benders分解(generalBendersdecomposition,GBD)最初是1962年Benders45为求解MILP问题提出的,其基本思想是将MILP模型分解为一系列LP模型和纯整数规划(integerprogram-ming,IP)模型,并且一般只用于求解小规模问题.1972年,Geoffrion28首次利用非线性凸对偶理论对Benders分解进行推广,将其应用于MINLP.1995年,Floudas7详细给出了GBD的基本理论和过程,进一步将Benders分解在求解MILP问题中取得的成果进行了扩展,为MINLP问题的研究提供了更好的向导.GBD迭代算法与OA算法用到的数学工具相同,只有构造MILP的方式不同.它的基本思想是分解,首先在根节点求解MINLP的连续松弛问题(2.4)并初始化线性化点集K1和K2.它在每个迭代步都要求解NLP问题和MILP问题:
(1)固定整数变量yk得到NLP子问题(2.5)或(2.6),求解NLP问题得到连续变量xk并试图更新上界.
(2)用(xk,yk)更新K1或K2,构造和求解MILP问题(2.8),其中MILP子问题的更新方式如下:
如果子问题(2.5)是可行的,利用目标函数及有效约束函数线性化后的有效结合,生成最优割添加到6中国科学:
数学第46卷第1期MILP子问题.对于固定的y,令(x,y)是(2.5)的最优解,则有最优Lagrange乘子0使得以下广义Benders分解对于MINLP问题是成立的,f(x,y)+(yf(x,y)+yg(x,y)T(yy);
而如果(2.5)不可行,利用(2.6)提供的解(x,y)及Lagrange乘子0得到相应的最优割Tg(x,y)+yg(x,y)(yy)60.这样可得到MILP松弛子问题ZGBD=min,s.t.f(x,y)+(yf(x,y)+yg(x,y)T(yy),(x,y)K1,Tg(x,y)+yg(x,y)(yy)60,(x,y)K2,yYZp,R,(2.8)其中K1和K2分别表示(2.5)和(2.6)的最优解集.(3)若上下界的差值满足给定的容忍度,则终止;
否则,返步
(1).利用OA算法求解MILP问题得到的下界比利用GBD算法得到的下界的精确性要强29,这导致GBD算法总体上需要的迭代次数比OA算法多.但是,注意到子问题(2.8)比(2.7)规模小,所以有时候用GBD算法比OA算法更方便.如今,Abhishek等人46建议Benders割平面添加到分支定界算法中,为Benders割平面带来了新的发展空间.如今人们已经利用GBD算法求解不定性过程供应链计划中的两阶段随机线性规划问题47,工程设计优化中的双层规划问题48,更具有挑战性的过程设计和组合优化的较大规模非凸MINLP问题49等,不断推进GBD算法的研究发展.2.2.4基于线性/非线性-分支定界算法基于线性/非线性-分支定界算法(LP/NLPbasedbranch-and-bound,LP/NLP-BB)于1992年由Quesada和Grossmann30提出,并证明了该方法的收敛性,故有时也称QG算法.LP/NLP-BB最初目的是改善0-1MINLP问题的求解效率.第1步是初始化MILP子问题.在根节点处求解MINLP松弛问题(2.4)得其解为(x,y),并初始化线性化点集C=(x,y),在此节点处利用外逼近思想构造MILP子问题.第2步是利用BB求解MILP.选择分支定界树的某一节点,求解LP子问题.若LP不可行,则删除此节点并重新搜索分支定界树;
否则设(x,y)为LP的解.若y为非整数,则对当前节点进行分支处理;
否则,若y为整数,则求解NLP子问题(2.5).如果(2.5)是可行的,设(x,y)为其最优解.当(2.5)的最优函数值小于当前上界时,更新上界.如果(2.5)不可行,则令(x,y)为(2.6)的最优解.利用(2.5)或(2.6)提供的解(x,y)更新线性化点集C=C(x,y),并更新MILP子问题.第3步是检查分支定界树是否为空.若没有要访问的节点,则算法终止;
否则重复进行第2步.7刘明明等:
混合整数非线性规划的算法软件及最新进展LP/NLP-BB算法已经被应用到BONMIN和FiMINT等软件包中.它可以看成OA算法的延伸,与OA算法的区别在于LP/NLP-BB求解的是一系列LP子问题ZLP/NLP=min,s.t.f(x,y)+f(x,y)T(xxyy)6,(x,y)C,g(x,y)+g(x,y)T(xxyy)60,(x,y)C,xX,yY,R,R,(2.9)其中Y是在可行域Y中加入分支信息,从而避免了求解大量MILP子问题(2.7),并且不需要在所有的节点处更新线性化点集C.LP/NLP-BB与NLP-BB的不同点在于,LP/NLP-BB并非在每个节点处求解NLP子问题,而是需要求解一系列LP子问题.仅当LP子问题得到可行整数解时,再求解NLP子问题,从而节省计算量.2.2.5扩展割平面法扩展割平面法(extendedcuttingplane,ECP)是1995年Westerlund和Petterson31对1960年Kelly50提出的只能用于求解凸NLP的割平面法的扩展,用于求解凸MINLP问题并给出ECP算法的收敛性.ECP的基本思想是割平面,每个迭代步仅需要求解一个MILP子问题ZECP=min,s.t.f(x,y)+f(x,y)T(xxyy)6,(x,y)D,gj(x,y)+gj(x,y)T(xxyy)60,(x,y)D,jJ(x,y),xX,yYZp,R,(2.10)其中D为(2.10)的迭代解集.如果MILP的解(x,y)满足所有的线性化,则算法终止;
否则更新迭代解集D=D(x,y)和最大违反约束指标集J(x,y)def=jargmaxjJgj(x,y),J=1,.,m.有的学者也考虑将所有违反约束都添加到J(x,y).(2.10)的迭代最优解为(1.1)的最优解提供了一非降下界序列,有限收敛定理31证明其收敛到(1.1)的最优解,但是一般需要很多次迭代才能实现.常用的商业软件-ECP执行的就是ECP算法.此外,ECP算法在理论和应用中也得到了扩展.现在ECP算法已经可以求解伪凸MINLP问题51.文献52将SHP(生成支撑超平面)的思想融入到ECP算法中,由于SHP算法对可行域比ECP算法更小,从而加快了算法的收敛速度.文献53详细给出了ECP算法在光滑和非光滑问题中的应用,并给出了收敛性证明.文献54利用ECP求解了一类非可微MINLP,这类问题的目标函数及约束函数是f0伪凸的,并证明了算法可以收敛到MINLP的全局最优解.可见人们在努力将ECP应用到更复杂的MINLP问题,促使对ECP的研究不断深入.2.2.6混合算法混合算法(Hyb)是2008年由Bonami等人32提出的.这个混合算法是将Quesada和Gross-mann提出的LP/NLP-BB与OA算法结合到一起,本质上是对LP/NLP-BB进行改进.混合算法与8中国科学:
数学第46卷第1期LP/NLP-BB的不同点在于,
(1)每l步,在分支定界树子节点处直接求解NLP子问题(2.5)或(2.6)用于构造OA切割;
(2)限定时间t,对分支定界树的根节点调用OA算法,求解MILP松弛问题和NLP子问题,进行局部搜索.如果局
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 混合 整数 非线性 规划 算法 软件 最新进展