<< Click to Display Table of Contents >> Navigation:  Wadiso 6 User Guide > Optimization > Optimization technique and general concepts  > Reasons for an Enumeration Algorithm

The optimization of pipe networks is complicated by several practical considerations that make it very difficult to apply standard optimization techniques without contorting the problem to fit the technique. These are discussed below.

The discrete character of the variables to be selected (i.e. pipe sizes with their associated cost) makes the use of standard optimization procedures difficult. Such procedures typically assume that the variables to be selected are continuous. Of particular concern in connection with treating the pipe sizes as continuous variables is the fact that the discrete cost function may be quite erratic and difficult to approximate by a continuous function. In addition to these difficulties, some optimization procedures require that the cost function should have some specific characteristics (e.g. cost per unit length has to be proportional to the diameter to the power 2.63).

Most of the optimization procedures proposed so far are essentially gradient search techniques, some in a continuous variable space, some in a discrete space. Such algorithms can only guarantee local minima.

Finally, a solution developed in a continuous space requires an additional step after the execution of the optimization algorithm, in which the pipe sizes are “rounded” to commercially available pipe sizes. This step is not trivial. Indeed, it is possible that the globally optimal, discrete solution may not even be in the neighbourhood of the globally optimal solution using continuous pipe sizes, but could be associated with a local minimum. An exhaustive search among the discrete solutions in the neighbourhood of the global minimum of the continuous solution does not guarantee the globally optimal solution in discrete space.

If the transition from a continuous solution to a discrete solution poses such significant difficulties, it is then quite logical to explore the feasibility to work in the discrete space from the very beginning. Optimization by exhaustive enumeration of all possible size combinations within user specified constraints overcome several shortcomings of the traditional optimization procedures. Most importantly it guarantees the globally optimal solution in the discrete domain of pipe sizes. There are no requirements associated with the discrete cost function. It is also relatively easy to account for pumping cost and/or tank cost as part of the optimization, or to consider cleaning of old pipes as an alternative to the addition of new pipes. The inclusion of multiple loading patterns is possible as well, a point which addresses the problem of system redundancy. Finally, the exhaustive enumeration can be used for the generation of a queue of Pareto Optimal solutions (non-inferior). Such a queue is most valuable in the decision making process since pressure constraints and water demands are in many cases somewhat arbitrary.

The most important drawback of an algorithm based on exhaustive enumeration may be the computer time required to find the optimum. In its most general formulation such a procedure is NP-hard (i.e. the computer time required to find the optimum solution increases exponentially with system size). This observation deserves two comments.

First, if a problem is formulated in the most general format (i.e. the sizing of every pipe individually), exhaustive enumeration would have to be limited to “relatively small” systems. Since many optimization problems are in fact, topologically speaking, small, this in itself does not rule out the usefulness of the procedure.

Second, the most general formulation may indeed not even be desirable. In the most general formulation each leg of pipe is sized individually. Such an approach may well lead to very arbitrary size selection, dictated to a large degree by specific loading patterns, and the peculiarities of the cost function. The optimized system may in the end no longer show a clear conveyance concept. (Conveyance concept refers to the overall flow pattern from the source to the users, e.g. most of the flow is carried in pipe along Walnut St. while pipe along Cherry St. merely closes the loop.) From an operational point of view such a clear conveyance concept is an important requirement. By combining several pipes to be sized into one group of pipes, with the ultimate goal that all pipes in the same group be assigned the same size, the optimization can be forced to provide a simple and easy to understand conveyance concept.

If the number of groups of pipes can be limited say to less than 10 in real sizing problems, independent of total system size, and if the number of candidate sizes for each group can be limited to say less than 6, the problem is no longer NP-hard. Computer time now increases only with system size (number of nodes) to a power somewhat smaller than two if a sparse matrix technique is used in the computation of the pressure distributions.