混合整数非线性规划的算法软件及最新进展

自然科学基金项目进展专栏综述英文引用格式:LiuMM,CuiCF,TongXJ,etal.Algorithms,softwaresandrecentdevelopmentsofmixedintegernonlinearprogramming(inChinese).SciSinMath,2016,46:1{20,doi:10.1360/N012014-00278中国科学:数学2016年第46卷第1期:120SCIENTIASINICAMathematicac⃝2016《中国科学》杂志社混合整数非线性规划的算法软件及最新进展刘明明¬,崔春风­,童小娇®¬,戴彧虹­∗¬湘潭大学数学与计算科学学院,湘潭411105;­中国科学院数学与系统科学研究院,北京100190;®湖南第一师范学院数学与计算科学学院,长沙410000E-mail:[e-mail],[e-mail],[e-mail],[e-mail]收稿日期: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;x∈X;y∈Y∩Zp;(1.1)其中函数f:Rn×p→R,gj:Rn×p→R,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)研究成果的基础上发展起来的,其中包括MILP[8{12]和0-1MINLP[13{15],以及MIQCP(mixedintegerquadraticconstrainedprogramming)等特殊形式问题.我国学者孙小玲与李端在混合整数规划方面有一些理论与综述性文章,如文献[16,17].但本文仅侧重介绍一般MINLP.MINLP是规划领域中最难求解的问题之一,属于NP-难问题[18].由于MINLP含有整数变量,使得求解NLP的很多优秀算法都不能直接求解MINLP.因此,虽然自20世纪80年代开始(参见文献[9,16]),尤其是在越来越多实际问题中的应用,使得MINLP受到了国内外很多学者的广泛关注.但是相对于MILP问题,在理论和算法上还有较大的差距,且仍然有很多瓶颈,如很难判断当前解是否最优.关于MINLP的发展情形,感兴趣的读者可参见文献[19–22].近年来,MINLP算法理论的研究及相关软件的开发有了很大的进展,参见文献[23–25].本文致力于为求解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;x∈X;y∈Y∩Zp;∈R:求解MINLP的很多算法都依赖于MINLP的目标函数与约束函数的线性逼近.设当前点为(ˆx;ˆy),由于f和g都是凸函数,故不等式f(ˆx;ˆy)+▽f(ˆx;ˆy)T(x−ˆxy−ˆy)6f(x;y);g(ˆx;ˆy)+▽g(ˆx;ˆy)T(x−ˆxy−ˆy)6g(x;y)成立.因此,非线性约束条件f(x;y)6;g(x;y)60在(ˆx;ˆy)点处可分别松弛为线性不等式f(ˆx;ˆy)+▽f(ˆx;ˆy)T(x−ˆxy−ˆy)6;(2.1)g(ˆx;ˆy)+▽g(ˆx;ˆy)T(x−ˆxy−ˆy)60:(2.2)此时,可得(1.1)的一种MILP子问题ZMINLP=min;s.t.f(ˆx;ˆy)+▽f(ˆx;ˆy)T(x−ˆxy−ˆy)6;g(ˆx;ˆy)+▽g(ˆx;ˆy)T(x−ˆxy−ˆy)60;x∈X;y∈Y∩Zp;∈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)|i∈I};得(1.1)的一种NLP松弛子问题ZNLPR(lI;uI)=minf(x;y);s.t.g(x;y)60;x∈X;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;x∈X:(2.5)如果(2.5)是可行的,则(2.5)为(1.1)提供上界;否则NLP求解器一般会求解一个相关可行子问题.可行子问题的一种构造方式为ZNLPF(^y)=minm∑i=1i;s.t.g(x;ˆy)6;0;x∈X;∈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年由Dakin[27]首次应用到求解凸MINLP问题.(2)广义Benders分解算法.该算法是1972年Geoffrion[28]首次利用非线性凸对偶理论对Benders分解进行推广,将其用于求解MINLP.4中国科学:数学第46卷第1期(3)外逼近算法.该算法于1986年由Duran和Grossmann[29]提出,并且求解了一类特殊类型MINLP问题.(4)基于线性/非线性-分支定界算法.该算法是1992年Quesada和Grossmann[30]为了改善0-1MINLP问题提出的.(5)扩展割平面算法.1995年,Westerlund和Petterson[31]将割平面进行扩展,并求解了凸MINLP问题.(6)混合算法