FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

Telecommunication problems

Description
Problem name and type, featuresDifficulty
G‑1 Network reliability: Maximum flow with unitary capacities ***
encoding of arcs, range, exists, create, algorithm for printing paths, forall-do, while-do, round
G‑2 Dimensioning of a mobile phone network **
if-then, exit
G‑3 Routing telephone calls: Multi-commodity network flow problem ***
encoding of paths, finalize, getsize
G‑4 Construction of a cabled network: Minimum weight spanning tree problem ***
formulation of constraints to exclude subcycles
G‑5 Scheduling of telecommunications via satellite: Preemptive open shop scheduling *****
data preprocessing, algorithm for preemptive scheduling that involves looping over optimization, ``Gantt chart'' printing
G‑6 Location of GSM transmitters: Covering problem *
modeling an equivalence; sparse data format


Further explanation of this example: 'Applications of optimization with Xpress-MP', Chapter 12: Telecommunication problems

mosel_app_7.zip[download all files]

Source Files

Data Files





g5satell.mos

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

   file g5satell.mos
   `````````````````
   Scheduling of telecommunications via satellite
   
   (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)
   if(getsol(flow(t,r))>0) then
    solflowt(t,ct):= t
    solflowr(t,ct):= r
   end-if 

 ! 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

Back to examples browserPrevious exampleNext example