Metho ds and Mo dels fo r Combinato rial Optimi zatio n

Metho ds and Mo dels fo r Combinato rial Optimi zatio n

Introduction LuigiDeGiovanni,MarcoDiSumma DipartimentodiMatematica,Universit`adiPadova DeGiovanni,DiSummaMeMoCO1/36

W e have seen.. .

Coursegoal:howtomanagecombinatorialexplosionindecisionsupport problemsofpracticalinterest(state-of-the-artalgorithmdesignand implementation) Importanceof(mathematicalprogramming)modelsandlinearity Coursecontent: �Models(formulation,understanding,IBM-CPlexlibraries) �LinearProgr.(simplexreview,columngeneration,implementation) �IntegerProgr.(Theoryandmethods[byProf.DiSumma], implementationofB&C) �Metaheuristics(trajectorybased,randomizedsearch,genetic algorithms:designandimplementation) �Labs Materialavailableonthewebpagebeforetheclass:readit! Exam.Mandatory:twoexercises[0-10]+oral[0-20].Optionalproject[2-6] �exerciseduedate:4daysbeforethe“appello”date(e.g.“appello” onJuly16th,duedateJuly12th):anoticewillbeposted �shortproject:normallyaftertheoral,toimprovethescoreifnecessary DeGiovanni,DiSummaMeMoCO2/36

W e have seen.. .

Coursegoal:howtomanagecombinatorialexplosionindecisionsupport problemsofpracticalinterest(state-of-the-artalgorithmdesignand implementation) Importanceof(mathematicalprogramming)modelsandlinearity Coursecontent: �Models(formulation,understanding,IBM-CPlexlibraries) �LinearProgr.(simplexreview,columngeneration,implementation) �IntegerProgr.(Theoryandmethods[byProf.DiSumma], implementationofB&C) �Metaheuristics(trajectorybased,randomizedsearch,genetic algorithms:designandimplementation) �Labs Materialavailableonthewebpagebeforetheclass:readit! Exam.Mandatory:twoexercises[0-10]+oral[0-20].Optionalproject[2-6] �exerciseduedate:4daysbeforethe“appello”date(e.g.“appello” onJuly16th,duedateJuly12th):anoticewillbeposted �shortproject:normallyaftertheoral,toimprovethescoreifnecessary DeGiovanni,DiSummaMeMoCO2/36

W e have seen.. .

Coursegoal:howtomanagecombinatorialexplosionindecisionsupport problemsofpracticalinterest(state-of-the-artalgorithmdesignand implementation) Importanceof(mathematicalprogramming)modelsandlinearity Coursecontent: �Models(formulation,understanding,IBM-CPlexlibraries) �LinearProgr.(simplexreview,columngeneration,implementation) �IntegerProgr.(Theoryandmethods[byProf.DiSumma], implementationofB&C) �Metaheuristics(trajectorybased,randomizedsearch,genetic algorithms:designandimplementation) �Labs Materialavailableonthewebpagebeforetheclass:readit! Exam.Mandatory:twoexercises[0-10]+oral[0-20].Optionalproject[2-6] �exerciseduedate:4daysbeforethe“appello”date(e.g.“appello” onJuly16th,duedateJuly12th):anoticewillbeposted �shortproject:normallyaftertheoral,toimprovethescoreifnecessary DeGiovanni,DiSummaMeMoCO2/36

W e have seen.. .

Coursegoal:howtomanagecombinatorialexplosionindecisionsupport problemsofpracticalinterest(state-of-the-artalgorithmdesignand implementation) Importanceof(mathematicalprogramming)modelsandlinearity Coursecontent: �Models(formulation,understanding,IBM-CPlexlibraries) �LinearProgr.(simplexreview,columngeneration,implementation) �IntegerProgr.(Theoryandmethods[byProf.DiSumma], implementationofB&C) �Metaheuristics(trajectorybased,randomizedsearch,genetic algorithms:designandimplementation) �Labs Materialavailableonthewebpagebeforetheclass:readit! Exam.Mandatory:twoexercises[0-10]+oral[0-20].Optionalproject[2-6] �exerciseduedate:4daysbeforethe“appello”date(e.g.“appello” onJuly16th,duedateJuly12th):anoticewillbeposted �shortproject:normallyaftertheoral,toimprovethescoreifnecessary DeGiovanni,DiSummaMeMoCO2/36

W e have seen.. .

Coursegoal:howtomanagecombinatorialexplosionindecisionsupport problemsofpracticalinterest(state-of-the-artalgorithmdesignand implementation) Importanceof(mathematicalprogramming)modelsandlinearity Coursecontent: �Models(formulation,understanding,IBM-CPlexlibraries) �LinearProgr.(simplexreview,columngeneration,implementation) �IntegerProgr.(Theoryandmethods[byProf.DiSumma], implementationofB&C) �Metaheuristics(trajectorybased,randomizedsearch,genetic algorithms:designandimplementation) �Labs Materialavailableonthewebpagebeforetheclass:readit! Exam.Mandatory:twoexercises[0-10]+oral[0-20].Optionalproject[2-6] �exerciseduedate:4daysbeforethe“appello”date(e.g.“appello” onJuly16th,duedateJuly12th):anoticewillbeposted �shortproject:normallyaftertheoral,toimprovethescoreifnecessary DeGiovanni,DiSummaMeMoCO2/36

Mathem atical Progra mming Mo dels

Amathematicalprogrammingmodeldescribesthecharacteristicsof theoptimalsolutionofanoptimizationproblembymeansof mathematicalrelations. Sets:theygrouptheelementsofthesystem Parameters:thedataoftheproblem,whichrepresenttheknown quantitiesdependingontheelementsofthesystem. Decision(orcontrol)variables:theunknownquantities,onwhich wecanactinordertofinddifferentpossiblesolutionstotheproblem. Constraints:mathematicalrelationsthatdescribesolutionfasibility conditions(theydistinguishacceptablecombinationsofvaluesofthe variables). Objectivefunction:quantitytomaximizeorminimize,asafunction ofthedecisionvariables. DeGiovanni,DiSummaMeMoCO3/36

Linea r Pro grammi ng mo dels

Mathematicalprogrammingmodelswhere: objectivefunctionisalinearexpressionofthedecisionvariables; constraintsareasystemoflinearequationsand/orinequalities. Classificationoflinearprogrammingmodels: LinearProgrammingmodels(LP):allthevariablescantakereal (R)values; IntegerLinearProgrammingmodels(ILP):allthevariablescan takeinteger(Z)valuesonly; MixedIntegerLinearProgrammingmodels(MILP):some variablescantakerealvaluesandotherscantakeintegervaluesonly. Linearitylimitsexpressivenessbutallowsfastersolutiontechniques! DeGiovanni,DiSummaMeMoCO4/36

Linea r Pro grammi ng mo dels

Mathematicalprogrammingmodelswhere: objectivefunctionisalinearexpressionofthedecisionvariables; constraintsareasystemoflinearequationsand/orinequalities. Classificationoflinearprogrammingmodels: LinearProgrammingmodels(LP):allthevariablescantakereal (R)values; IntegerLinearProgrammingmodels(ILP):allthevariablescan takeinteger(Z)valuesonly; MixedIntegerLinearProgrammingmodels(MILP):some variablescantakerealvaluesandotherscantakeintegervaluesonly. Linearitylimitsexpressivenessbutallowsfastersolutiontechniques! DeGiovanni,DiSummaMeMoCO4/36

Linea r Pro grammi ng mo dels

Mathematicalprogrammingmodelswhere: objectivefunctionisalinearexpressionofthedecisionvariables; constraintsareasystemoflinearequationsand/orinequalities. Classificationoflinearprogrammingmodels: LinearProgrammingmodels(LP):allthevariablescantakereal (R)values; IntegerLinearProgrammingmodels(ILP):allthevariablescan takeinteger(Z)valuesonly; MixedIntegerLinearProgrammingmodels(MILP):some variablescantakerealvaluesandotherscantakeintegervaluesonly. Linearitylimitsexpressivenessbutallowsfastersolutiontechniques! DeGiovanni,DiSummaMeMoCO4/36

An LP mo del fo r a simple CO probl em

Example Aperfumefirmproducestwonewitemsbymixingthreeessences:rose, lilyandviolet.Foreachdecaliterofperfumeone,itisnecessarytouse1.5 litersofrose,1literoflilyand0.3litersofviolet.Foreachdecaliterof perfumetwo,itisnecessarytouse1literofrose,1literoflilyand0.5 litersofviolet.27,21and9litersofrose,lilyandviolet(respectively)are availableinstock.Thecompanymakesaprofitof130eurosforeach decaliterofperfumeonesold,andaprofitof100eurosforeachdecaliter ofperfumetwosold.Theproblemistodeterminetheoptimalamountof thetwoperfumesthatshouldbeproduced. max130xone+100xtwoobjectivefunction s.t.1.5xone+xtwo≤27availabilityofrose xone+xtwo≤21availabilityoflily 0.3xone+0.5xtwo≤9availabilityofviolet xone,xtwo≥0domainsofthevariables DeGiovanni,DiSummaMeMoCO5/36

An LP mo del fo r a simple CO probl em

Example Aperfumefirmproducestwonewitemsbymixingthreeessences:rose, lilyandviolet.Foreachdecaliterofperfumeone,itisnecessarytouse1.5 litersofrose,1literoflilyand0.3litersofviolet.Foreachdecaliterof perfumetwo,itisnecessarytouse1literofrose,1literoflilyand0.5 litersofviolet.27,21and9litersofrose,lilyandviolet(respectively)are availableinstock.Thecompanymakesaprofitof130eurosforeach decaliterofperfumeonesold,andaprofitof100eurosforeachdecaliter ofperfumetwosold.Theproblemistodeterminetheoptimalamountof thetwoperfumesthatshouldbeproduced. max130xone+100xtwoobjectivefunction s.t.1.5xone+xtwo≤27availabilityofrose xone+xtwo≤21availabilityoflily 0.3xone+0.5xtwo≤9availabilityofviolet xone,xtwo≥0domainsofthevariables DeGiovanni,DiSummaMeMoCO5/36

One p ossible mo deling schema: optima l pro ductio n mix

setI:resourcesetI={rose,lily,violet} setJ:productsetJ={one,two} parametersDi:availabilityofresourcei∈Ie.g.Drose=27 parametersPj:unitprofitforproductj∈Je.g.Pone=130 parametersQij:amountofresourcei∈Irequiredforeachunitof productj∈Je.g.Qroseone=1.5,Qlilytwo=1 variablesxj:amountofproductj∈Jxone,xtwo max� j∈JPjxj s.t.� j∈JQijxj≤Di∀i∈I xj∈R+[Z+|{0,1}]∀j∈J DeGiovanni,DiSummaMeMoCO6/36

The diet proble m

Example Weneedtoprepareadietthatsuppliesatleast20mgofproteins.30mg ofironand10mgofcalcium.Wehavetheopportunityofbuying vegetables(containing5mg/kgofproteins,6mg/Kgofirone5mg/Kg ofcalcium,cost4E/Kg),meat(15mg/kgofproteins,10mg/Kgofirone 3mg/Kgofcalcium,cost10E/Kg)andfruits(4mg/kgofproteins,5 mg/Kgofirone12mg/Kgofcalcium,cost7E/Kg).Wewantto determinetheminimumcostdiet. min4xV+10xM+7xFcost s.t.5xV+15xM+4xF≥20proteins 6xV+10xM+5xF≥30iron 5xV+3xM+12xF≥10calcium xV,xM,xF≥0domainsofthevariables DeGiovanni,DiSummaMeMoCO7/36

The diet proble m

Example Weneedtoprepareadietthatsuppliesatleast20mgofproteins.30mg ofironand10mgofcalcium.Wehavetheopportunityofbuying vegetables(containing5mg/kgofproteins,6mg/Kgofirone5mg/Kg ofcalcium,cost4E/Kg),meat(15mg/kgofproteins,10mg/Kgofirone 3mg/Kgofcalcium,cost10E/Kg)andfruits(4mg/kgofproteins,5 mg/Kgofirone12mg/Kgofcalcium,cost7E/Kg).Wewantto determinetheminimumcostdiet. min4xV+10xM+7xFcost s.t.5xV+15xM+4xF≥20proteins 6xV+10xM+5xF≥30iron 5xV+3xM+12xF≥10calcium xV,xM,xF≥0domainsofthevariables DeGiovanni,DiSummaMeMoCO7/36

One p ossible mo deling schema: minimum cost cover ing

setI:availableresourcesI={V,M,F} setJ:requestsetJ={proteins,iron,calcium} parametersCi:unitcostofresourcei∈I parametersRj:requestedamountofj∈J parametersAij:amountofrequestj∈Jsatisfiedbyoneunitof resourcei∈I variablesxi:amountofresourcei∈I min� i∈ICixi s.t. � i∈IAijxi≥Dj∀j∈J xi∈R+[Z+|{0,1}]∀i∈I DeGiovanni,DiSummaMeMoCO8/36

The tra nsp ortat ion problem

Example Acompanyproducesrefrigeratorsinthreedifferentfactories(A,BandC) andneedtomovethemtofourstores(1,2,3,4).Theproductionof factoriesA,BandCis50,70and20units,respectively.Stores1,2,3and 4require10,60,30e40units,respectively.ThecostsinEurostomove onerefrigeratorfromafactorytostores1,2,3and4arethefollowing: fromA:6,8,3,4 fromB:2,3,1,3 fromC:2,4,6,5 Thecompanyasksustoformulateaminimumcosttransportationplan. DeGiovanni,DiSummaMeMoCO9/36

One p ossible mo deling schema: tran sp ortat ion

setI:originsfactoriesI={A,B,C} setJ:destinationsstoresJ={1,2,3,4} parametersOi:capacityoforigini∈Ifactoryproduction parametersDj:requestofdestinationj∈Jstorerequest parametersCij:unittransp.costfromorigini∈Itodestinationj∈J variablesxij:amounttobetransportedfromi∈Itoj∈J min� i∈I� j∈JCijxij s.t. � i∈Ixij≥Dj∀j∈J � j∈Jxij≤Oi∀i∈I xij∈R+[Z+|{0,1}]∀i∈Ij∈J DeGiovanni,DiSummaMeMoCO10/36

Fixed costs

Example AsupermarketchainhasabudgetWavailableforopeningnewstores. PreliminaryanalysesidentifiedasetIofpossiblelocations.Openinga storeini∈IhasafixedcostFi(landacquisition,otheradministrative costsetc.)andavariablecostCiper100m2 ofstore.Onceopened,the storeiniguaranteesarevenueofRiper100m2 .Determinethesubsetof locationwhereastorehastobeopenedandtherelatedsizeinorderto maximizethetotalrevenue,takingintoaccountthatatmostKstorescan beopened. DeGiovanni,DiSummaMeMoCO11/36 Modelingfixedcosts:binary/booleanvariables setI:potentiallocations parametersW,Fi,Ci,Ri,“large-enough”M variablesxi:size(in100m2 )ofthestoreini∈I variablesyi:takingvalue1ifastoreisopenedini∈I(xi>0),0otherwise max� i∈IRixi s.t. � i∈ICixi+Fiyi≤Wbudget xi≤Myi∀i∈IBigMconstraint/relatexitoyi � i∈Iyi≤Kmaxnumberofstores xi∈R+,yi∈{0,1}∀i∈I DeGiovanni,DiSummaMeMoCO12/36

Movin g sca ff olds b et w een constr uction ya rds

Aconstructioncompanyhastomovethescaffoldsfromthreeclosingbuildingsites(A, B,C)tothreenewbuildingsites(1,2,3).Thescaffoldsconsistofironrods:inthe sitesA,B,Ctherearerespectively7000,6000and4000ironrods,whilethenewsites1, 2,3need8000,5000and4000rodsrespectively.Thefollowingtableprovidethecostof movingoneironrodfromaclosingsitetoanewsite: Costs(eurocents)123 A965 B749 C463 Truckscanbeusedtomovetheironrodsfromonesitetoanothersite.Eachtruckcan carryupto10000rods.Findalinearprogrammingmodelthatdeterminetheminimum costtransportationplan,takingintoaccountthat: usingatruckcausesanadditionalcostof50euros; only4trucksareavailable(andeachofthemcanbeusedonlyforasinglepairof closingsiteandnewsite); therodsarrivinginsite2cannotcomefrombothsitesAandB; itispossibletorentafifthtruckfor65euros(i.e.,15eurosmorethantheother trucks). DeGiovanni,DiSummaMeMoCO13/36

Movin g sca ff olds b et w een constr uction ya rds: elements

Sets: I:closingsites(origins); J:newssites(destinations). Parameters: Cij:unitcost(perrod)fortransportationfromi∈Itoj∈J; Di:numberofrodsavailableatorigini∈I; Rj:numberofrodsrequiredatdestinationj∈J; F:fixedcostforeachtruck; N:numberoftrucks; L:fixedcostfortherentofanadditionaltruck; K:truckcapacity. Decisionvariables: xij:numberofrodsmovedfromi∈Itoj∈J; yij:binary,values1ifatruckfromi∈Itoj∈Jisused,0otherwise. z:binary,values1iftheadditionaltruckisused,0otherwise. DeGiovanni,DiSummaMeMoCO14/36

Movin g sca ff olds b et w een constr uction ya rds: MILP mo del

[Suggestion:composetransportationandfixedcostschemas] min� i∈I,j∈JCijxij+F� i∈I,j∈Jyij+(L−F)z s.t.� i∈Ixij≥Rj∀j∈J � j∈Jxij≤Di∀i∈I xij≤Kyij∀i∈I,j∈J � i∈I,j∈Jyij≤N+z xij∈Z+∀i∈I,j∈J yij∈{0,1}∀i∈I,j∈J z∈{0,1} DeGiovanni,DiSummaMeMoCO15/36

Movin g sca ff olds b et w een constr uction ya rds: MILP mo del

[Suggestion:composetransportationandfixedcostschemas] min� i∈I,j∈JCijxij+F� i∈I,j∈Jyij+(L−F)z s.t.� i∈Ixij≥Rj∀j∈J � j∈Jxij≤Di∀i∈I xij≤Kyij∀i∈I,j∈J � i∈I,j∈Jyij≤N+z xij∈Z+∀i∈I,j∈J yij∈{0,1}∀i∈I,j∈J z∈{0,1} DeGiovanni,DiSummaMeMoCO15/36

Movin g sca ff olds b et w een constr uction ya rds: va rian t 1

truckcapacityKdoesnotguaranteethatonetruckisenough �howmanytrucksper(i,j)?⇒variableswij,z∈Z+insteadof yij,z∈{0,1} min� i∈I,j∈JCijxij+F� i∈I,j∈Jwij+(L−F)z s.t.� i∈Ixij≥Rj∀j∈J � j∈Jxij≤Di∀i∈I xij≤Kwij∀i∈I,j∈J � i∈I,j∈Jwij≤N+z xij∈Z+∀i∈I,j∈J wij∈Z+∀i∈I,j∈J z∈Z+ DeGiovanni,DiSummaMeMoCO16/36

Movin g sca ff olds b et w een constr uction ya rds: va rian t 1

truckcapacityKdoesnotguaranteethatonetruckisenough �howmanytrucksper(i,j)?⇒variableswij,z∈Z+insteadof yij,z∈{0,1} min� i∈I,j∈JCijxij+F� i∈I,j∈Jwij+(L−F)z s.t.� i∈Ixij≥Rj∀j∈J � j∈Jxij≤Di∀i∈I xij≤Kwij∀i∈I,j∈J � i∈I,j∈Jwij≤N+z xij∈Z+∀i∈I,j∈J wij∈Z+∀i∈I,j∈J z∈Z+ DeGiovanni,DiSummaMeMoCO16/36

Movin g sca ff olds b et w een constr uction ya rds: va rian t 2

additionalfixedcostAiforloadingoperationsini∈I �doesloadingtakeplaceini?⇒variablevi∈{0,1} min� i∈I,j∈JCijxij+F� i∈I,j∈Jwij+(L−F)z+� i∈IAivi s.t.� i∈Ixij≥Rj∀j∈J � j∈Jxij≤Divi∀i∈I xij≤Kwij∀i∈I,j∈J � i∈I,j∈Jwij≤N+z xij∈Z+∀i∈I,j∈J wij∈Z+∀i∈I,j∈J vi∈{0,1}∀i∈I z∈Z+ Attention:trytopreservelinearity! DeGiovanni,DiSummaMeMoCO17/36

Movin g sca ff olds b et w een constr uction ya rds: va rian t 2

additionalfixedcostAiforloadingoperationsini∈I �doesloadingtakeplaceini?⇒variablevi∈{0,1} min� i∈I,j∈JCijxij+F� i∈I,j∈Jwij+(L−F)z+� i∈IAivi s.t.� i∈Ixij≥Rj∀j∈J � j∈Jxij≤Divi∀i∈I xij≤Kwij∀i∈I,j∈J � i∈I,j∈Jwij≤N+z xij∈Z+∀i∈I,j∈J wij∈Z+∀i∈I,j∈J vi∈{0,1}∀i∈I z∈Z+ Attention:trytopreservelinearity! DeGiovanni,DiSummaMeMoCO17/36

Movin g sca ff olds b et w een constr uction ya rds: va rian t 2

additionalfixedcostAiforloadingoperationsini∈I �doesloadingtakeplaceini?⇒variablevi∈{0,1} min� i∈I,j∈JCijxij+F� i∈I,j∈Jwij+(L−F)z+� i∈IAivi s.t.� i∈Ixij≥Rj∀j∈J � j∈Jxij≤Divi∀i∈I xij≤Kwij∀i∈I,j∈J � i∈I,j∈Jwij≤N+z xij∈Z+∀i∈I,j∈J wij∈Z+∀i∈I,j∈J vi∈{0,1}∀i∈I z∈Z+ Attention:trytopreservelinearity! DeGiovanni,DiSummaMeMoCO17/36

Emerge ncy lo cati on

Anetworkofhospitalshastocoveranareawiththeemergencyservice.Thearea hasbeendividedinto6zonesand,foreachzone,apossiblelocationforthe servicehasbeenidentified.Theaveragedistance,inminutes,fromeveryzoneto eachpotentialservicelocationisshowninthefollowingtable. Loc.1Loc.2Loc.3Loc.4Loc.5Loc.6 Zone151020303020 Zone210525352010 Zone320255153020 Zone430351551525 Zone530203015514 Zone620102025145 Itisrequiredeachzonehasanaveragedistancefromaemergencyserviceofat most15minutes.Thehospitalsaskusforaserviceopeningschemethat minimizesthenumberofemergencyservicesinthearea. DeGiovanni,DiSummaMeMoCO18/36

Emerge ncy lo cati on: MILP mo del from cover ing schema

Isetodpotentiallocations(I={1,2,...,6}). xivariables,values1ifserviceisopenedatlocationi∈I,0otherwise. minx1+x2+x3+x4+x5+x6 s.t. x1+x2≥1(coverzone1) x1+x2+x6≥1(coverzone2) x3+x4≥1(coverzone3) x3+x4+x5≥1(coverzone4) x4+x5+x6≥1(coverzone5) x2+x5+x6≥1(coverzone6) x1,x2,x3,x4,x5,x6∈{0,1}(domain) DeGiovanni,DiSummaMeMoCO19/36

TLC anten nas lo catio n

Atelephonecompanywantstoinstallantennasinsomesitesinordertocoversixareas. Fivepossiblesitesfortheantennashavebeendetected.Aftersomesimulations,the intensityofthesignalcomingfromanantennaplacedineachsitehasbeenestablished foreacharea.Thefollowingtablesummarizedtheseintensitylevels: area1area2area3area4area5area6 siteA10201625010 siteB0121823116 siteC218562319 siteD16151581418 siteE211313171822 Receiversrecognizeonlysignalswhoselevelisatleast18.Furthermore,itisnotpossible tohavemorethanonesignalreachinglevel18inthesamearea,otherwisethiswould causeaninterference.Finally,anantennacanbeplacedinsiteEonlyifanantennais installedalsoinsiteD(thisantennawouldactasabridge).Thecompanywantsto determinewhereantennasshouldbeplacedinordertocoverthemaximumnumberof areas. DeGiovanni,DiSummaMeMoCO20/36

TLC anten nas lo catio n: MILP [fro m cover ing schema]

I:setofsitesforpossiblelocations;J:setofareas; σij:parameter,signallevelofantennaini∈Ireceivedinj∈J; T:parameter,minimumsignallevelrequired; N:parameter,maximumnumberofnon-interferingsignals(here,N=1); Mj:parameter,largeenough,e.g.,Mj=card({i∈I:σij≥T}). xi:binaryvariable,values1ifanantennaisplacedini∈I,0otherwise; zj:binaryvariable,values1ifareaj∈Jwillbecovered,0otherwise; max� j∈J1 s.t.� i∈I:σij≥Txi≥1∀j∈J � i∈I:σij≥Txi≤N∀j∈J xi∈{0,1}∀i∈I zj∈{0,1}∀j∈J DeGiovanni,DiSummaMeMoCO21/36

TLC anten nas lo catio n: MILP [fro m cover ing schema]

I:setofsitesforpossiblelocations;J:setofareas; σij:parameter,signallevelofantennaini∈Ireceivedinj∈J; T:parameter,minimumsignallevelrequired; N:parameter,maximumnumberofnon-interferingsignals(here,N=1); Mj:parameter,largeenough,e.g.,Mj=card({i∈I:σij≥T}). xi:binaryvariable,values1ifanantennaisplacedini∈I,0otherwise; zj:binaryvariable,values1ifareaj∈Jwillbecovered,0otherwise; max� j∈Jzj s.t.� i∈I:σij≥Txi≥zj∀j∈J � i∈I:σij≥Txi≤N+Mj(1−zj)∀j∈J xi∈{0,1}∀i∈I zj∈{0,1}∀j∈J DeGiovanni,DiSummaMeMoCO21/36