分支-切割法的框架及收敛性(精)

293Vol.29,No.320089JournalofHebeiUniversityofScienceandTechnologySept.2008:1008-1542(2008)03-0185-03-王艳红,张文娟(西安工业大学数理系,陕西西安710032):在解决各类整数规划问题时,分支-切割法是一个非常成功的方法,并且它能保证给出一个最优解从一个简单例子出发引出分支-切割算法的思想,从而给出其算法框架,并对其收敛性进行分析:分支-切割;混和整数线性规划;分支;割平面:O221.4:AFrameworkandconvergenceofbranch-and-cutalgorithmsWANGYan-hong,ZHANGWen-juan(DepartmentofMathematicsandPhysics,Xi'anTechnologicalUniversity,XianShaanxi710032,China)Abstract:Branch-and-cutmethodsareverysuccessfultechniquesforsolvingawidevarietyofintegerprogrammingproblems,andtheycanprovideaguaranteeoptimality.Inthispaper,wederivethethoughtofbranch-and-cutalgorithmsfromasimpleexample,givingtheframeworkofthealgorithmsandanalyzingifthealgorithmsconvergeornot.Keywords:branch-and-cut;mixedintegerlinearprogramming;branch;cuttingplane:2008-03-24;::(1981-),,,,,-2[1,2],-[3]1(ILP)[4]:minz=-6x1-5x2,s.t.3x1+x211,-x1+2x25,x1,x20,,,,,22,?,,11,(3,2),z=-283,,,,图1一个二维整数规划问题的分支-切割算法过程Fig.1Branch-and-cutalgorithmprocessofatwo-dimensionalintegerprogrammingproblem2mincTx,s.t.Axb,x0,xi,i=1,,pxcn;bm;Amn,p,p=n,01,,[5]-1):MILP0z=+,lL,z-l=-2):L=,x*z-,x*,MILP3):LMILPl4):MILPl,z-l=+,6,,z-l,xlR;z-l=-5):,,xlR;,46):(a)z-lz-,2;(b)z-lz-xlR,z=z-l,Lz-lz-,27):sljj=kj=1MILPlslLMILPljj=kj=1,MILPljMILPlslj,z-lj(j=1,2,,k)lz-l2-L-MILPz-,MILP,,z-l,LPz-l[6],5,,7,MILPl,:xia,xia+1,xia,[7],,,5,,,,1862008,,,MILP,-,-3--123MILP,,,123,11MILP,-,12,,,-,MILP3-,(,,),-MILP,x*,MILP4-,,-,,,-,,:[1].[M]..:,1990.[2]CHRISTOSHP,KENNETHS.CombinatorialOptimization:AlgorithmsandComplexity[M].Canada:GeneralPublishingCompany,1998.[3]PARDALOSPM.HandbookofAppliedOptimization[M].Oxford:OxfordUniversityPress,2000.[4]JOHNEM.Branch-and-cutalgorithmsforcombinatorialoptimizationproblem[J].MathematicalSciences,1999,23:166-168.[5]BALASE,CERIAS,CORNUEJOLSG.Mixed0-1programmingbylift-and-projectinabranch-and-cutframework[J].ManagementScience,1996,42:1229-1246.[6]NEMHAUSERGL,SAVELSBERGHMWP,SIGISMONDIGC.Amixedintegeroptimizer[J].OperationsResearchLetters,1994,15:47-58.[7]JUNGERM,THIENELS.Introductiontoabacus-abranch-and-cutsystem[J].OperationsResearchLetters,1998,22:83-95.向本期载文的审稿专家致谢20,(,,),,():白志明陈廷陈薇陈一鸣崔洪斌范松川李法朝李荣平刘守信任军号任世伟孙晓云唐瑞增汪国昭王坤许永兵岳峰翟建华翟学良()1873-