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

   file g5satell.mos
   `````````````````
   Scheduling of telecommunications via satellite
   
   A digital telecommunications system via satellite contains
   a satellite and a set of stations on earth. The satellite 
   divides its time between the stations. Consider 4 transmitting
   stations in the U.S. and 4 receiving stations in Europe. 
   The quantity of data transmitted between stations is known.
   A specific permutation of connections of transmitters and 
   receivers that allows routing part of the traffic is called 
   a 'mode'. The portion of a traffic demand transmitted during 
   a mode is a 'packet' of data. The duration of a mode is the 
   length of its longest packet. Determine the schedule of
   satellite modes with minimal total duration.
   
   This program implements the algorithm of Gonzalez and 
   Sahni. The inter-station traffic must be translated into
   a quasi bistochastic matrix via data preprocessing. The 
   problem definition is then incremental so that after each 
   solution of the MIP, the matrix is updated. Since the entire 
   problem is redefined in every iteration of the 'while' loop,
   each constraint is named so that they may be replaced. Note
   that once the 'flow' variables are defined they cannot be 
   removed. The final solution is printed as a Gantt chart
   showing the traffic leaving each of the 4 U.S. stations.
   
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, Apr. 2002
*******************************************************!)

model "G-5 Satellite scheduling"
 uses "mmxprs"

 declarations
  TRANSM = 1..4                         ! Set of transmitters
  RECV = 1..4                           ! Set of receivers

  TRAF: array(TRANSM,RECV) of integer   ! Traffic betw. terrestrial stations
  TQBS: array(TRANSM,RECV) of integer   ! Quasi bistochastic traffic matrix
  row: array(TRANSM) of integer         ! Row sums
  col: array(RECV) of integer           ! Column sums
  LB: integer                           ! Maximum of row and column sums
 end-declarations

 initializations from 'g5satell.dat'
  TRAF
 end-initializations

! Row and column sums
 forall(t in TRANSM) row(t):= sum(r in RECV) TRAF(t,r)
 forall(r in RECV) col(r):= sum(t in TRANSM) TRAF(t,r)
 LB:=maxlist(max(r in RECV) col(r), max(t in TRANSM) row(t))

! Calculate TQBS
 forall(t in TRANSM,r in RECV) do
  q:= minlist(LB-row(t),LB-col(r))
  TQBS(t,r):= TRAF(t,r)+q
  row(t)+=q
  col(r)+=q
 end-do

 declarations
  MODES: range
  
  flow: array(TRANSM,RECV) of mpvar         ! 1 if transmission from t to r,
                                            ! 0 otherwise
  pmin: mpvar                               ! Minimum exchange
  onerec, minexchg: array(TRANSM) of linctr ! Constraints on transmitters
                                            ! and min exchange
  onetrans: array(RECV) of linctr           ! Constraints on receivers

  solflowt: array(TRANSM,MODES) of integer  ! Solutions of every iteration
  solflowr: array(RECV,MODES) of integer    ! Solutions of every iteration
  solpmin: array(MODES) of integer          ! Objective value per iteration
 end-declarations

 forall(t in TRANSM,r in RECV) flow(t,r) is_binary

 ct:= 0
 while(sum(t in TRANSM,r in RECV) TQBS(t,r) > 0) do
  ct+=1
  
 ! One receiver per transmitter
  forall(t in TRANSM) onerec(t):= sum(r in RECV | TQBS(t,r)>0) flow(t,r) =1
 ! One transmitter per receiver
  forall(r in RECV) onetrans(r):= sum(t in TRANSM | TQBS(t,r)>0) flow(t,r) =1

 ! Minimum exchange
  forall(t in TRANSM) 
   minexchg(t):= sum(r in RECV | TQBS(t,r)>0) TQBS(t,r)*flow(t,r) >= pmin

 ! Solve the problem: maximize the minimum exchange
  maximize(pmin)

 ! Solution printing
  writeln("Round ", ct, " objective: ", getobjval)

 ! Save the solution
  solpmin(ct):= round(getobjval)
  forall(t in TRANSM,r in RECV | TQBS(t,r)>0 and getsol(flow(t,r))>0) do
   solflowt(t,ct):= t
   solflowr(t,ct):= r
  end-do 

 ! Update TQBS
  forall(t in TRANSM)
   TQBS(solflowt(t,ct),solflowr(t,ct)) -= solpmin(ct)

 end-do
 
! Solution printing
 writeln("\nTotal duration: ", sum(m in MODES) solpmin(m))
 
 write("      ")
 forall(i in 0..ceil(LB/5)) write(strfmt(i*5,5))
 writeln
 forall(t in TRANSM) do
  write("From ", t, " to: ")
  forall(m in MODES)
   forall(i in 1..solpmin(m)) do
    write(if(TRAF(solflowt(t,m),solflowr(t,m))>0, string(solflowr(t,m)),"-"))
    TRAF(solflowt(t,m),solflowr(t,m))-=1
   end-do
  writeln 
 end-do
 
end-model