Models Telecommunication
From TomWiki
Jump to navigationJump to search
|
|
This page is part of TOMLAB Models. See TOMLAB Models. |
Network reliability
% function Result = networkreliabilityEx(PriLev)
%
% Creates a TOMLAB MIP problem for network reliability
%
% NETWORK RELIABILITY
%
% We consider the military telecommunications network represented
% below. This network consists of eleven sites connected by
% bidirectional lines for data transmission. For reliability reasons
% in the case of a conflict, the specifications require that the two
% sites (nodes) 10 and 11 of the network remain able to communicate
% even if any three other sites of the network are destroyed. Does
% the network satisfy this requirement?
%
%
% 1 --- 2 ---------- 8
%
% / | / | / |
% / | / | / |
% / | / | / |
% | |
% 11 --- 3 ---+---- 10 |
% | |
% | \ / \ | / | \ |
% | X \ | / | | |
% | / \ \ | / | | |
% | | |
% 4 --- 5 --- 9 | | |
% | | |
% \ | / | |
% \ | / \ |
% \ | / \ |
% \
% ----- 6 ---------- 7
%
%
%
% VARIABLES
%
% arcs_out/in For an arc i arcs_out(i) is its starting node
% and arcs_in(i) ts target node
%
% RESULTS
%
% for an interpretation of the results, use a PriLev > 1, for example
% Result = networkreliabilityEx(2);
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev Print Level
%
% OUTPUT PARAMETERS
% Result Result structure.
% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2005 by Tomlab Optimization Inc., $Release: 5.0.0$
% Written Nov 7, 2005. Last modified Nov 7, 2005.
function Result = networkreliabilityEx(PriLev)
if nargin < 1
PriLev = 1;
end
arcs_in = [1 1 1 2 2 2 3 3 3 3 4 4 4 5 5 6 6 6 7 7 8 9]';
arcs_out = [2 3 11 3 8 9 4 9 10 11 5 6 11 9 11 7 9 10 8 10 10 10]';
Prob = networkreliability(arcs_in, arcs_out);
Result = tomRun('cplex', Prob, PriLev);
if PriLev > 1,
f = - Result.f_k;
x = - Result.x_k;
disp(['The network can manage the loss of ' num2str(f-1) ' nodes.'])
disp(['There are ' num2str(f) ' disjunctive paths.'])
[arcs,direction] = find(reshape(x,length(arcs_in),2));
disp('For a maximal number of disjunctive paths, activate...')
for arc = 1:length(arcs),
if direction(arc) == 1,
disp([' arc ' num2str([arcs_out(arcs(arc))]) '->' ...
num2str([arcs_in(arcs(arc))])])
end
if direction(arc) == 2,
disp([' arc ' num2str([arcs_in(arcs(arc))]) '->' ...
num2str([arcs_out(arcs(arc))])])
end
end
end
% MODIFICATION LOG
%
% 051107 med Created.
% 060116 per Added documentation.
% 060126 per Moved disp to endDimensioning of a mobile phone network
% function Result = dimofamobilephonenetworkEx(PriLev)
%
% Creates a TOMLAB MIP problem for dimensioning of a mobile phone network
%
% DIMENSIONING OF A MOBILE PHONE NETWORK
%
% The figure below represents the typical architecture of a mobile
% phone network. Every elementary geographical zone or cell is served
% by a transmitter-receiver called a relay. The calls originating
% from a mobile phone first pass through these relays. Every relay is
% connected by cable or electro-magnetic waves to a transit node
% (hub). One of the hubs controls the network, this is the MTSO
% (Mobile Telephone Switching Office). A very reliable ring of fiber
% optic cable connects the hubs and the MTSO with high capacity
% links. It is capable of re-establishing itself in the case of a
% breakdown (self-healing ring) and there is no need to replicate it.
%
% At the present state of technology, there are no dynamic
% connections between the relays and the MTSO. The connections are
% fixed during the design phase, so it is necessary to choose the
% nodes of the ring that a relay should be connected to. The number
% of links between a cell c and the ring is called the diversity of
% the cell c, denoted by CNCTc. A diversity larger than 1 is
% recommended for making the system more reliable.
%
% The traffic in this kind of system is entirely digitized, expressed
% in values equivalent to bidirectional circuits at 64kbps (kilobit
% per second). This capacity corresponds to the number of
% simultaneous calls during peak periods. The ring has edges of known
% capacity CAP. The traffic TRAFc from a cell c is divided into equal
% parts (TRAFc / CNCTc) among the connections to the ring. This
% traffic is transmitted via the ring to the MTSO, that then routes
% it to another cell or to a hub that serves as the interface to the
% fixed-line telephone network. A relay may be connected directly to
% the MTSO that also has the functions of an ordinary hub.
%
% We consider a network of 10 cells and a ring of 5 nodes with a
% capacity of CAP = 48 circuits. The MTSO is at node 5. The following
% table indicates the traffic, the required number of connections and
% the cost per connection in thousand $ per cell. For example, cell 1
% is connectable with node 1 for a cost of $15,000. Its diversity is
% 2, which means it must be connected to at least two nodes of the
% ring. Its traffic capacity is of 22 simultaneous circuits. The
% objective is to define the connections of the cells to the ring
% that minimize the connection costs whilst remaining within the
% capacity limits and satisfying the constraints on the number of
% connections.
%
% Structure of a mobile phone network
%
% Cell 1
% 2 connections
%
% Relay ---------\
% \
% | \
% | \
% | |
% V V
%
% hub2 ============ hub3 <-- Relay
% cell 2
% || || 1 connection
% || ||
% || ||
%
% hub1 === MTSO === hub4
%
% Connection costs, traffic and number of connections per cell
%
% +------------+--+--+--+--+--+--+--+--+--+--+
% |Cell | 1| 2| 3| 4| 5| 6| 7| 8| 9|10|
% +------------+--+--+--+--+--+--+--+--+--+--+
% |Hub 1 |15| 9|12|17| 8| 7|19|20|21|25|
% |Hub 2 | 8|11| 6| 5|22|25|25| 9|22|24|
% |Hub 3 | 7| 8| 7| 9|21|15|21|15|14|13|
% |Hub 4 |11| 5|15|18|19| 9|20|18|16| 4|
% |Hub 5 (MTSO)|10|14|15|24| 6|17|22|25|20|11|
% +------------+--+--+--+--+--+--+--+--+--+--+
% |Traffic |22|12|20|12|15|25|15|14| 8|22|
% +------------+--+--+--+--+--+--+--+--+--+--+
% |Connections | 2| 2| 2| 2| 3| 1| 3| 2| 2| 2|
% +------------+--+--+--+--+--+--+--+--+--+--+
%
% VARIABLES
%
% hub_mat Matrix describing the hubs
% traffic Traffic from cells
% connections Possible connections per cell
% capacity Capacity
%
% RESULTS
%
% For an interpretation of the results, try:
% Result = dimofamobilephonenetworkEx(2);
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev Print Level
%
% OUTPUT PARAMETERS
% Result Result structure.
% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2005 by Tomlab Optimization Inc., $Release: 5.0.0$
% Written Nov 8, 2005. Last modified Nov 8, 2005.
function Result = dimofamobilephonenetworkEx(PriLev)
if nargin < 1
PriLev = 1;
end
hub_mat = [15 9 12 17 8 7 19 20 21 25;...
8 11 6 5 22 25 25 9 22 24;...
7 8 7 9 21 15 21 15 14 13;...
11 5 15 18 19 9 20 18 16 4;...
10 14 15 24 6 17 22 25 20 11]*1000;
traffic = [22 12 20 12 15 25 15 14 8 22]';
connections = [ 2 2 2 2 3 1 3 2 2 2]';
capacity = 48;
Prob = dimofamobilephonenetwork(hub_mat, traffic, connections,...
capacity);
Result = tomRun('cplex', Prob, PriLev);
if PriLev > 1,
[h,c] = size(hub_mat) ;
temp = reshape(Result.x_k,c,h);
for cell = 1:c,
idx = find(temp(cell,:));
disp(['cell ' num2str(cell) ' connects to hub(s) ' num2str(idx)])
end
end
% MODIFICATION LOG
%
% 051108 med Created.
% 060116 per Added documentation.
% 060126 per Moved disp to endRouting telephone calls
% function Result = routingtelephonecallsEx(PriLev)
%
% Creates a TOMLAB MIP problem for routing telephone calls
%
% ROUTING TELEPHONE CALLS
%
% A private telephone company exploits a network, represented in the
% figure below, between five cities: Paris, Nantes, Nice, Troyes, and
% Valenciennes.
%
% Structure of the network of the company
%
% Nantes --(300)-- Paris --(200)-- Valenciennes
%
% \ / |
% (120) (300) (70)
% \ / |
%
% Nice ----(80)---- Troyes
%
% The number beside each edge (connection) is the capacity of the
% link in terms of circuits. This issue is worth some further
% explanation. Suppose that a person A at Nantes calls a person B at
% Nice. The company needs to find a path formed by non-saturated
% edges from Nantes to Nice to route the binary flow corresponding to
% the digitized voice of A. But the conversation is only possible if
% a flow from Nice to Nantes is established so that B may answer A.
% In digital telephone networks, the binary flows all have the same
% throughput standard (often 64 kbps). The associated capacity is
% called a channel. The return channel uses the same edges as the
% first channel, but in the opposite direction. This linked pair of
% channels necessary for a telephone conversation is a circuit.
%
% The routing of the return channel through the same edges is due to
% the fact that the call could fail if one waited until the callee
% picked up the phone before searching for a non-saturated return
% path. This is why, at the moment of the call, the routing system
% constructs the path edge by edge and immediately reserves the edges
% of the return channel. As a consequence, as the capacity of an edge
% is consumed in increments of a bidirectional circuit, we do not
% consider any directed flows. For example, there may be 10 persons
% calling from Nantes to Nice and 20 from Nice to Nantes, or the
% opposite: in both cases, 30 circuits are used.
%
% At a given moment, the company is facing demands for circuits given
% in the following table. Is it possible to satisfy the demands
% entirely? If this is not possible, try to transmit as much as
% possible. In every case, indicate the corresponding routing,
% that is, the access paths used.
%
% Demand of circuits
%
% +-------------------+--------+
% |Cities |Circuits|
% +-------------------+--------+
% |Nantes-Nice | 100 |
% |Nantes-Troyes | 80 |
% |Nantes-Valenciennes| 75 |
% |Nice-Valenciennes | 100 |
% |Paris-Troyes | 70 |
% +-------------------+--------+
%
%
% VARIABLES
%
% arcs_out/in For an arc i arcs_out(i) is its starting node
% and arcs_in(i) ts target node
% capacity Capacity of arcs
% demand_out/in For a demand i demand_out(i) is its starting node
% and demand_in(i) its target node
% demands Demand
% path_mat Possible paths
% paths In/Out of possible paths
%
% RESULTS
%
% For an interpretation of the results, try:
% Result = routingtelephonecallsEx(2);
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev Print Level
%
% OUTPUT PARAMETERS
% Result Result structure.
% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2005 by Tomlab Optimization Inc., $Release: 5.0.0$
% Written Nov 22, 2005. Last modified Nov 22, 2005.
function Result = routingtelephonecallsEx(PriLev)
if nargin < 1
PriLev = 1;
end
% Nantes, Paris, Nice, Valenciennes, Troyes
arcs_in = [1 1 2 2 3 4]';
arcs_out = [2 3 3 4 5 5]';
capacity = [300 120 300 200 80 70]';
demand_in = [1 1 1 3 2]';
demand_out = [3 5 4 4 5]';
demands = [100 80 75 100 70]';
path_mat = [1 3 0 0 0;...
1 2 3 0 0;...
1 2 4 5 3;...
1 2 4 5 0;...
1 2 3 5 0;...
1 3 5 0 0;...
1 3 2 4 5;...
1 2 4 0 0;...
1 3 2 4 0;...
1 2 3 5 4;...
1 3 5 4 0;...
3 1 2 4 0;...
3 2 4 0 0;...
3 5 4 0 0;...
2 4 5 0 0;...
2 1 3 5 0;...
2 3 5 0 0];
paths = [1 3;...
1 3;...
1 3;...
1 5;...
1 5;...
1 5;...
1 5;...
1 4;...
1 4;...
1 4;...
1 4;...
3 4;...
3 4;...
3 4;...
2 5;...
2 5;...
2 5];
Prob = routingtelephonecalls(arcs_in, arcs_out, capacity,...
demand_in, demand_out, demands, path_mat, paths);
Result = tomRun('cplex', Prob, PriLev);
if PriLev > 1,
paths = Result.x_k;
idx = find(paths);
load = [];
cities = ['Nant'; 'Pari'; 'Nice'; 'Vale'; 'Troy'];
disp('INCOMING AND OUTGOING CIRCUITS')
for i = 1:length(idx),
id = idx(i);
temp_path = path_mat(id,:);
temp_path = temp_path(find(temp_path));
city_path = [];
for city = 1:length(temp_path),
city = temp_path(city);
city_path = [city_path cities(city,:) ' ' ];
end
disp([' ' num2str(paths(id)) ' circuits ' ...
cities(temp_path(1),:) '-' cities(temp_path(end),:) ...
' using the following path: ' num2str(city_path)])
for j = 2:length(temp_path),
out = temp_path(j-1);
in = temp_path(j);
if in < out,
in_temp = in;
in = out;
out = in_temp;
end
if (size(load) > [out in]),
load(out,in) = load(out,in) + paths(id);
else
load(out,in) = paths(id);
end
end
end
disp('LOAD BETWEEN CITIES')
for i = 1:length(cities)-1,
for j = 1:length(cities),
if load(i,j) > 0,
disp([' between ' cities(i,:) ' and ' cities(j,:) ': ' ...
num2str(load(i,j)) ' circuits.' ])
end
end
end
end
% MODIFICATION LOG
%
% 051122 med Created.
% 060116 per Added documentation.
% 060126 per Moved disp to endConstruction of a cabled network
% function Result = constructionofacablednetworkEx(PriLev)
%
% Creates a TOMLAB MIP problem for construction of a cabled network
%
% CONSTRUCTION OF A CABLED NETWORK
%
% A university wishes to connect six terminals located in different
% buildings of its campus. The distances, in meters, between the
% different terminals are given in the table below.
%
% Distances between the different terminals (in meters)
%
% +----------+---+---+---+---+---+---+
% | | T1| T2| T3| T4| T5| T6|
% +----------+---+---+---+---+---+---+
% |Terminal 1| 0|120| 92|265|149|194|
% |Terminal 2|120| 0|141|170| 93|164|
% |Terminal 3| 92|141| 0|218|103|116|
% |Terminal 4|265|170|218| 0|110|126|
% |Terminal 5|149| 93|103|110| 0| 72|
% |Terminal 6|194|164|116|126| 72| 0|
% +----------+---+---+---+---+---+---+
%
% These terminals are to be connected via underground cables. We
% suppose the cost of connecting two terminals is proportional to the
% distance between them. Determine the connections to install to
% minimize the total cost.
%
% VARIABLES
%
% distances a distance matrix
%
% RESULTS
%
% for an interpretation of the results, let PriLev > 1, for example:
% Result = constructionofacablednetworkEx(2); % call solver
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev Print Level
%
% OUTPUT PARAMETERS
% Result Result structure.
% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2005 by Tomlab Optimization Inc., $Release: 5.0.0$
% Written Nov 22, 2005. Last modified Nov 22, 2005.
function Result = constructionofacablednetworkEx(PriLev)
if nargin < 1
PriLev = 1;
end
distances = [ 0 120 92 265 149 194;...
120 0 141 170 93 164;...
92 141 0 218 103 116;...
265 170 218 0 110 126;...
149 93 103 110 0 72;...
194 164 116 126 72 0];
Prob = constructionofacablednetwork(distances);
Result = tomRun('cplex', Prob, PriLev);
if PriLev > 1,
t = size(distances,1); % number of terminals
s = sum(1:t-1); % possible connections
arcs = []; % empty set of arcs
count = 1; % counter
for i = 1:t-1, % we catch true arcs
for j = i+1:t,
if Result.x_k(count) == 1,
arcs = [arcs ; i j];
end
count = count + 1;
end
end
for arc = 1:length(arcs),
arc = arcs(arc,:);
disp(['connect the terminals ' num2str(arc(1)) ' and ' num2str(arc(2)) ])
end
end
% MODIFICATION LOG
%
% 051122 med Created.
% 060116 per Added documentation.
% 060126 per Moved disp to endScheduling of telecommunications via satellite
% function Result = schedulingofteleviasatelliteEx(PriLev)
%
% Creates a TOMLAB MIP problem for scheduling of telecommunications via
% satellite
%
% SCHEDULING OF TELECOMMUNICATIONS VIA SATELLITE
%
% A digital telecommunications system via satellite consists of a
% satellite and a set of stations on earth which serve as interfaces
% with the terrestrial network. With SS-TDMA (Satellite-Switch, Time
% Division Multiple Access) access technology, the satellite divides
% its time among the stations. Consider for example the transmissions
% from four transmitter stations in the US to four receiver stations
% in Europe. The following table gives a possible 4 × 4 traffic
% matrix. TRAFtr is the quantity of data transmitted from station t
% to station r. It is expressed in seconds of transmission duration,
% because all lines have the same constant transmission rate.
%
% Matrix TRAF with its lower bound LB
%
% +----+--+--+--+--+-------+
% |TRAF| 1| 2| 3| 4| rowt |
% +----+--+--+--+--+-------+
% | 1 | 0| 7|11|15| 33 |
% | 2 |15| 8|13| 9| 45 |
% | 3 |17|12| 6|10| 45 |
% | 4 | 6|13|15| 4| 38 |
% +----+--+--+--+--+-------+
% |colr|38|40|45|38|LB = 45|
% +----+--+--+--+--+-------+
%
% The satellite has a switch that allows any permutation between the
% four transmitters and the four receivers. The figure below gives an
% example of a permutation connecting the transmitters 1 to 4 to the
% receivers 3, 4, 1, and 2 respectively. These connections allow
% routing a part of the traffic matrix, called a mode. A part of a
% matrix entry transmitted during a mode is a packet of data. A mode
% is thus a 4 × 4 matrix M with at most one non-zero packet per row
% and column and such that Mtr <= TRAFtr for all t, r. To every
% mode corresponds a slice of a schedule as shown in the figure.
%
% +----+--+--+--+--+ +---------+---------------+
% |TRAF| 1| 2| 3| 4| |Stations | Packets |
% +----+--+--+--+--+ +---------+---------------+
% | 1 | 0| 0|11| 0| | 1 --> 3 |-----11---> |
% | 2 | 0| 0| 0| 9| | 2 --> 4 |------9-> |
% | 3 |15| 0| 0| 0| | 3 --> 1 |-----15------->|
% | 4 | 0|13| 0| 0| | 4 --> 2 |-----13-----> |
% +----+--+--+--+--+ +---------+---------------+
% |colr|38|40|45|38|LB = 45
% +----+--+--+--+--+
%
%
% Example of a mode and associated schedule
%
% A valid schedule of transmissions defines a sequence of
% permutations for the on-board switch that routes all the traffic of
% the matrix TRAF. In other words, this boils down to decomposing
% TRAF into a sum of mode matrices. An element of TRAF may be
% fragmented, like TRAF31 that is only partially transmitted in the
% mode represented in the figure above. A fragmented element will
% appear in several packets and several modes of the final
% decomposition. The duration of a mode is the length of its longest
% packet. The objective is to find a schedule with minimal total duration.
%
% VARIABLES
%
% traffic A matrix describing the traffic
%
% RESULTS
%
% For an interpretation of the results, let PriLev > 1,
% schedulingofteleviasatelliteEx(2);
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev Print Level
%
% OUTPUT PARAMETERS
% Result Result structure.
% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2005 by Tomlab Optimization Inc., $Release: 5.0.0$
% Written Nov 22, 2005. Last modified Nov 22, 2005.
function Result = schedulingofteleviasatelliteEx(PriLev)
if nargin < 1
PriLev = 1;
end
if PriLev > 1, % if: PriLev > 1
sequence = []; % then: let us catch all x_k
end
traffic = [ 0 7 11 15;...
15 8 13 9;...
17 12 6 10;...
6 13 15 4];
TQBS = schedulingofteleviasatellite(traffic);
while sum(sum(TQBS)) > 0.01
n1 = size(TQBS,1);
n2 = n1^2;
n = n2 + 1;
x_L = zeros(n,1);
x_U = [ones(n2,1);inf];
IntVars = [ones(n2,1);0];
b_L1 = ones(n1,1);
b_U1 = ones(n1,1);
b_L2 = ones(n1,1);
b_U2 = ones(n1,1);
b_L3 = zeros(n1,1);
b_U3 = inf*ones(n1,1);
A1 = zeros(n1,n);
A2 = zeros(n1,n);
A3 = zeros(n1,n);
for i=1:n1
idx1 = [(i-1)*n1+1:i*n1];
idx2 = find(TQBS(:,i) == 0);
idx1(idx2) = [];
idx3 = [i:n1:n2-n1+i];
idx4 = find(TQBS(i,:) == 0);
idx3(idx4) = [];
A1(i,idx1) = ones(1,length(idx1));
A2(i,idx3) = ones(1,length(idx3));
A3(i,(i-1)*n1+1:i*n1) = TQBS(:,i)';
A3(i,end) = -1;
end
c = [zeros(n2,1);-1];
Prob = mipAssign(c, [A1;A2;A3], [b_L1;b_L2;b_L3], [b_U1;b_U2;b_U3], x_L, x_U, [], 'Satellite Scheduling',...
[], [], IntVars);
Result = tomRun('cplex', Prob, 0);
x_k = Result.x_k;
x_k = reshape(x_k(1:end-1), n1, n1);
TQBS = TQBS - x_k*(-Result.f_k);
if PriLev > 1,
sequence = [sequence Result.x_k];
end
end
PrintResult(Result,PriLev);
if PriLev > 1,
for t = 1:size(sequence,2),
disp(['Transmission ' num2str(t) ' transfers ' num2str(sequence(end,t)) ' packet(s) of data' ])
this = reshape(sequence(1:end-1,t),n1,n1);
this(find(this < 0.5)) = 0; % remove bad zeros
for j = 1:n1,
disp([' from station ' num2str(j) ' to ' num2str(find(this(j,:))) ])
end
end
end
% MODIFICATION LOG
%
% 051122 med Created.
% 060116 per Added documentation.
% 060126 per Moved disp to end
% 060131 per cleaned up help textLocation of GSM transmitters
% function Result = locationofgsmtransmittersEx(PriLev)
%
% Creates a TOMLAB MIP problem for location of gsm transmitters
%
% LOCATION OF GSM TRANSMITTERS
%
% A mobile phone operator decides to equip a currently uncovered
% geographical zone. The management allocates a budget of $ 10
% million to equip this region. A study shows that only 7 locations
% are possible for the construction of the transmitters and it is
% also known that every transmitter only covers a certain number of
% communities. The figure below represents a schematic map of the
% region with the division into communities and the possible
% locations for transmitters. Every potential site is indicated by
% four stars and a number, every community is represented by a
% polygon. The number in the center of a polygon is the number of the
% community.
%
% Certain geographical and topological constraints add to the
% construction cost and reduce the reach of the GSM transmitters. The
% table below lists the communities covered and the cost for every
% site.
%
% For every community the number of inhabitants is known (see table).
% Where should the transmitters be built to cover the largest
% population with the given budget limit of $ 10M?
%
% Map of the region to cover
%
% +--------+-------+----------+--------+
% | | * 7 / |
% | 1 | 4 *3* / |
% | * * /--\ /* 11 |
% +-------*1* |/ 10 \/*6* |
% | *\ / \ / -*--+-------+
% | \ / \--/ \ |
% | \ /\ | \ 15 |
% | 2 / \ 8 |* \ |
% | / \ *5* 12 *\ +
% | / \ |* *7*\ /|
% | / 5 \ | * \/ |
% +-----*-+ * \|-----+----- / |
% | *2* \ -*4*---+ | \ 14|
% | * \ / * / | \ |
% | \/ / 9 | \ |
% | 3 \ 6 / | 13 \|
% | \ / | +
% +-------------+-+----------+---------+
%
% Inhabitants of the communities
%
% +--------------------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
% |Community | 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|
% +--------------------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
% |Population (in 1000)| 2| 4|13| 6| 9| 4| 8|12|10|11| 6|14| 9| 3| 6|
% +--------------------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
%
% Cost and communities covered for every site
%
% +-------------------+-----+-----+--------+-------+------+-------------+-----------+
% |Site | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
% +-------------------+-----+-----+--------+-------+------+-------------+-----------+
% |Cost (in million $)| 1.8 | 1.3 | 4.0 | 3.5 | 3.8 | 2.6 | 2.1 |
% |Communities covered|1,2,4|2,3,5|4,7,8,10|5,6,8,9|8,9,12|7,10,11,12,15|12,13,14,15|
% +-------------------+-----+-----+--------+-------+------+-------------+-----------+
%
% VARIABLES
%
% budget Money available
% cost Cost to build site
% connections Communities covered by a site
% population People living in communities
% var1 30 plus
% var2 30 minus
%
% RESULTS
%
% To interpret the results try the following:
% Result = locationofgsmtransmittersEx(2);
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev Print Level
%
% OUTPUT PARAMETERS
% Result Result structure.
% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2005 by Tomlab Optimization Inc., $Release: 5.0.0$
% Written Nov 30, 2005. Last modified Nov 30, 2005.
function Result = locationofgsmtransmittersEx(PriLev)
if nargin < 1
PriLev = 1;
end
budget = 10e6;
cost = [1.8 1.3 4.0 3.5 3.8 2.6 2.1]'*1e6;
connections = [ 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0;...
0 1 1 0 1 0 0 0 0 0 0 0 0 0 0;...
0 0 0 1 0 0 1 1 0 1 0 0 0 0 0;...
0 0 0 0 1 1 0 1 1 0 0 0 0 0 0;...
0 0 0 0 0 0 0 1 1 0 0 1 0 0 0;...
0 0 0 0 0 0 1 0 0 1 1 1 0 0 1;...
0 0 0 0 0 0 0 0 0 0 0 1 1 1 1];
population = [ 2 4 13 6 9 4 8 12 10 11 6 ...
14 9 3 6]'*1000;
Prob = locationofgsmtransmitters(budget, cost, connections, ...
population);
Result = tomRun('cplex', Prob, PriLev);
if PriLev > 1,
[loc,com] = size(connections);
build = Result.x_k(1:loc);
cover = Result.x_k(loc+1:end);
disp(['Build at locations ' num2str(find(build'))])
disp(['Cover communities ' num2str(find(cover'))])
end
% MODIFICATION LOG
%
% 051130 med Created.
% 060116 per Added documentation.
% 060126 per Moved disp to end