TomSym Water Supply Management

This page is part of the TomSym Manual. See TomSym Manual.

Problem description

The graph in the figure below shows a water transport network. The nodes, numbered from 1 to 10, represent the cities, the reservoirs, and the pumping stations connected by a network of pipes. The three cities Gotham City, Metropolis, and Spider Ville are supplied from two reservoirs. The availabilities of water from these reservoirs in thousands of m3/h are 35 for reservoir 1 and 25 for reservoir 2. The capacity of each pipe connection is indicated in thousands of m3/h in the graph.

A study is undertaken to find out whether the existing network will be able to satisfy the demands of the cities in ten years time, that is 18, 15, and 20 thousand m3/h. Determine the maximum flow in the current network. Will it be sufficient in ten years from now?

Water transport network

35 20 15 7 18

 Reservoir-1 ----> 3 -------> 4 ------->  8-Gotham city
                                           ^
           | \15   |            \       ---+
           |  \    |10           ----\ /
         12|   \   |                  X
            \   \  |       10        / \10
             \   V V  --------------/   ---+
  25          \      /      15             V   15
 Reservoir-2 --+-> 5 ------------------->  9-Metropolis
               | 6   \       15            ^
             \ \      -----------   -------+
              \ \                \ /   10
               \ \12              X
             22 \ \              / \
                 V V            /   -----+
                       22         10     V     20
                   6 -------> 7 -------> 10-Spider Ville

Variables

arcs_out/in For an arc i arcs_out(i) is its target node

                 and arcs_in(i) its starting node

capacity Capacity of an arc source Artificial node acting as a source sink Artificial node acting as a sink

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.

arcs_in  = [ 1  1  1  2  2  3  3  4  4  5  5  5  6  7  7  8  9 10 11 11]';
arcs_out = [ 3  5  6  5  6  4  5  8  9  8  9 10  7  9 10 12 12 12  1  2]';

capacity = [20 15 12  6 22 15 10  7 10 10 15 15 22 10 10 18 15 20 35 25]';
source   = 11;
sink     = 12;

n = length(arcs_in);  %arcs

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

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

% Kirchhoffs's law
n1   = length(unique([arcs_in;arcs_out])) - 2;
b_L  = zeros(n1,1);
b_U  = zeros(n1,1);
con = cell(n1,1);
count = 1;
for i=1:n1+2
    if ~(i == source || i == sink)
        idx1 = find(arcs_in == i);
        idx2 = find(arcs_out == i);
        con{count} = {sum(arcs(idx1)) == sum(arcs(idx2))};
        count = count + 1;
    end
end

% Objective
idx = find(arcs_out == sink);
objective = -sum(arcs(idx));
constraints = {bnds, con};
options = struct;
options.solver = 'cplex';
options.name   = 'Water Conveyance';
sol = ezsolve(objective,constraints,[],options);

PriLev = 1;
if PriLev > 0
    x        = sol.arcs;
    names    = ['Reservoir 1 '; ...
        'Reservoir 2 '; ...
        'Node 3      '; ...
        'Node 4      '; ...
        'Node 5      '; ...
        'Node 6      '; ...
        'Node 7      '; ...
        'Gotham City '; ...
        'Metropolis  '; ...
        'Spider Ville'; ...
        'Production  '; ... % this is the source node
        'Consumption '];    % this is the sink node
    disp('Maximum flow of the network is as follows:')
    for i = 1:length(arcs_in),
        if x(i) ~= 0,
            disp([names(arcs_in(i),:) ' -> ' names(arcs_out(i),:) ': ' num2str(x(i)) ])
        end
    end
end

% MODIFICATION LOG
%
% 051205 med   Created.
% 060117 per   Added documentation.
% 060125 per   Moved disp to end
% 090325 med   Converted to tomSym

Problem type appears to be: mip
Time for symbolic processing: 0.05995 seconds
Starting numeric solver
===== * * * =================================================================== * * *
TOMLAB - TOMLAB Development license  999007. Valid to 2011-12-31
=====================================================================================
Problem: ---  1: Water Conveyance               f_k     -52.000000000000000000
                                              f(x_0)      0.000000000000000000

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

FuncEv    4 
CPU time: 0.015600 sec. Elapsed time: 0.013000 sec. 
Maximum flow of the network is as follows:
Reservoir 1  -> Node 3      : 20
Reservoir 1  -> Node 5      : 15
Reservoir 2  -> Node 6      : 17
Node 3       -> Node 4      : 15
Node 3       -> Node 5      : 5
Node 4       -> Gotham City : 7
Node 4       -> Metropolis  : 8
Node 5       -> Gotham City : 10
Node 5       -> Spider Ville: 10
Node 6       -> Node 7      : 17
Node 7       -> Metropolis  : 7
Node 7       -> Spider Ville: 10
Gotham City  -> Consumption : 17
Metropolis   -> Consumption : 15
Spider Ville -> Consumption : 20
Production   -> Reservoir 1 : 35
Production   -> Reservoir 2 : 17