基于Branch-Bound方法MIQP问题的求解及应用

Vol.15No.4JOURNALOFSYSTEMSIMULATIONApril2003•488•Branch&BoundMIQP1,221(1310014;2310027)Branch&BoundB&BMixedIntegerQuadraticProgramming,MIQPB&BMIQPB&BQPmax,QPMIQPMATLABMIQPBranch&BoundMIQP1004-731X(2003)04-0488-04O17ABranch&BoundBasedSolutionofMIQPProblemandItsApplicationZHANGJu1,2,LIPing2,WANGWan-liang1(1InstituteofAutomation,ZhejiangUniversityofTechnology,Hangzhou310014,China)(2InstituteofIndustrialProcessControl,ZhejiangUniversity,Hangzhou310027,China)Abstract:Branch&Bound(B&B)basedsolutionofMixedIntegerQuadraticProgramming(MIQP)problemanditsapplicationintheoptimalcontrolofaclassofhybridsystemsarestudiedinthispaper.TheprocedureoffindingtheoptimalsolutionofMIQPproblemcanberepresentedgraphicallyastheexplorationofabinarytree.Twomainaspects,whichaffecttheefficiencyoftheB&Balgorithm,arebranchrulesandtreeexplorationstrategies.ByintroducingQPmax,whichspecifiesthemaximumnumberofQPproblemsallowedtobesolvedduringexploration,suboptimalsolutionsoftheMIQPproblemcanbeobtainedwithinashortcomputationtime.AnMATLABprogramisdevelopedasanMIQPproblemsolver,andsimulationsaremadewhenappliedtotheoptimalcontrolofaclassofhybridsystems.Keywords:branch&boundalgorithm;MIQPproblem;hybridsystem;optimalcontrol1[1][2][3]NP-hardGBDGeneralizedBendersDecomposition,OAOuterApproximationBranch&Bound[4][5][6]MIQPMIQPNP-hardMIQP,B&B2002-05-182002-08-13(1973-),,,,,;(1954-),,,;(1955-),,B&BMIQPB&BMIQPMIQPQPB&BQPmax,QPMIQPMATLABMIQP1B&BMIQPMIQP1:gmingggFH′+′s.t.⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎨⎧∈∈⎥⎥⎦⎤⎢⎢⎣⎡==≤nddnccdceqeqineqineqRbAbA}1,0{ggggggg(1)gmingggFH′+′s.t.⎪⎪⎪⎩⎪⎪⎪⎨⎧∈∈⎥⎦⎤⎢⎣⎡==≤nddnccdceqeqineqineqRRbAbAggggggg(2)Vol.15No.4April2003,Branch&BoundMIQP•489•(1)(QuadraticProgramming,QP)(2):(1)0110B&BMIQPgdgMIQPQPQPMIQPQPMATLABOptimizationToolboxQPB&BMIQPnd},1,0{*∈xdgxQPxdgQPx*[0,1]MIQP0x[]444344421nd*......**0=x0x0xQP2MATLABQPQP2RgRf2∞=RfMIQPRgRgdg01RgMIQPRg0xQP0xQP0x010x,1x2x1[][]44344214434421ndnd*...*1**...*0*2,1==xx1xQP(3)gmingggFH′+′s.t.⎪⎪⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎧=∈=∈∈⎥⎥⎦⎤⎢⎢⎣⎡==≤-,...)4,3(#)(#0)2()1(2nddddnccdceqeqineqineqRRRbAbAggggggggg(3)2xQP(4)gmingggFH′+′s.t.⎪⎪⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎧=∈=∈∈⎥⎥⎦⎤⎢⎢⎣⎡==≤-,...)4,3(#)(#1)2()1(2nddddnccdceqeqineqineqRRRbAbAggggggggg(4)(3)(4)QP23MIQPxQP2B&BMIQPB&BMIQP10xQPQP[]∞∞∞=+∞=...,optgoptfQPmax,QP2QPQPQPmaxoptf,optgsuboptf,suboptg+∞==optf+∞==suboptfMIQP3QPQPQPQP4QPRfRg54QP1)QPQPQPQP22)optRff≥QPQPoptfQP23)optRff≤QPMIQPRoptRffoptgg==,24)optRff≤623MIQPVol.15No.4April2003•490•6QPQPQP2B&BMIQPQP121-+nd512QPoptRff≥QPQPB&BMIQPB&BMIQPMIQPMIQPQPB&BB&B63MIQPB&B(1)FirstFreeVariable,x2(2)FractionalPartBasedx01MIQPB&B(1)B&BQP3a(2)3b(3)QPQPB&BMIQPMATLAB3a3bQPQP3MLDMIQP[1]B&BMIQP[1]1,]'2,2[0-=x,,xf]'00[=]1,1[)(-∈tuT=7.MIQP7dn=7(4a-4c)QPmax4cMIQP4a4b4c412,QPmax,]'2,2[0-=x,,xf]'11[-=]3,3[)(-∈tuT=1053,264,27TrajectoryofAuxiliaryLogicalVariable(0,1)210-1-2OptimalTrajectoryofu(t)OptimalTrajectoryofSystemStatesX(t),X(0)=[-2,2]’01234567Timet(T=7)0.40-0.4-0.80123456Timet(T=7)210-101234567Timet(T=7)Vol.15No.4April2003,Branch&BoundMIQP•491•5QPmax6741)B&BMIQPB&BMIQP2)B&B(QPmax)3)MIQPQPmaxQPQPmaxQPmax4)MATLABMIQPMIQP5)B&B6)[5]MIQPMIQPB&B:[1]BemporadA,MorariM.ControlofSystemsIntegratingLogic,DynamicsandConstraints[J].Automatica,1999,35:407-427.[2]NottHP,LeePL.Anoptimalcontrolapproachforschedulingmixedbatch/continuousprocessplantswithvariablecycletime[J].ComputerandChemicalEngineering,1999,23:907-917.[3].[M].:,1998.[4]FloudasCA.Nonlinearandmixed-integeroptimization[M].Oxford:UniversityPress,1995.[5]LinoCosta.PedroOliveira.Evolutionaryalgorithmsapproachtothesolutionofmixedintegernon-linearprogrammingproblems[J].ComputerandChemicalEngineering,2001,25:257-266.[6]CardosoM.F.,SalcedoR.L.,FeyodeAzevedos.,&BarbosaD.,AsimulatedannealingapproachtothesolutionofMINLPproblems[J].ComputerandChemicalEngineering,1997,20:1065-1080.487(13)2,4/[1]SongXQ,LiuQ,SunZK.Trackingamaneuveringtargetwithmultisensor[J].SPIE,1997,3067:206-210.[2],.[J].,1998,(9):134-138.[3]ShettyS,AlouaniAT.Amultisensortrackingsystemwithanimage-basedmaneuverdetector[J].IEEEtransonAerospaceandElectronicsystems.1996,32(1):167-185.[4]SundareshanMK.Neuralnetworkschemesfordatafusionandtrackingofmaneuveringtargets[Z].ONRGrant#N00014-95-1-1224.1-47.Z(km)86420Y(km)0510152()