基于混合线性整数规划机组组合的有效计算方法

IEEETRANSACTIONSONPOWERSYSTEMS,VOL.21,NO.3,AUGUST20061371AComputationallyEfficientMixed-IntegerLinearFormulationfortheThermalUnitCommitmentProblemMiguelCarrión,StudentMember,IEEE,andJoséM.Arroyo,SeniorMember,IEEEAbstract—Thispaperpresentsanewmixed-integerlinearformulationfortheunitcommitmentproblemofthermalunits.Theformulationproposedrequiresfewerbinaryvariablesandconstraintsthanpreviouslyreportedmodels,yieldingasignificantcomputationalsaving.Furthermore,themodelingframeworkprovidedbythenewformulationallowsincludingaprecisedescriptionoftime-dependentstartupcostsandintertemporalconstraintssuchasrampinglimitsandminimumupanddowntimes.Acommerciallyavailablemixed-integerlinearprogram-mingalgorithmhasbeenappliedtoefficientlysolvetheunitcommitmentproblemforpracticallarge-scalecases.Simulationresultsbacktheseconclusions.

IndexTerms—Mixed-integerlinearprogramming(MILP),thermalgeneratingunits,unitcommitment.

NOMENCLATURE

ConstantsCoefficientofthepiecewiselinearproductioncostfunctionofunitj.Coefficientsofthequadraticproductioncostfunctionofunitj.Coefficientsofthestartupcostfunctionofunitj.

Shutdowncostofunitj.Loaddemandinperiodk.Minimumdowntimeofunitj.Slopeofblockofthepiecewiselinearproductioncostfunctionofunitj.Numberofperiodsunitjmustbeinitiallyonlineduetoitsminimumuptimeconstraint.Costoftheintervaltofthestairwisestartupcostfunctionofunitj.Numberofperiodsunitjmustbeinitiallyofflineduetoitsminimumdowntimeconstraint.Numberofintervalsofthestairwisestartupcostfunctionofunitj.Numberofsegmentsofthepiecewiselinearproductioncostfunctionofunitj.Capacityofunitj.ManuscriptreceivedNovember15,2005;revisedJanuary31,2006.ThisworkwassupportedinpartbytheMinistryofEducationandScienceofSpainunderGrantCICYTDPI2003-01362andinpartbytheJuntadeComunidadesdeCastilla—LaMancha,Spain,underGrantPBI-05-053.Paperno.TPWRS-00717-2005.TheauthorsarewiththeDepartamentodeIngenieríaEléctrica,Elec-trónica,AutomáticayComunicaciones,E.T.S.I.Industriales,UniversidaddeCastilla—LaMancha,CiudadRealE-13071,Spain(e-mail:miguel.car-rion@uclm.es;josemanuel.arroyo@uclm.es).DigitalObjectIdentifier10.1109/TPWRS.2006.876672Minimumpoweroutputofunitj.Spinningreserverequirementinperiodk.Ramp-downlimitofunitj.Ramp-uplimitofunitj.Numberofperiodsunitjhasbeenofflinepriortothefirstperiodofthetimespan(endofperiod0).Shutdownramplimitofunitj.Startupramplimitofunitj.Numberofperiodsofthetimespan.Upperlimitofblockofthepiecewiselinearproductioncostfunctionofunitj.Numberofperiodsunitjhasbeenonlinepriortothefirstperiodofthetimespan(endofperiod0).Minimumuptimeofunitj.Initialcommitmentstateofunitj(1ifitisonline,0otherwise).VariablesShutdowncostofunitjinperiodk.Productioncostofunitjinperiodk.Startupcostofunitjinperiodk.Poweroutputofunitjinperiodk.Maximumavailablepoweroutputofunitjinperiodk.Numberofperiodsunitjhasbeenofflinepriortothestartupinperiodk.Binaryvariablethatisequalto1ifunitjisonline

inperiodkand0otherwise.Powerproducedinblockofthepiecewiselinearproductioncostfunctionofunitjinperiodk.

SetsSetofindexesofthegeneratingunits.Setofindexesofthetimeperiods.

I.INTRODUCTION

THENEWcompetitiveenvironmentinpowersystemsisde-

mandingmoreefficientandaccuratetoolstosupportde-cisionsforresourcescheduling.Thethermalunitcommitmentproblemhasbeentraditionallysolvedincentralizedpowersys-temstodeterminewhentostartuporshutdownthermalgen-eratingunitsandhowtodispatchonlinegeneratorstomeet

