Telecommunication problems
Description
Problem name and type, features | Difficulty | Related examples |
G‑1 | Network reliability: Maximum flow with unitary capacities | *** | maxflow_graph.mos, j1water.mos |
| encoding of arcs, range, exists, create, algorithm for printing paths, forall-do, while-do, round, list handling |
G‑2 | Dimensioning of a mobile phone network | ** | |
| if-then, exit |
G‑3 | Routing telephone calls: Multi-commodity network flow problem | *** | multicomflow_graph.mos |
| encoding of paths, finalize, getsize |
G‑4 | Construction of a cabled network: Minimum weight spanning tree problem | *** | spanningtree_graph.mos |
| formulation of constraints to exclude subcycles |
G‑5 | Scheduling of telecommunications via satellite: Preemptive open shop scheduling | ***** | openshop_graph.mos |
| data preprocessing, algorithm for preemptive scheduling that involves looping over optimization, ``Gantt chart'' printing |
G‑6 | Location of GSM transmitters: Covering problem | * | covering_graph.mos, d5cutsh.mos, j2bigbro.mos |
| modeling an equivalence; sparse data format |
Further explanation of this example:
'Applications of optimization with Xpress-MP', Chapter 12: Telecommunication problems
Source Files
By clicking on a file name, a preview is opened at the bottom of this page. Data Files
g5satell.mos
(!******************************************************
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
|