Branch-and-Bound-ppt

BranchandBoundAlgorithmDr.HuQin2014October1ExhaustiveEnumeration(完全枚举法完全枚举法完全枚举法完全枚举法)
Knapsackproblem(背包问题背包问题背包问题背包问题)whereciisthebenefitobtainedifitemiischosen,bistheamountofanavailableresource,andaiistheamountoftheavailableresourceusedbyitemi.2ExhaustiveenumerationisalsocalledBrute-forcesearch.Thenumberofpossiblesolutionsis2n,wherenisthenumberofvariables.ExhaustiveSearchTree3•Thecirclesarecallednodes,andthelinesarecalledbranches.•Attheverytopofthetree,wehavetherootnode.•Aswedescendthetree,decisionsaremadeasindicatedbythenumberonthebranches.•Anegativenumber,-j,impliesthatthevariablexjhasbeensetequalto0,whereasapositivenumber+j,impliesxjhasbeensetequalto1.
Atanynodethatisnotaleaf,somevariable,calledtheseparationvariable,isfixedatitstwopossiblevaluesatthenextlevel.
Thesetofsolutionsatthecurrentnodeisdividedintotwomutuallyexclusivesubsetsbythisoperation.
Choosingaseparationvariableandmovingtothenextleveliscalledbranching,becausethisishowthebranchesofthetreeareformed.
Branchingstrategy(i.e.,chooseavariableforbranching)andsearchstrategy(e.g.,depth-first).4BranchandBoundAlgorithm
Elementarybutimportantobservation:IfyousolvetheLPrelaxationofapureIPandobtainasolutioninwhichallvariablesareintegers,thentheoptimalsolutiontotheLPrelaxationisalsotheoptimalsolutiontotheIP.5TheoptimalsolutiontotheLPrelaxationofthispureIPisx1=0,x2=6,z=12.6ThefeasibleregionfortheIPisasubsetofthepointsintheLPRelaxation’sfeasibleregion.AssumetheoptimalsolutionsofIPandLPrelaxationareZIPandZLP,sowemusthaveZIP≤ZLP.(Maximizationproblem)•Z=ZLP•x1=0,x2=6isafeasibleintegersolution,soZ≤ZIP.•Z≤ZIP≤ZLP=Z•SowemusthaveZ=ZIPBranch
ForanIP,wecangraduallydecomposeitintoaseriesofsmallerIPproblemsExample:Ifx1isabinaryvariable,thenwemayhavetwosmallproblems,IP1andIP2:InIP1,fixingx1=0.SupposeZIP1istheoptimalsolutionInIP2,fixingx1=1.SupposeZIP2istheoptimalsolutionZIP=max(ZIP1,ZIP2)7Bound
SupposewehavesolvedIP1andgotZIP1
ConsiderIP2:FortheLPRelaxationofIP2,ZLP2canbeobtainedIfZLP2≤ZIP1,wedonotneedtosolveIP2Reason:ZIP2≤ZLP2≤ZIP1,soZIP1mustbetheoptimalsolutiontotheoriginalIPThisiscalledBOUND
ForeachsmallerIP,wecansolveitsLPrelaxationandseeifwecanfathomitdirectly,meaningthatwewillnolongerneedtosolveit8GeneralApproachofB&BSupposewehaveafeasiblesolutionoftheIPathand,theobjectivefunctionvalueiszBzBisalowerboundoftheproblemConsideringasmallIPproblem:Case1:TheLPrelaxationhasnofeasiblesolutionTheIPhasnofeasiblesolutioneither.Case2:IntheLPrelaxation,ZLP≤ZBTheIPcannothaveabettersolutionthanZB,thuscanbefathomedCase3:IntheLPrelaxation,anintegeroptimalsolutionisfound,andZLPZBThissmallIPissolved,andupdateZB=ZLPCase4:IntheLPrelaxation,anoptimalsolutionisfoundwithZLPZB,butnotintegervalueDecomposetheIPintomoresmallerIPproblems–morebranches910
WecalltheLPrelaxationoftheoriginalproblemsubproblem1.
TheoptimalsolutiontotheLPrelaxationisz=165/4,x1=15/4,x2=9/4.
Thisimpliesthattheoptimalz-valuefortheIPcannotexceed165/4.
Theoptimalz-valuefortheLPrelaxationisanupperboundforTelfa’sprofit.11
PartitioningthefeasibleregionfortheLPrelaxation.
WearbitrarilychooseavariablethatisfractionalintheoptimalsolutiontotheLPrelaxation—sayx1.
EverypointinthefeasibleregionfortheIPmusthaveeitherx1≤3orx1≥4.
Branchonthevariablex1andcreatethefollowingtwoadditionalsubproblems:Subproblem2:Subproblem1+Constraintx1≥4.Subproblem3:Subproblem1+Constraintx1≤3.12BranchandBoundTree13Thelabeltindicatesthechronologicalorderinwhichthesubproblemsaresolved.
Theoptimalsolutiontosubproblem2didnotyieldanintegersolution,sowechoosetousesubproblem2tocreatetwonewsubproblems.
Webranchonx2byx2≥2andx2≤1,whichcreatesthefollowingtwosubproblems:Subproblem4:Subproblem1+Constraintsx1≥4andx2≥2=subproblem2+constraintx2≥2.Subproblem5:Subproblem1+Constraintx1≥4andx2≤1=subproblem2+constraintx2≤1.14
Subproblem4(ornode4)isfathomedsinceitisinfeasible.15
Theoptimalsolutiontosubproblem5ispointI:z=365/9,x1=40/9,x2=1.
Partitionsubproblem5by:Subproblem6:Subproblem5+Constraintx1≥5Subproblem7:Subproblem5+Constraintx1≤41617
Optimalsolutiontosubproblem7ispointH:z=37,x1=4,x2=1,whichisafeasiblesolutiontotheoriginalIP.
Subproblem7hasbeenfathomed.
Wemayconcludethattheoptimalz-valuefortheIP≥37.
37isalowerboundontheoptimalz-valuefortheoriginalIP.181920•TheoptimalsolutiontotheIPisforTelfatomanufacture5tablesand0chairs.•Thissolutionwillcontribute$40toprofits.B&BforMachineScheduling
Fourjobsmustbeprocessedonasinglemachine.
Thetimerequiredtoprocesseachjobandthedatethejobisdueareshowninthefollowingtable.
Thedelayofajobisthenumberofdaysaftertheduedatethatajobiscompleted(ifajobiscompletedontimeorearly,thejob’sdelayiszero).
Inwhatordershouldthejobsbeprocessedtominimizethetotaldelayofthefourjobs?21
Supposethejobsareprocessedinthefollowingorder:job1,job2,job3,andjob4.
Thenthedelaysshowninthefollowingtablewouldoccur.
Forthissequence,totaldelay=0+6+3+7=16days.22
Becauseapossiblesolutiontotheproblemmustspecifytheorderinwhichthejobsareprocessed,wedefine:xij=1ifjobiisthej-thjobtobeprocessedand=0otherwise.
Thebranch-and-boundapproachbeginsbypartitioningallsoluti