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
g4cable.mos
(!******************************************************
Mosel Example Problems
======================
file g4cable.mos
````````````````
Connecting terminals through cables
A university wants to connect 6 terminals located in
different campus buildings. These terminals will be
connected via underground cables. The connection cost
is proportional to the distance between the terminals.
Which connections should be installed to minimize total
cost?
Simple constraints defining the number of total connections
and that each terminal must be connected to another
terminal could result in a sub cycle leading to an infeasible
solution. Each node is assigned a level value that is used in
the formulation of additional constraints to exclude the
creation of sub cycles.
(c) 2008-2022 Fair Isaac Corporation
author: S. Heipcke, Apr. 2002, rev. Mar. 2022
*******************************************************!)
model "G-4 Cabled network"
uses "mmxprs"
declarations
NTERM = 6
TERMINALS = 1..NTERM ! Set of terminals to connect
DIST: array(TERMINALS,TERMINALS) of integer ! Distance between terminals
ifconnect: array(TERMINALS,TERMINALS) of mpvar ! 1 if direct connection
! between terminals, 0 otherwise
level: array(TERMINALS) of mpvar ! level value of nodes
end-declarations
initializations from 'g4cable.dat'
DIST
end-initializations
! Objective: length of cable used
Length:= sum(s,t in TERMINALS | s<>t) DIST(s,t)*ifconnect(s,t)
! Number of connections
sum(s,t in TERMINALS | s<>t) ifconnect(s,t) = NTERM - 1
! Avoid subcycle
forall(s,t in TERMINALS | s<>t)
level(t) >= level(s) + 1 - NTERM + NTERM*ifconnect(s,t)
! Direct all connections towards the root (node 1)
forall(s in 2..NTERM) sum(t in TERMINALS | s<>t) ifconnect(s,t) = 1
forall(s,t in TERMINALS | s<>t) ifconnect(s,t) is_binary
! Solve the problem
minimize(Length)
! Solution printing
writeln("Cable length: ", getobjval)
write("Connections:")
forall(s,t in TERMINALS | s<>t and getsol(ifconnect(s,t))>0)
write(" ", s, "-", t)
writeln
end-model
|