0885-8950/$20.00©2006IEEE1372IEEETRANSACTIONSONPOWERSYSTEMS,VOL.21,NO.3,AUGUST2006systemdemandandspinningreserverequirementswhilesatis-fyinggenerationconstraints(productionlimits,rampinglimits,andminimumupanddowntimes)overaspecificshort-termtimespan,sothattheoveralloperationcostisminimized[1].Thegenerationschedulingproblemssolvedbytheindepen-dentsystemoperator(ISO)incurrentelectricitymarkets[2]aresimilartotheunitcommitmentproblemincentralizednon-competitivepowersystems,aspromotedbyFERC’sStandardMarketDesign[3].Themainconceptualdifferencebetweenbothproblemsisthat,ratherthanminimizingoperationcosts,theISOmaximizesameasureofsocialwelfare,whichisafunc-tionofmarketparticipantbidsandoffers.Thus,thesolutionofthetraditional,centralizedunitcommitmentproblemisrelevantforthecompetitivepowerindustry.Forseveraldecades,thislarge-scale,mixed-integer,com-binatorial,andnonlinearprogrammingproblemhasbeenanactiveresearchtopicbecauseofpotentialsavingsinoperationcosts.Asaconsequence,severalsolutiontechniqueshavebeenproposedsuchasheuristics[4]–[6],dynamicprogram-ming[7]–[9],mixed-integerlinearprogramming(MILP)[10],[11],Lagrangianrelaxation[12]–[18],simulatedannealing[19]–[21],andevolution-inspiredapproaches[22]–[26].Arecentextensiveliteraturesurveyonunitcommitmentcanbefoundin[27].Amongtheaforementionedmethodologies,Lagrangianre-laxationisthemostwidelyusedapproachbecauseofitscapa-bilityofsolvinglarge-scaleproblems.Themaindisadvantageofthismethodisthat,duetothenonconvexitiesoftheunitcommit-mentproblem,heuristicproceduresareneededtofindfeasiblesolutions,whichmaybesuboptimal.Incontrast,MILPguaranteesconvergencetotheoptimalso-lutioninafinitenumberofsteps[28]whileprovidingaflex-ibleandaccuratemodelingframework.Inaddition,duringthesearchoftheproblemtree,informationontheproximitytotheoptimalsolutionisavailable.Efficientmixed-integerlinearsoft-waresuchasthebranch-and-cutalgorithmhasbeendeveloped,andoptimizedcommercialsolverswithlarge-scalecapabilitiesarecurrentlyavailable[29]–[31].Asaconsequence,agreatdealofattentionhasbeenpaidtoMILP-basedapproaches.In[10],MILPwasfirstappliedtosolvetheunitcommitmentproblem.Theformulationin[10]wasbasedonthedefinitionofthreesetsofbinaryvariablesto,respectively,modelthestartup,shutdown,andon/offstatesforeveryunitandeverytimepe-riod.Thismixed-integerlinearformulationwasextendedin[32]tomodeltheself-schedulingproblemfacedbyasinglegener-atingunitinanelectricitymarket.Nonconvexproductioncosts,time-dependentstartupcosts,andintertemporalconstraintssuchasrampinglimitsandminimumupanddowntimeswereac-countedforattheexpenseofincreasingthenumberofbinaryvariables.Forrealisticpowersystemscomprisingseveraltensofgen-erators,themodelsof[10]and[32]requirealargenumberofbinaryvariables.Thus,theresultingMILPproblemsmightbecomputationallyintensiveforstate-of-the-artimplementationsofbranch-and-cutalgorithms[29]–[31]andcurrentcomputingcapabilities.In[33],startupcostsandminimumupanddowntimeswereformulatedusinglinearexpressionsthatrequiredasingletypeofbinaryvariables.However,theunitcommitmentmodeldidnotconsiderrampinglimitsandtheirinfluenceonthespin-ningreserveconstraints.Inaddition,shutdowncostswerenotmodeledeither.Theobjectiveofthispaperistopresentanalternativemixed-integerlinearformulationofthethermalunitcommit-mentproblem,hereinafterdenotedbyMILP-UC,requiringasinglesetofbinaryvariables(oneperunitandperperiod).UnlikepreviousMILPapproaches[10],[32],thelowernumberofbinaryvariablesinMILP-UCyieldsareductioninthenumberofnodesofthesearchtreeusedbythebranch-and-cutalgorithm,aswellasareductioninthenumberofconstraints,thusdecreasingthecomputingtimerequiredbyavailablesolvers[29]–[31]totacklerealisticcases.Moreover,MILP-UCaccuratelymodelsthermalunitcommitmentstates,intertem-poralconstraints,andtime-dependentstartupcosts,therebyimprovingthemodelingcapabilitiesof[33].Themodelproposedinthispaperisalsoapplicabletotheschedulingproblemsarisinginelectricitymarketssuchasmarket-clearingproceduressolvedbyISOs,self-schedulingproblemssolvedbygeneratingcompaniestoderivebiddingstrategies,andmarketsimulatorsusedtoanalyzethebehaviorofmarketparticipants.Therefore,marketagentscanbenefitfromMILP-UC.Themaincontributionsofthispaperareasfollows.1)Anewformulation,MILP-UC,requiringfewerbinaryvari-ablesandconstraintstoaccuratelymodelthethermalunitcommitmentproblemispresentedinordertoreducethecomputationalburdenofexistingMILPapproaches.2)Numericalexperienceisreportedbysolvingarealisticap-plication.Theremainingsectionsareoutlinedasfollows.SectionIIprovidesadetaileddescriptionoftheproposedMILP-UCfor-mulation.Thissectionincludesaprecisemodelofthephysicalandintertemporalconstraintsofthepowergenerators.InSec-tionIII,numericalresultsarepresentedanddiscussed.InSec-tionIV,somerelevantconclusionsaredrawn.Finally,thedatausedinthenumericalsimulationsareprovidedintheAppendix.