| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Telecommunication problems Description
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 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

© Copyright 2024 Fair Isaac Corporation. |