Discrete Optimization Optimisation of the interconnecting network of a UMTS radio mobile telephone system

AbstractInthispaperweaddressaveryimportantoptimisationproblemarisinginthetelecommunicationfield,namelythedesignoftheinterconnectingnetworkofaUMTSradiomobiletelephonesystem.ForthisNP-hardoptimisationproblemweproposeanewmixed-integerlinearprogrammingmodel,aswellasseveralclassesofadditionalconstraintsmeantatimprovingtheperformanceofsolutionalgorithmsandthequalityofthelowerboundsproduced.Afterwards,weintroduceanexactsolutionprocedureinthebranch-and-cutframework,andevaluateitonalibraryofreal-lifetestproblemsprovidedbyCSELT,amajorresearchlaboratoryoperatingwithanItaliantelephoneoperator(TELECOMItalia).Wereportonourcomputationalexperienceonthesetestinstances,showingthatthemethodweproposeiscapableoffindingtightlowerboundsandapproximatesolutionsforreal-worldinstances,withinacceptablecomputingtime. 2002ElsevierScienceB.V.Allrightsreserved. Keywords:Communication;Location;Mixedintegerlinearmodels 1.IntroductionAmobileradiotelephonesystemaimsaten-suringsecurecommunicationsbetweenmobileter-minalsandanyothertypeofuserdevice,eithermobileorfixed.Amobilecustomershouldbereachableatanytimeandinanylocationwheretheradiocoverageisgranted.Theconnectionamongmobileterminals(i.e.,theuser’shandheldterminals)andfixedradiobasestations is obtained by means of radio waves.However,asingleantennasystemcannotcoverthewholeservicearea.Infact,thatchoicewouldre-quirehighirradiationpowerbothfromthefixedandthemobilestations,withconsequentpossi-bledamageduetothegeneratedelectromagneticfield.Theabovelimitationsleadtotheimplementa-tionof‘‘cellularsystems’’,constitutedbyseveralfixed radio base stations and related antennasystems.Eachsingleradiobasestationcoverageareaiscalled‘‘cell’’anditservesasmallregionofvariablesizerangingfrom10to100m(highuserdensityinsidebusinessbuildings)to1–20km(lowuserdensityareasinthecountry).