(!******************************************************
   Mosel Example Problems
   ======================

   file covering.mos
   `````````````````
   TYPE:         Covering problem
   DIFFICULTY:   2
   FEATURES:     MIP problem, modeling an equivalence; sparse data format,
                 graphical output representation, 'if-then-else'
   DESCRIPTION:  A mobile phone operator decides to equip a currently 
                 uncovered geographical zone. A budget is allocated to equip 
                 this region. 7 locations are possible for the construction 
                 of the transmitters. Every transmitter only covers a certain
                 number of communities. For every community the number of 
                 inhabitants is known. Where should the transmitters be built 
                 to cover the largest population with the given budget?     
   FURTHER INFO: `Applications of optimization with Xpress-MP', 
                 Section 12.6 `Location of GSM transmitters'. 
                 Similar problems: Section 9.5 `Cutting of sheet metal', 
                 Section 15.2 `CCTV surveillance'
   
   (c) 2002 Dash Associates
       author: S. Heipcke
*******************************************************!)

model "Transmitter placement"
 uses "mmxprs", "mmive"

 declarations
  COMMS = 1..15                         ! Set of communities
  PLACES = 1..7                         ! Set of possible transm. locations

  COST: array(PLACES) of real           ! Cost of constructing transmitters
  COVER: array(PLACES,COMMS) of integer ! Coverage by transmitter locations
  POP: array(COMMS) of integer          ! Number of inhabitants (in 1000)
  BUDGET: integer                       ! Budget limit
   
  build: array(PLACES) of mpvar         ! 1 if transmitter built, 0 otherwise
  covered: array(COMMS) of mpvar        ! 1 if community covered, 0 otherwise 
 end-declarations

 initializations from 'covering.dat'
  COST COVER POP BUDGET
 end-initializations

! Objective: total population covered
 Coverage:= sum(c in COMMS) POP(c)*covered(c)

! Towns covered
 forall(c in COMMS) 
  CoverTown(c):= sum(p in PLACES) COVER(p,c)*build(p) >= covered(c) 

! Budget limit
 BudgetLim:= sum(p in PLACES) COST(p)*build(p) <= BUDGET

 forall(p in PLACES) build(p) is_binary
 forall(c in COMMS) covered(c) is_binary

! Solve the problem
 maximize(Coverage)
 
! Solution printing
 writeln("Total coverage: ", getobjval, " total cost: ", 
         getsol(sum(p in PLACES) COST(p)*build(p)))
 write("Build transmitters:")
 forall(p in PLACES) write(if(getsol(build(p))>0, " "+p, ""))
 write("\nCommunities covered:")
 forall(c in COMMS) write(if(getsol(covered(c))>0, " "+c, ""))
 writeln

! Solution drawing
 declarations
  XT,YT: array(PLACES) of integer       ! x-y-coordinates for transmitters
  XC,YC: array(COMMS) of integer        ! x-y-coordinates of communities
 end-declarations
 
 initializations from 'covering.dat'
  [XT,YT] as 'POST'
  [XC,YC] as 'POSC'
 end-initializations

 IVEzoom(10,10,110,75)
 
 CovGraph:= IVEaddplot("Communities covered", IVE_BLACK)
 UncGraph:= IVEaddplot("Communities not covered", IVE_RGB(150,150,150))
 forall(c in COMMS) do
  if(getsol(covered(c))>0) then
   IVEdrawpoint(CovGraph, XC(c), YC(c))
   IVEdrawlabel(CovGraph, XC(c)+1, YC(c)+1, string(c))
  else
   IVEdrawpoint(UncGraph, XC(c), YC(c))
   IVEdrawlabel(UncGraph, XC(c)+1, YC(c)+1, string(c))
  end-if
 end-do
 
 LocGraph:= IVEaddplot("Possible locations", IVE_RGB(120,0,0))
 BuildGraph:= IVEaddplot("Chosen locations", IVE_RED)
 forall(p in PLACES)
  if(getsol(build(p))>0) then
   IVEdrawpoint(BuildGraph, XT(p), YT(p))
   IVEdrawlabel(BuildGraph, XT(p)+1, YT(p)+1, string(p))
   forall(c in COMMS)
    if(COVER(p,c)>0) then 
     IVEdrawline(BuildGraph, XT(p), YT(p), XC(c), YC(c))
    end-if
  else
   IVEdrawpoint(LocGraph, XT(p), YT(p))
   IVEdrawlabel(LocGraph, XT(p)+1, YT(p)+1, string(p))
  end-if
 
end-model