Network Reliability

Contents

Problem description

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

Reference

Applications of optimization... Gueret, Prins, Seveaux

% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2009 by Tomlab Optimization Inc., $Release: 7.2.0$
% Written Oct 7, 2005.   Last modified Apr 8, 2009.

Problem setup

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]';

n1 = length(arcs_in);   % arcs_in
n  = 2*n1;              % bi-directional
nodes = length(unique([arcs_in; arcs_out]));
arcs_in_new = [arcs_in;arcs_out];
arcs_out = [arcs_out;arcs_in];
arcs_in  = arcs_in_new;

arcs = tom('arcs',n,1,'int');

% All variables are binary.
bnds = {0 <= arcs <= 1};

% Kirchhoff's law, 1 source and 1 sink
con1 = cell(nodes-2,1);
for i=1:nodes-2 %Assuming 10 and 11 are source and sink
    idx1 = find(arcs_in == i);
    idx3 = find(arcs_out == i);
    con1{i} = {sum(arcs(idx1)) == sum(arcs(idx3))};
end

% Limit flow in intermediate node
con2 = cell(nodes-2,1);
for i=1:nodes-2 %Assuming 10 and 11 are source and sink
    idx1 = find(arcs_in == i);
    con2{i} = {sum(arcs(idx1)) <= 1};
end

% Source has no incoming flows
idx1 = find(arcs_out == nodes-1);
con3 = {sum(arcs(idx1)) == 0};

% Objective
idx1 = find(arcs_in == (nodes-1));
objective = -sum(arcs(idx1));

constraints = {bnds, con1, con2, con3};
options = struct;
options.solver = 'cplex';
options.name   = 'Network Reliability';
sol = ezsolve(objective,constraints,[],options);

PriLev = 1;
if PriLev > 0
    f      = -subs(objective,sol);
    x      = -sol.arcs;
    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,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
% 090308 med   Converted to tomSym

Problem type appears to be: mip
===== * * * =================================================================== * * *
TOMLAB - Tomlab Optimization Inc. Development license  999001. Valid to 2010-02-05
=====================================================================================
Problem: ---  1: Network Reliability            f_k      -4.000000000000000000
                                              f(x_0)      0.000000000000000000

Solver: CPLEX.  EXIT=0.  INFORM=101.
CPLEX Branch-and-Cut MIP solver
Optimal integer solution found

FuncEv    7 
CPU time: 0.015625 sec. Elapsed time: 0.016000 sec. 
The network can manage the loss of 3 nodes.
There are 4 disjunctive paths.
For a maximal number of disjunctive paths, activate...
 arc 11->1
 arc 11->3
 arc 11->4
 arc 11->5
 arc 8->7
 arc 1->2
 arc 2->8
 arc 3->10
 arc 4->6
 arc 5->9
 arc 6->10
 arc 7->10
 arc 9->10