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
g6transmit.mos
(!******************************************************
Mosel Example Problems
======================
file g6transmit.mos
```````````````````
Placing mobile phone transmitters
A mobile phone operator plans to equip a currently uncovered
region. There are 7 possible locations for the transmitters.
Each site has a defined number of communities it can serve.
Given the construction cost and reach of each site, where
should the transmitters be built so that the largest
population is covered with the given budget restrictions?
The formulation as a covering problem is straightforward.
We store data for 'COVER' in sparse format, that is, only
the entries with value 1 are given. Since this array is
declared as a dense array, all other entries are
automatically populated with value 0.
(c) 2008-2022 Fair Isaac Corporation
author: S. Heipcke, Apr. 2002, rev. Mar. 2022
*******************************************************!)
model "G-6 Transmitter placement"
uses "mmxprs"
declarations
COMMS = 1..15 ! Set of communities
PLACES = 1..7 ! Set of possible transm. locations
COST: array(PLACES) of real ! Cost of constructing transmitters
COVER: array(PLACES,COMMS) of integer ! Coverage by transmitter locations
POP: array(COMMS) of integer ! Number of inhabitants (in 1000)
BUDGET: integer ! Budget limit
build: array(PLACES) of mpvar ! 1 if transmitter built, 0 otherwise
covered: array(COMMS) of mpvar ! 1 if community covered, 0 otherwise
end-declarations
initializations from 'g6transmit.dat'
COST COVER POP BUDGET
end-initializations
! Objective: total population covered
Coverage:= sum(c in COMMS) POP(c)*covered(c)
! Towns covered
forall(c in COMMS) sum(p in PLACES) COVER(p,c)*build(p) >= covered(c)
! Budget limit
sum(p in PLACES) COST(p)*build(p) <= BUDGET
forall(p in PLACES) build(p) is_binary
forall(c in COMMS) covered(c) is_binary
! Solve the problem
maximize(Coverage)
! Solution printing
writeln("Total coverage: ", getobjval, " (of ", sum(c in COMMS) POP(c),
") total cost: ", getsol(sum(p in PLACES) COST(p)*build(p)))
write("Build transmitters:")
forall(p in PLACES | getsol(build(p))>0) write(" ", p)
write("\nCommunities covered:")
forall(c in COMMS | getsol(covered(c))>0) write(" ", c)
writeln
end-model
|
