Optimization models for operative planning in drin

Konrad-Zuse-Zentrumfu¨rInformationstechnikBerlinTakustraße7D-14195Berlin-DahlemGermanyJENSBURGSCHWEIGER,BERNDGNA¨DIG,ANDMARCC.STEINBACHOptimizationModelsforOperativePlanninginDrinkingWaterNetworksZIB-Report04-48(December2004)OPTIMIZATIONMODELSFOROPERATIVEPLANNINGINDRINKINGWATERNETWORKSJENSBURGSCHWEIGER,BERNDGNA¨DIG,ANDMARCC.STEINBACHABSTRACT.Thetopicofthispaperisminimumcostoperativeplanningofpressurizedwatersupplynetworksoverafinitehorizonandunderreliabledemandforecast.Sincethisisaveryhardproblem,itisdesirabletoemploysophisticatedmathematicalalgorithms,whichinturncallsforcarefullydesignedmodelswithsuitableproperties.Thepaperde­velopsanonlinearmixedintegermodelandanonlinearprogrammingmodelwithfavorablepropertiesforgradient-basedoptimizationmethods,basedonsmoothcomponentmodelsforthenetworkelements.Incombinationwithfurthernonlinearprogrammingtechniques(tobereportedelsewhere),practicallysatisfactorynear-optimumsolutionsevenforlargenetworkscanbegeneratedinacceptabletimeusingstandardoptimizationsoftwareonaPCworkstation.SuchanoptimizationsystemisinoperationatBerlinerWasserbetriebe.0.INTRODUCTIONMunicipalwatersupplysystemsconstituteacentralpartofthepublicinfrastructureandcausesubstantialcosts,bothinmonetaryandenergeticterms.Avoidingunnecessarycon­sumptionofresourcesisthereforedesirableforeconomicalaswellasecologicalreasons.Toachievethisgoal,model-baseddecisionsupporttoolsbecomeincreasinglyimportant.Theprincipalplanningtasksincludeoptimalnetworkdesigntoreduceinvestmentcostsandoptimalnetworkoperationtominimizerunningcosts.Thesubjectofthispaperisnetworkoperation.Themathematicalproblemofoperativeplanningishardbecauseitinvolvesbothdiscreteandcontinuousdecisions,inadditiontothecomplexitycausedbyclose-meshednetworksandtemporalcouplingovertheentireplanninghorizon.Fromapracticalviewpoint,thismakesitdifficulttogeneratesufficientlyaccurateandreliableso­lutionsinacceptabletime.Toachieveareasonablecompromisebetweenmodelaccuracyandcomputationtimes,thedevelopmentofappropriatemodelsforadvancedoptimizationmethodsisimportant.Becauseoftheenormouscomplexityoftheoperativeplanningtask,earlymathematicalapproachestypicallyrelyonsubstantiallysimplifiednetworkhydraulics(bydroppingallnonlinearities,forinstance)[13,14,18,32,39],whichisoftenunacceptableinpractice.Otherauthorsemploydiscretedynamicprogramming[8,9,11,29,31,41],whichismath­ematicallysoundbutonlyapplicabletosmallnetworksunlessspecificpropertiescanbeexploitedtoincreaseefficiency.Optimizationmethodsbasedonnonlinearmodels(mostlyforthepumpsonly)arereportedin[3,10,12,24,36].Theseapproachesemploycompu­tationallyexpensivemeta-heuristicsorsufferfrominefficientcouplingofgradient-basedoptimizationwithnon-smoothsimulationbyexistingnetworkhydraulicssoftware,suchasEPANET[35].Morerecentrelatedworkaddressesmodelingandoptimizationfornetworksofirrigationandsewagecanalsorforgasnetworks,see,e.g.,[19,23,28,38].Notefinallythatthehydraulicequationsalreadyhaveanintrinsicoptimizationstructure[1];quitegen­eralmathematicalformulationstogetherwithexistence,uniqueness,andsensitivityresultscanbefoundin[16,17].2000MathematicsSubjectClassification.90B10,90C06,90C11,90C30,90C59,90C90.Keywordsandphrases.Drinkingwatersupply,distributionnetwork,minimumcostoperativeplanning,con­tinuoustimemodel,mixedintegermodel,nonlinearprogrammingmodel.1J.BURGSCHWEIGER,B.G,ANDM.C.STEINBACHFIGURE1.Schematicdiagramsofwaterworkswithtanks(typeI;left)andwithouttanks(typeII;right)Thecurrentpaperaddressesdetailedandcomprehensivemodelsthataresuitedforgradient-basednonlinearoptimizationofdailynetworkoperationsunderreliabledemandforecasts.Thesemodelspossesscertainfavorablesmoothnessandregularityproperties.Togetherwithfurtherworkbytheauthors[4,5,7,20,21],theyprovidethebasisforanoptimizationmodulethatisinoperationatBerlinerWasserbetriebe(BWB)forminimumcostoperativeplanningofintegratedrawwaterandpurewatermanagementinthemu­nicipaldrinkingwaternetwork.Ourmodelsaregenericinthattheyareapplicabletoanypressurizedwatersupplynetworkconsistingofsimilarelements.Toaddconcreteness,however,wewilloftenrefertotheBWBnetwork.Thepaperisorganizedasfollows.Section1outlinestheoverallstructureandopera­tionofurbanwatersupplynetworks.Section2thendevelopsadetailedandcomprehen­sivephysicalmodelfordynamicnetworkoperationincontinuoustime,withemphasisonsmoothapproximationsofthehydraulicpressurelossinpipesandoftheaggregateeffi­ciencyofpumpingstations.Thismodelcoversbasicwaterhydraulics[15,26,30].InSection3weconsiderthefulloperativeplanningproblemwithbinaryandcontinuousde­cisionsindiscretetime,providingbothageneralizeddisjunctiveprogramming(GDP)andamixedintegernonlinearprogramming(MINLP)formulation.Indevelopingthelatterweavoidintroducingadditionalnonlinearitiesorundesirablebig-Mtermsandensurethattherelaxationsarenondegenerate.Sinceafullmixed-integeroptimizationisimpracticalforlargenetworksasinBerlin,wefinallypresentabasicnonlinearprogramming(NLP)modelinSection4which,incombinationwithspecialtechniquesaddressingthebinarydecisions[7],isactuallysuitedforpracticalcomputations.AtB