Models Telecommunication

From TomWiki
Revision as of 19:00, 17 January 2012 by Elias (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Notice.png

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 end

Dimensioning 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 end

Routing 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 end

Construction 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 end

Scheduling 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 text

Location 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