一种整数线性乘积规划问题的分支定界算法.pdf

应用数学MATHEMATICA APPLICATA2024,37(1):1-14一种整数线性乘积规划问题的分支定界算法李敏敏1,2,高岳林1,2(1.北方民族大学数学与信息科学学院,宁夏 银川 750021;2.宁夏科学计算与智能信息处理协同创新中心,宁夏 银川 750021)摘要：本文为了求解整数线性乘积规划(ILMP)问题的全局最优解,提出一种新的线性松弛分支定界算法.该算法利用对数函数的单调性及凹凸性,得到(ILMP)全局最小值的下界,并利用区域缩减技术以最大限度地删除不可行区域,加快该算法的收敛速度.最后数值实验表明,本文提出的算法是有效并且可行的.关键词：整数规划;全局优化;分支定界;线性乘积规划;区域缩减中图分类号：O221.2AMS(2010)主题分类：90C30;90C32文献标识码：A文章编号：1001-9847(2024)01-0001-141.引言整数规划可用于解决众多领域中的实际问题,如工商管理、工程技术、金融及社会科学等.随着科学技术的发展和决策问题求解的迫切需要,非线性整数规划问题的算法研究已经成为运筹学与最优化领域的研究热点之一.12求解非线性整数规划问题的确定性方法有割平面法3、分解算法4、外逼近法5、分支定界法610等.由于整数规划是NP难问题,现有算法仅可以求解某种特殊形式的整数规划问题,且往往存在收敛速度慢、最优解效果差、计算复杂等不足,对于特殊的非线性整数规划问题整数线性乘积规划问题,至今还没有一个通用而有效的算法.本文主要考虑以下形式的整数线性乘积规划问题:(ILMP):min f(x)=pj=1(cTjx+dj)j,s.t.x X0=x Rn:Ax b,x Zn.这里j 0,cj Rn,dj R,j=1,p.A Rmn,b Rm,假定cTjx+dj 0,j=1,p.X0为非空有界闭集.(ILMP)不仅应用于金融优化11、证券投资12、微观经济学13等金融经济问题中,而且在VLISI芯片设计14、数据挖掘15、鲁棒优化16等方面也有涉及.由于(ILMP)问题是一个NP-hard问题17,且往往存在许多局部最优解而不是全局最优解,这就使得在理论和计算上存在巨大的挑战.因此,寻找一种有效的算法全局求解(ILMP)问题是十分必要的.从(ILMP)问题的研究历程来看,已经有许多算法都适用于求解全局(LMP)问题,求解全局(ILMP)问题的算法相对较少,现如今分支定界算法已成为求解这类问题最常用的工具之收稿日期：2022-10-19基金项目：国家自然科学基金项目(11161001);宁夏高等教育一流学科建设项目(NXYLXK 2017B09)作者简介：李敏敏,女,汉族,山东人,研究方向:最优化理论与方法.通讯作者：高岳林.2应用数学2024一.根据分支定界算法的框架,基于对(ILMP)问题的松弛,在每个节点求解松弛子问题的下界,得到一个高质量的下界对原问题起着至关重要的作用.SHAO和Ehrgott18提出了利用多目标线性规划和原始对偶条件求解(LMP)问题的全局优化算法.对于广义线性乘积规划问题,JIAO19利用指数函数和对数函数的线性逼近,建立了一类广义线性乘法规划的可靠高效算法.SHEN20将适当删除技术与分支定界格式相结合,提出了求解广义线性乘法规划的一种新的加速方法.针对指数型线性乘法规划问题,LIU和ZHAO21在Youness22的研究基础上提出了一个水平集算法.SHEN等人23提出了一个完全多项式时间逼近算法.对于约束中具有线性乘积项的问题,Benson24提出了一种基于分解的分支定界算法,Kuno25提出了一种基于Soland矩形分支定界法最小化多面体上仿射函数乘积的算法.非凸(ILMP)问题的困难源于决策变量的非连续性以及目标函数为线性乘积,松弛过程中需要将目标函数的连乘利用对数恒等式进行转换以及将决策变量松弛为连续变量,本文给出了求解整数线性乘积规划(ILMP)问题的全局优化算法.该算法结合分支定界操作和区域缩减技术,通过利用对数函数的恒等式,将目标函数等价转化为对数函数求和的形式,使用线性松弛技术将非凸(ILMP)问题转化为线性松弛规划问题,并将其嵌入到分支定界操作中.为了加快算法的收敛速度,在分支和定界过程中采用了区域缩减技术,为当前不存在全局最优解的区域提供了理论可能性,可以显著减少松弛间隙.结合新的线性化技术、分支定界操作、区域缩减技术,本文提出了一种简化的分支定界区域缩减算法.最后,数值实验结果表明,该方法能较好地解决所有存在于全局最优解中的(ILMP)问题.本文的组成结构如下:第一部分提出了整数线性乘积规划问题,并且概述了求解整数线性乘积规划问题的相关算法.第二部分描述了怎样将问题(ILMP)转化为一个等价的问题(EILMP(Hk).第三部分利用对数函数的单调性和凹凸性得到(ILMP)的松弛问题.第四部分将第三部分得到的线性松弛规划,以及区域缩减技术嵌套在分支定界框架内,得到线性松弛分支定界算法以求解整数线性乘积规划问题.第五部分通过实例证明算法的有效性和可行性.第六部分得出相关结论.2.等价问题为了以下叙述的方便,我们首先介绍两个常用的取整函数,分别是上取整函数和下取整函数.上取整函数在数学中记作r,表示不小于r的整数中最小的一个;下取整函数在数学中记作r,表示不超过r的整数中最大的一个.即:r=minn Z|r n,r=maxn Z|n r.本节将分两个阶段对问题(ILMP)进行等价转换.第一个阶段:记问题(ILMP)的可行域为X=X0Zn,构造包含X的整超矩形H=l,u=x|l x u,l,u Zn,其中l=(l1,l2,ln)T,u=(u1,u2,un)T,li=ai,i=1,2,n,ui=bi,i=1,2,n,这里ai,bi分别是(2.1),(2.2)的最优值,当i 1,2,n时,ai=min xi,s.t.x X0,(2.1)bi=max xi,s.t.x X0.(2.2)第 1 期李敏敏等：一种整数线性乘积规划问题的分支定界算法3接下来,引入非负向量y=(y1,y2,yp)T Rp+,满足yj=cTjx+dj,j=1,2,p.当x Hk=ns=1lks,uks H0时,构造y的超矩形Vk=vk,hk=y|vk y hk,vk,hkRp+,其中vk=(vk1,vk2,vkp)T,hk=(hk1,hk2,hkp)T,这里vkj,hkj分别由(2.3),(2.4)求得.vkj=ns=1mincjslks,cjsuks+djs,j 1,2,p,(2.3)hkj=ns=1maxcjslks,cjsuks+djs,j 1,2,p.(2.4)显然,式(2.3),(2.4)表明:uk lk 0 hkj vkj 0.(2.5)因此,我们得到问题(ILMP)在Hk上的第一个等价问题如下:(ILMP(Hk):minpj=1yjj,s.t.yj=cTjx+dj,j=1,2,p,x XHk,y Vk.第二个阶段:根据对数恒等式以及对数函数的性质可得:pj=1yjj=elnpj=1yjj=epj=1jlnyj.(2.6)根据指数函数的单调性,问题(ILMP)可被再次改写为以下问题:(EILMP(Hk):min F(x,y)=pj=1jlnyj,s.t.yj=cTjx+dj,j=1,2,p,x XHk,y Vk.注1当问题(EILMP(Hk)中Hk和Vk分别由H0和V0替换时,问题(EILMP(H0)在本质上与原问(ILMP)等价,若(x,y)为(EILMP(H0)的可行解,其中yj=cTjx+dj,则x必然是(ILMP)的可行解,反之亦然.另外,由式(2.6)知:eF(x,y)=epj=1jlnyj=pj=1yjj=f(x).3.定界技术我们将利用对数函数fj(y)=ln(yj)的凹凸性给出问题(ILMP)在超矩形上的下界函数hj(y)为:hj(y)=ln(vkj)+Aj(yj vkj)=Ajyj+ln(vkj)Ajvkj,其中Aj=lnhkj lnvkjhkj vkj.4应用数学2024定理3.1对于任意的y Vk,考虑fj(y)和hj(y)有下列两条性质:1)函数hj(y)是函数fj(y)的凸包,另外fj(y)和hj(y)满足:hj(y)fj(y),y Vk.2)fj(y)和hj(y)之间的差值满足:maxyVkj(y)0,其中,j(y)=fj(y)hj(y).证1)由于fj(y)=ln(yj)是一个凹函数并且在vkj,hkj上单调递增,它的凸包为ln(vkj)+Aj(yj vkj)=hj(y),因此有:ln(vkj)+Aj(yj vkj)=hj(y)fj(y)=ln(yj).2)记j(yj)=j(y),我们有:j(yj)=ln(yj)ln(vkj)Aj(yj vkj)0.因为j(yj)是在vkj,hkj上是一个凹函数,易得,当yj=1Aj时,j(yj)取得最大值,即:j(1Aj)=maxvkjyjhkjj(yj)=ln(1Aj)ln(vkj)Aj(1Aj vkj)=ln(Aj)ln(vkj)1+Ajvkj=ln(lnhkj lnvkjhkj vkj)ln(vkj)1+lnhkj lnvkjhkj vkjvkj=lnhkj lnvkjhkj vkjvkj 1(ln(lnhkj lnvkjhkj vkj)+ln(vkj)=ln(hkjvkj)hkjvkj 1 1 lnln(hkjvkj)hkjvkj 1,由式(2.5)知,当uk lk 0时,hkj vkj 0,即hkjvkj 1,ln(hkjvkj)hkjvkj1 1.由上式可得:当uklk 0时,j(yj)0.根据定理3.1,问题(EILMP(Hk)可被松弛为:(LRP(Hk):Fl(x,y)=minpj=1j(lnhkj lnvkjhkj vkjyj+lnvkjlnhkj lnvkjhkj vkjvkj),s.t.yj=cTjx+dj,j=1,2,p,x X0Hk,y Vk.对于问题(LRP(Hk)来说,其最优解(x,y)不一定是问题(EILMP(Hk)的可行解,若x Zn,则直接利用(x,y)更新(EILMP(Hk)的上界;否则,记b x=x,由于b x周围存在可能的解,而一个点周围有2n个整点,下面我们分两种情况:当n 5时,令b x周围2n个整点集合为k.当n 5时,对每一个i 1,2,n,取cxi1=(b x1,b x2,b xi+1,dxi+1,cxn)T,cxi2=(b x1,b x2,b xi 1,dxi+1,cxn)T,同时记k=cxi1,cxi2.第 1 期李敏敏等：一种整数线性乘积规划问题的分支定界算法5注2k中的点x也不一定满足x X0,所以在算法中需要判断这些解的可行性.4.分支定界算法及其理论分析整超矩形的分支规则为了得到原问题(ILMP)的全局最优解,提出了整超矩形分支定界算法.在H0被剖分后的子集上求解一系列线性松弛规划问题.在分支过程中,需要依据一定的剖分规则将初始超矩形H0分成两个新的子矩形.本文所采用的是标准整超矩形二分方法.考虑任一通过Hk=lk,uk所确定的子节点问题.分支规则如下所示:1)令=argmaxuki lki:i=1,n;2)记xk=lk+uk2;3)设新的子矩形区域Hk1=1i=1lki,uki lk,xk ni=+1lki,uki,Hk2=1i=1lki,uki xk,uk ni=+1lki,uki.通过以上分支规则,将矩形区域Hk剖分成两个子矩形Hk1和Hk2.为了方便起见,把H0的任意子整超矩形都记作Hk,记LBk是线性松弛规划问题(LRP(Hk)的最优值,xk是相对应的最优解.整超矩形的缩减规则问题(ILMP)中的所有线性不等式约束写成展开形式为:ni=1atixi bt,t=1,2,m.结合超矩形缩减技术29,考虑任一通过Hk=lk,uk所确定的子节点问题,其中lk=(lk1,lk2,lkn)T,uk=(uk1,uk2,ukn)T,lki是超矩形中第i维的左端点,uki是超矩形中第i维的右端点.给出本文的整超矩形的缩减规则:for t=1,2,m do begin计算rLt:=ni=1minatilki,atiuki;if rLt btthen停止,问题(ILMP)在Hk上没有可行解(Hk被删除);elsefor i=1,2,n doif ati 0 thenuki=minuki,btrLt+minatilki,atiukiati;if uki Zuki:=uki;else uki:=uki;endif;elseif ati 5,对每一个i 1,2,n,取cxi1=(b x1,b x2,b xi+1,dxi+1,cxn)T,cxi2=(b x1,b x2,b xi 1,dxi+1,cxn)T,令k=cxi1,cxi2.根据不等式约束Ax b,判断k中的整数点是否是问题(EILMP)的可行解,并将所有可行解置于W中,并置初始上界U0=minF(x,y):(x,y)W.步1.4置容忍度 0,迭代次数k=0;超矩形集合Q=.步2(迭代过程)步2.1(终止条件)若Uk Lk 5时,对每一个i 1,2,n,取cxi1kj=(b x1kj,b x2kj,b xikj+1,dxi+1kj,cxnkj)T,cxi2kj=(b x1kj,b x2kj,b xikj 1,dxi+1kj,cxnkj)T,令k=cxi1kj,cxi2kj.根据不等式约束Ax b,判断k中的整数点是否是问题(EILMP)的可行解,并将所有可行解置于W中.步2.7(超矩形删除)若L(Hkj)0,若算法迭代到第k次时,记U为问题(EILMP)当前的最优值,L(Hk)为问题(LRP(xk,yk)的最优值.如果Hk满足(Hk)p,那么U L(Hk).这里(Hk)=maxs=1,2,n|us ls|,=maxj=1,2,pj,=1vkjAj,=nCj,其中Cj=maxs=1,2,n|cjs|,j=1,2,p.第 1 期李敏敏等：一种整数线性乘积规划问题的分支定界算法7证 假设(xk,yk)是问题(LRP(xk,yk)的-全局最优解,这里yj=cTjx+dj,j=1,2,p.如果(xk,yk)是(EILMP(xk,yk)的可行解,根据U和L(Hk)的定义知U L(Hk)=pj=1jfj(y)hj(y)=pj=1jln(yj)ln(vkj)Aj(yj vkj).(4.1)根据微分中值定理可得:存在 vkj,hkj使得ln(yj)ln(vkj)=1(yj vkj),j=1,2,p.(4.2)因此,由(4.1),(4.2)可得U L(Hk)=pj=1j1(yj vkj)Aj(yj vkj)=pj=1j(1 Aj)(yj vkj)pj=1j(1vkj Aj)(ns=1|cjsuks cjslks|)pj=1j(1vkj Aj)nCj(Hk).结合已知(Hk)p,=1vkj Aj,=nCj,那么U L(Hk)pj=1(1vkj Aj)nCj(Hk).定理4.1证毕.定理 4.2假设(EILMP)问题的可行域是非空的,且矩形的剖分是耗尽的,则以下结论成立:(EILMP)问题的全局最优解将在算法迭代有限步终止时得到.证因为本文研究的是整数规划问题,故算法迭代在有限步终止,假设算法是在第k次迭代终止,k 0.根据算法的步1和步2.1得到Uk Lk.由步1和步2.8.1可知,等价问题(EILMP)存在可行解(x,y)使得Uk=F(x,y),因此有F(x,y)Lk.(4.3)假设v是等价问题(EILMP)的全局最优值,由下界的计算过程表明Lk v.(4.4)由于(x,y)是等价问题(EILMP)的可行解,有F(x,y)v.(4.5)联立式(4.3)-(4.5)得v F(x,y)Lk+v+,(4.6)所以,(x,y)是等价问题(EILMP)的全局最优解.定理4.2保证了当l u 0时线性松弛规划问题(LRP(Hk)无限地逼近于等价问题(EILMP),说明本文给出的分支定界算法是全局收敛的.8应用数学20245.数值实验以下给出几个例子证明本文算法的有效性.本文算法中所有的线性规划问题均选用对偶单纯形法求解,算法所有测试过程均用MATLAB9.2.0.538062(R2017a)在Inter(R)Core(TM)i5-8250U,CPU1.60GHz,4GB内存,64位Windows10操作系统的计算机上运行.算例 127min f(x)=(4x1 2x4+3x5+21)(4x1+2x2+3x3 4x4+4x5 3)(3x1+4x2+2x3 2x4+2x5 7)(2x1+x2 2x3+2x5+11)s.t.4x1+4x2+5x3+3x4+x5 25,x1 5x2+2x3+3x4+x5 2,x1+2x2+x3 2x4+2x5 6,4x2+3x3 8x4+11x5 8,x1+x2+x3+x4+x5 6,x1 1,x2 1,x3 1,x4 1,x5 1,x1,x2,x3,x4,x5 Z.通过本文的算法将算例1转化为以下等价问题(EILMP):min F(x,y)=pj=1jlnyj,s.t.yj=cTjx+dj,j=1,2,p,x X0H1,x Zn,y V1,其中H1=1,1,1,1,1;1,2,1,1,2T,V1=18,6,2,10;21,12,8,13T,图1中的 1 处的矩形为H1,下面构造线性规划松弛问题(LRP):Fl(x,y)=minpj=1j(lnh1j lnv1jh1j v1jyj+lnv1jlnh1j lnv1jh1j v1jv1j),s.t.yj=cTjx+dj,j=1,2,p,x X0H1,y V1.解线性规划问题(LRP),得出问题在第一个矩形H1上的下界8.9206,在第一个矩形H1上得到上界对应的最优解x1=1;2;1;1;1,最优值9.1595;再选择下界对应的矩形H1作为下次剖分的矩形,通过本文的剖分规则得到矩形H11=1,1,1,1,1;1,1,1,1,2T,H12=1,2,1,1,1;1,2,1,1,2T,图1中的 2 处的矩阵为H11,4 处的矩阵为H12;对H11进行缩减,在H11上计算的下界为9.2183,大于当前上界9.1595,H11被删除,此时在图1中对应的位置是 3,对H12进行缩减,在H11上计算的下界为9.1595,H12被删除,这样超矩形的集合T为空,松弛问题的目标值为9.1595,全局最优值为9.1595,最优解为x1=1;2;1;1;1,具体迭代过程如图1.第 1 期李敏敏等：一种整数线性乘积规划问题的分支定界算法9图1分支流程图算例 221,2628min(x1+x2)(x1 x2+7)s.t.2x1+x2 14,x1+x2 10,4x1+x2 0,2x1 x2 6,x1 2x2 6,x1 x2 3,x1 x2 0,x1+x2 7,x1 0,x2 0,x1,x2 Z.算例 321min(x1+x2+1)2.5(2x1+x2+1)1.1(x1+2x2+1)1.9s.t.x1+2x2 6,2x1+2x2 8,1 x1 3,1 x2 3,x1,x2 Z.算例 421min(3x1 2x2 2)23(x1+2x2+2)25s.t.2x1 x2 2,x1 2x2 2,x1+x2 5,3 x1 5,1 x2 3,x1,x2 Z.算例 521,2628min(cT1x+d1)(cT2x+d2)s.t.Ax b,x Z11.10应用数学2024这里,b=(81,72,72,9,9,9,8,8)T,d1=0,d2=0,c1=(1,0,19,0,0,0,0,0,0,0,0)T,c2=(0,1,19,0,0,0,0,0,0,0,0)T,A=9921000000081801000000188001000007110001000017100001000117000001001000000001001000000001.根据文28,我们可知算例5可被改写为:min(x1+1/9x3)(x2+1/9x3)s.t.9x1+9x2+2x3 81,8x1+x2+8x3 72,x1+8x2+8x3 72,7x1+x2+x3 9,x1+7x2+x3 9,x1+x2+7x3 9,0 x1 8,0 x2 8,0 x3 9,x1,x2,x3 Z.算例 6minT0j=1(cT0jx+d0j)0js.t.Ax b,x 0,1n,其中0j在区间0.01,1随机产生,c0j的每一个元素在区间-1,1随机产生;dj与c0j中的元素满足dj=ni=1|cij|+的关系式,其中是区间0,1的随机数;约束函数中系数矩阵A的每一个元素在区间0,1随机产生;bi与A中的元素满足bi=nj=1aij+2,其中是区间0,1的随机数.算例1-5的计算结果如表5.1所示,算法运行过程中的精度为104,得到最优值f(x)和最优解x.表5.2表示每个算例使用不同的算法得到的平均迭代次数(Iteration(次)和平均运行时间(Time(s).利用文21,26-28中的算法和本文算法进行比较,从总体看本文算法在5个算例上取得的最优值和最优解与其他算法的相同,证明了本文算法的有效性.从计算效果看,本文算法在算例1,算例3和算例4中无论是平均迭代次数还是平均运行时间上均取得了不错的效果,在算例2中本文算法的运行效果与其他算法相比相差不大.在算例5中本文算法无论是在平均迭代次数还是平均运行时间方面与其他算法相比较差.从总体看5个算例的数值结果证明了我们提出的算法是可行并且有效的.第 1 期李敏敏等：一种整数线性乘积规划问题的分支定界算法11表 5.1算例1-5利用本文算法产生的数值结果序号文献xf(x)1本文(1,2,1,1,1)9504.00001文27(1,2,1,1,1)9503.99992本文(2,8)10.00002文21(2,8)10.00002文26(2,8)10.00002文27(2,8)10.00002文28(1.9999998,7.9999988)10.00003本文(1,1)997.66133文21(1,1)997.66124本文(3,2)5.00934文21(3,2)5.00935本文(0,8,1,0,0,0,0,0,0,0,0)0.90125文21(0,8,1,0,0,0,0,0,0,0,0)0.90125文26(0,8,1,0,0,0,0,0,0,0,0)0.91205文27(0,8,1,0,0,0,0,0,0,0,0)0.90125文28(0,8,1,0,0,0,0,0,0,0,0)0.9012表 5.2算例 1-5 利用本文算法产生的数值结果序号文献迭代次数时间(秒)序号文献迭代次数时间(秒)1本文20.049332120.05441文2720.06914本文20.04912本文40.127042130.09442文2120.02525本文270.83772文2620.312552120.00032文2720.018252630.04692文28410.020052750.07433本文10.030852830.0000为了进一步证明我们的算法是有效的,对算例6进行了随机试验,计算结果呈现在表5.3和5.4中,下文也做出了相应的说明.由于目前求解整数规划的分支定界算法较少,本文通过Matlab自带的求解非线性规划的求解器fmincon来对比最优值进而证明算法的可行性,另外由于求解器无法求解整数规划问题,特在约束条件中加入x(1 x)=0的等式约束,确保求得的解为整数解.因此使用求解器fmincon和我们的算法对算例6同时进行计算,并将结果置于表5.3和5.4中,表中m表示约束条件的个数,n表示目标函数的维数,p表示目标函数中线性乘积项的个数,在表5.3中,在m和p不变n逐渐增大的情况下,m较小时,迭代次数与迭代时间明显增加,m较大时,迭代次数与迭代时间均无明显变化;当n和p固定,m不断增加时,迭代次数与迭代时间均无明显变化.而且,随着p的增加,迭代次数和迭代时间在m和n越小时趋于不变.另外,本文算法求得的最优值与求解器fmincon求得的完全相同,故表明我们的算法是有效的.在表5.4中,在m和n不变p逐渐增大的情况下,迭代次数和迭代时间基本保持不变.12应用数学2024表 5.3算例6利用本文算法产生的数值结果(m,n)p=3p=5p=7p=10(10,20)迭代次数平均值7.9500e+011.1150e+021.4970e+022.0150e+02迭代时间平均值2.9353e+004.1366e+005.4315e+007.3404e+0010次平均最优值3.7775e+013.6323e+021.1640e+044.1852e+04fmincon求得10次平均最优值3.7775e+013.6323e+021.1640e+044.1852e+04(20,20)迭代次数平均值5.2300e+011.5880e+021.9860e+023.7140e+02迭代时间平均值1.8982e+005.7483e+007.2208e+001.3543e+0110次平均最优值2.6467e+014.0478e+024.5157e+031.6122e+05fmincon求得10次平均最优值2.6467e+014.0478e+024.5157e+031.6122e+05(22,20)迭代次数平均值6.8900e+011.0590e+022.4600e+023.0450e+02迭代时间平均值2.5228e+003.8286e+008.9509e+001.1106e+0110次平均最优值2.8033e+017.7974e+021.2091e+041.0741e+05fmincon求得10次平均最优值2.8033e+017.7974e+021.2091e+041.0741e+05(20,30)迭代次数平均值2.5970e+021.3292e+031.4378e+034.2112e+03迭代时间平均值9.4665e+005.2570e+015.8565e+011.7997e+0210次平均最优值3.0402e+011.0516e+034.1813e+036.5860e+05fmincon求得10次平均最优值3.0402e+011.0516e+034.1813e+036.5860e+05(35,50)迭代次数平均值8.7515e+033.6985e+044.7234e+045.2139e+04迭代时间平均值4.4449e+021.6556e+032.1441e+032.4000e+0310次平均最优值2.6604e+024.2703e+034.4204e+053.9021e+07fmincon求得10次平均最优值2.6604e+024.2703e+034.4204e+053.9021e+07(45,60)迭代次数平均值2.0876e+044.9227e+045.2220e+045.2373e+04迭代时间平均值9.3083e+022.2369e+032.4000e+032.4000e+0310次平均最优值1.5119e+025.3143e+045.3358e+053.2814e+07fmincon求得10次平均最优值1.5119e+025.3143e+045.3358e+053.2814e+07(45,100)迭代次数平均值4.8142e+045.1092e+045.0821e+045.0875e+04迭代时间平均值2.2213e+032.4000e+032.4000e+032.4000e+0310次平均最优值1.6191e+021.3642e+054.3140e+072.0205e+10fmincon求得10次平均最优值1.6191e+021.3642e+054.3140e+072.0205e+10(60,100)迭代次数平均值4.6534e+045.0624e+045.0391e+045.0415e+04迭代时间平均值2.1872e+032.4000e+032.4000e+032.4000e+0310次平均最优值6.2269e+022.8618e+052.2395e+081.4784e+10fmincon求得10次平均最优值6.2269e+022.8618e+052.2395e+081.4784e+10(70,100)迭代次数平均值4.5808e+045.0167e+045.0129e+044.9047e+04迭代时间平均值2.1641e+032.4000e+032.4000e+032.4000e+0310次平均最优值6.3321e+024.9715e+041.2841e+061.2251e+09fmincon求得10次平均最优值6.3321e+024.9715e+041.2841e+061.2251e+09(70,120)迭代次数平均值5.0067e+044.5880e+044.8223e+044.5444e+04迭代时间平均值2.4000e+032.4000e+032.4000e+032.4000e+0310次平均最优值1.2445e+031.6502e+054.1202e+077.0000e+09fmincon求得10次平均最优值1.2445e+031.6502e+054.1202e+077.0000e+09(100,100)迭代次数平均值3.8704e+044.7423e+044.9857e+044.5484e+04迭代时间平均值1.8208e+032.4000e+032.4000e+032.4000e+0310次平均最优值3.1117e+028.5980e+043.9225e+074.1619e+09fmincon求得10次平均最优值3.1117e+028.5980e+043.9225e+074.1619e+09第 1 期李敏敏等：一种整数线性乘积规划问题的分支定界算法13表 5.4算例6利用本文算法产生的数值结果(m,n)p=20p=50p=100p=200(50,5)迭代次数平均值5.96.95.85.9迭代时间平均值0.22380.24290.20380.221310次平均最优值4.0441e+032.435e+125.1292e+203.9591e+43fmincon求得10次平均最优值4.0441e+032.435e+125.1292e+203.9591e+436.结论针对一般的整数线性乘积规划问题,本文基于对数函数的性质和单调性求解关于整数乘积的线性松弛问题.为了加速算法的收敛性,利用对数函数的性质和单调性进行松弛,以及结合区域缩减技术,通过剖分矩形区域并解决线性子问题,提出的算法最终收敛到原问题(ILMP)的全局最优解.在第五节数值实验中,证实了在求解(ILMP)问题时本文算法是有效并且可行的.参考文献:1 黄红连,梁治安.全局优化引论M.北京:清华大学出版社,2003.2 陈志平,徐宗本.计算机数学M.北京:科学出版社,2001.3 NOWAK I,VIGERSKE S.LaGO:a(heuristic)branch and cut algorithm for nonconvex MINLPsJ.Central European Journal of Operations Research,2008,16:127-138.4 FLIPPO O E,KAN A.A note on benders decomposition in mixed-integer quadratic programmingJ.Operations Research Letters,1990,9(2):81-83.5 BERGAMINI M L,GROSSMANN I,SCENNA N,et al.An improved piecewise outer-approximationalgorithm for the global optimization of MINLP models involving concave and bilinear termsJ.Computers and Chemical Engineering,2008,32(3):477-493.6 MATHUR K,SALKIN H M,MORITO S.A branch and search algorithm for a class of nonlinearknapsack problemsJ.Operations Research Letters,1983,2(4):155-160.7 KUNO T.Solving a class of multiplicative programs with 01 knapsack constraintsJ.Journal ofOptimization Theory and Applications,1999,103(1):121-135.8 陈志平,郤峰.求解中大规模复杂凸二次整数规划问题的新型分枝定界算法J.计算数学,2004,26(4):14.9 陈志平,李乃成,卻峰.解复杂二次整数规划问题的新型分枝定界算法J.工程数学学报,2004,21(3):371-376,416.10 GAO Y,XU C,WANG Y,et al.A new two-level linear relaxed bound method for geometric pro-gramming problemsJ.Applied Mathematics and Computation,2005,164(1):117-131.11 MARANAS C D,ANDROULAKIS I P,FLOUDAS C A,et al.Solving long-term financial planningproblems via global optimizationJ.Journal of Economic Dynamics and Control,1997,21(8-9):1405-1425.12 KONNO H,WATANABE H.Bond portfolio optimization problems and their applications to indextracking:A partial optimization approachJ.Journal of the Operations Research Society of Japan,2017,39(3):295-306.13 RAU N,LAYARD P,WALTERS A A.Microeconomic theoryJ.Economica,1980,47(186):211.14 DONNISH M C,SALINITIES N V.Global optimization algorithms for chip design and compactionJ.Engineering Optimization,1995,25(2):131-154.15 BENNETT K P,MANGASARIAN O L.Bilinear separation of two sets in n-spaceJ.ComputationalOptimization and Applications,1993,2(3):207-227.14应用数学202416 MULVEY J M,VANDERBEI R J,ZENIOS S A.Robust optimization of large-scale systemsJ.Operations Research,1995,43(2):264-281.17 MATSUI T.NP-hardness of linear multiplicative programming and related problemsJ.Journal ofGlobal Optimization,1996,9(2):113-119.18 SHAO L,EHRGOTT M.Primal and dual multi-objective linear programming algorithms for