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
g3routing.mos
(!******************************************************
Mosel Example Problems
======================
file g3routing.mos
``````````````````
Routing telephone calls in a private network
A private telephone network connects 5 French cities.
The circuit capacity between cities is known. At any point
in time, the network expects certain circuit demands. Is it
feasible to satisfy all these demands? How much can be
transmitted, if not all? Which is the assigned routing for
the circuits?
Each path between cities is represented by a list of arcs
(specified as an array) between two directly connected cities.
The problem is defined as a MIP, but the LP solution
already provides integer values. The solution display reports
unmet demand and also calculates the unused arc capacities.
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, Apr. 2002
*******************************************************!)
model "G-3 Routing telephone calls"
uses "mmxprs"
declarations
CALLS: set of string ! Set of demands
ARCS: set of string ! Set of arcs
PATHS: range ! Set of paths (routes) for demands
CAP: array(ARCS) of integer ! Capacity of arcs
DEM: array(CALLS) of integer ! Demands between pairs of cities
CINDEX: array(PATHS) of string ! Call (demand) index per path index
end-declarations
initializations from 'g3routing.dat'
CAP DEM CINDEX
end-initializations
NARC:=getsize(ARCS)
declarations
ROUTE: array(PATHS,1..NARC) of string ! List of arcs composing the routes
flow: array(PATHS) of mpvar ! Flow on paths
end-declarations
initializations from 'g3routing.dat'
ROUTE
end-initializations
! Objective: total flow on the arcs
TotFlow:= sum(p in PATHS) flow(p)
! Flow within demand limits
forall(d in CALLS) sum(p in PATHS | CINDEX(p) = d) flow(p) <= DEM(d)
! Arc capacities
forall(a in ARCS)
sum(p in PATHS, b in 1..NARC | ROUTE(p,b)=a) flow(p) <= CAP(a)
forall(p in PATHS) flow(p) is_integer
! Uncomment to display the solver log
! setparam("XPRS_VERBOSE", true)
! Solve the problem
maximize(TotFlow)
! Solution printing
writeln("Total flow: ", getobjval)
forall(d in CALLS) do
writeln(d, " (demand: ", DEM(d), ", routed calls: ",
getsol(sum(p in PATHS | CINDEX(p) = d) flow(p)), ")")
forall(p in PATHS | CINDEX(p) = d and getsol(flow(p))>0) do
write(" ", getsol(flow(p)), ":")
forall(b in 1..NARC) write(" ", ROUTE(p,b))
writeln
end-do
end-do
writeln("Unused capacity:")
forall(a in ARCS) do
U:=CAP(a) - getsol(sum(p in PATHS, b in 1..NARC | ROUTE(p,b)=a) flow(p))
write(if(U>0," " + a + ": " + U + "\n", ""))
end-do
end-model
|
