搜索
Lecture2:Branch-and-BoundMethod(3units)OutlineILinearprogramISimplexmethodIDualoflinearprogrammingIBranch-and-boundmethodISoftwareforintegerprogramming1/32LinearProgramIRecallthatthestandardformofLP:mincTxs:t:Ax=bx¸0wherec2Rn,Aisanm£nmatrixwithfullrowrank,b2Rm.IApolyhedronisasetoftheformfx2RnjBx¸dgforsomematrixB.ILetP2Rnbeagivenpolyhedron.Avectorx2PisanextremepointofPiftheredoesnotexisty;z2P,and¸2(0;1)suchthatx=¸y+(1¡¸z).2/32BasicSolutionsandExtremePointsILetS=fx2RnjAx=b;x¸0g,thefeasiblesetofLP.SinceAisfullrowrank,ifthefeaisblesetisnotempty,thenwemustm·n.WLOG,weassumethatmn.ILetA=(B;N),whereBisanm£mmatrixwithfullrank,i.e.,det(B)6=0.Then,Biscalledabasis.ILetx=µxBxN¶.WehaveBxB+NxN=b.SettingxN=0,wehavexB=B¡1b.x=µB¡1b0¶iscalledabasicsolution.xBiscalledbasicvariables,xNiscallednonbasicvariables.IIfthebasicsolutionisalsofeasible,thisis,B¡1b¸0,thenx=µB¡1b0¶iscalledabasicfeasiblesolution.3/32BasicSolutionsandExtremePointsI^x2SisanextremepointofSifandonlyif^xisabasicfeasiblesolution.ITwoextremepointsareadjacentiftheydi®erinonlyonebasicvariable.I(BasicTheoremofLP)ConsiderthelinearprogramminfcTxjAx=b;x¸0g.IfShasatleastoneextremepointandthereexistsanoptimalsolution,thenthereexistsanoptimalsolutionthatisanextremepoint.IProof(representationofpolyhedron)IThefeasiblesetofstandardformlinearprogramhasatleastoneextremepoint.ITherefore,weclaimthattheoptimalvalueofalinearprogramiseither¡1,orisattainedanextremepoint(basicfeasiblesolution)ofthefeasibleset.4/32AnaivealgorithmforlinearprogrammingILetminfcTxjAx=b;x¸0gbeaboundedLPIEnumerateallbasesB2f1;:::;;ng,µmn¶=O(nm)manyIComputeassociatedbasicsolutionx=µB¡1b0¶IReturntheonewhichhaslargestobjectivefunctionvalueamongthefeasiblebasicsolutionsIRunningtimeisO(nm¢m3)!!!IAretheremoree±cientalgorithms?5/32SimplexmethodISimplexmethodwasinventedbyGeorgeDantzig(19142005)(fatheroflinearprogramming)ISupposewehaveabasicfeasiblesolution^x=µB¡1b0¶,A=(B;N).ILetx2SbeanyfeasiblesolutionoftheLP.Letx=µxBxN¶,c=µcBcN¶.ThenBxB+NxN=bandsoxB=B¡1b¡B¡1NxNcTx=cTBxB+cTNxN=cTBB¡1b¡cTBB¡1NxN+cTNxN=cT^xT+(cTN¡cTBB¡1N)xNILetrN=cTN¡cTBB¡1N(calledreducedcost).IfrN¸0,thencTx¸cT^xTandthecurrentextremepoint^xisoptimal6/32SimplexmethodIOtherwise,theremustexistanri0,wecanletcurrentnonbasicvariablexibecomeabasicvariablexi0(enteringvariable).ISuitablychoosingbasicvariabletobecomeanonbasicvariable(leavingvariable),wecangetanewbasicfeasiblesolutionwhoseobjectivevalueislessthanthatofthecurrentbasicfeasiblesolution^x.IGeometrically,theabovemethod(simplexmethod)movesfromoneextremepointtooneofitsadjacentextremepoint.ISincethereareonlya¯nitenumberofextremepoints,themethodterminates¯nitelyatanoptimalsolutionordetectsthattheproblemisinfeasibleoritisunbounded.7/32GeometryofSimplexMethodFigure:Simplexmethod8/32SimplexmethodIStep0:ComputeaninitialbasisBandthebasicfeasiblesolution:x=µB¡1b0¶.IStep1:IfrN=cTN¡cTBB¡1N¸0,stop,xisanoptimalsolution,otherwisegotoStep2.IStep2:ChoosejsatisfyingcTj¡cTBB¡1aj0,if¹aj=B¡1aj·0,stop,theLPisin¯nite;otherwise,gotoStep3.IStep3.Computethestepsize:¸=minf¹bi¹aijj¹aij0g=¹br¹arj¸0:Letx:=x+¸dj,wheredj=µ¡B¡1ajej¶.GotoStep1.9/32SimplexTableauxBxNrhsBNbcTBcTN0=)xBxNrhsIB¡1NB¡1b0cTN¡cTBB¡1N¡cTBB¡1b10/32Simplexmethod:AnexampleIConsiderthefollowingLP:min¡7x1¡2x2s:t:¡x1+2x2+x3=4;5x1+x2+x4=20;2x1+2x2¡x5=7;x¸0:ITheinitialtableauisx1x2x3x4x5rhs¡12100451010202200¡17¡7¡2000011/32IChoosetheinitialbasis:B=(a1;a3;a4),basicvariable:xB=(x1;x3;x4)T.Thesimplextableauis:x1x2x3x4x5rhs0310¡127120¡4012122121100¡123120500¡722412IThebasicfeasiblesolutionis:xB=(x1;x3;x4)T=(312;712;212)T.Since¡720,choosex5astheenteringvariable,¸=212212=1,sox4isleavingvariable,thenewbasicvariableisxB=(x1;x3;x5).Thenewtableauisx1x2x3x4x5rhs0115115080¡8502511115015040¡5307502812/32IChoosex2astheenteringvariable,compute¸=minf811=5;41=5g=4011.x3istheleavingvariable,thenewtableauis:x1x2x3x4x5rhs0151111104011008116111751110¡11121103611003111611030211SincerN=(311;1611)¸0,thecurrentbasicfeasiblesolutionx=(3611;4011;0;0;7511)Tistheoptimalsolutionwithoptimalvalue:¡30211.13/32Dualtheory:motivationIConsiderthefollowingminimizationproblemwithasingleequalityconstraint:(P)minf(x)s:t:h(x)=0;x2X;whereh(x)=0isahardconstraintandx2Xisa\easyconstraint.IHowcouldwesolvethisproblem?Theideaistorelaxthehardconstrainth(x)=0andsolveaneasierproblem.IThiscanbedonebyincorporatingtheconstraintintotheobjectivefunction.Apriceisassociatediftheconstraintisviolated.14/32IGivenaLagrangianmultiplier¸(price),theLagrangiandualfunctionde¯nedbyd(¸)=minx2XL(x;¸):=f(x)+¸h(x)givesalowerboundfor(P):d(¸)·f(x);8feasiblesolutionof(P):IThebestlowerboundisfoundbysolving(D)max¸d(¸):I(D)iscalledtheLagrangiandualproblemof(P).15/32DualofLinearProgramIConsiderthestandardLP:(LP)mincTxs:t:Ax=b;x¸0;IAssociatemultipliers¸2RmtoAx=b,thedualfunctionisd(¸)=minx¸0fcTx+¸T(b¡Ax)g=bT¸+minx¸0(c¡AT¸)Tx=½bT¸;ifAT¸·c¡1;otherwiseISo,thedualproblemis(LD)maxbT¸s:t:AT¸·c:16/32InequalityConstraintsIConsiderthestandardLP:(LP)mincTxs:t:Ax¸b;x¸0;IAddingslackvariabless¸0,weget(A;¡I)µxs¶=b:IThisleadstodualconstraints(A;¡I)T¸·µc0¶: