Linear programming network flow

M. S. Bazaraa and J. J. Jarvis, Linear Programming and Network Flows, Wiley, 1977. 

In the network model, the nodes represent source sites, demand sites, or other (intermediate) nodes that are neither source nor demand sites. The net supply at node i is denoted as (for source sites is positive, for demand sites bj is negative, and for all other nodes bj is zero). To simplify our discussion, it is assumed that the total amount produced at the source sites is exactly equ to the total amount required at the demand sites. An arc connecting two nodes represents a transportation Unk. Associated with each arc (/, j) is an upper bound (arc capacity) Ujj limiting the total amount of goods that can flow on it. (In more complex models, there may also be a specific lower bound ij on the total flow on the arc. However, to simplify the discussion in this chapter, it is assumed that all lower bounds are zero.) An uncapacitated arc is one that has no upper bound on the amount of flow it can carry. There is a unit transportation flow cost Cy. The minimum cost flow problem can be represented as the following linear program ... 

One of the most effective algorithms for these classes of network problems has been a specialized implementation of the simplex algorithm for linear programming. This type of approach uses special data structures to exploit the special properties of the network models and accelerate the steps of the simplex algorithm. For example, for these network flow models (and aU of the other related subclasses discussed in this chapter), the set of basic variables corresponds to a set of arcs that form a spanning tree for the underlying network. Computing such items as the current values for the dual multiphers is easily done with a specialized procedure that exploits the basis tree structure (Ahuja et al. 1993). 

This additional layer of nodes illustrates how other preferences or constraints can be added to a network flow model without destroying the special network flow structure. Such modeling techniques are quite useful since network models can be solved much more efficiently than general linear programs. 

The most common of these exact cases are optimization problems that can be modeled as singlecommodity network flows (see Chapter 99). Equivalently, these are the (ILP)s that can be written so that for each variable Xj, at most one constraint coefficient A j equals 1, at most one A j equals —1, and all other equal 0. Such ILP) s are totally unimodular in that any submatrix formed by the Ajj associated with a collection of rows i and a like-sized collection of variables y has determinant 0, 1 or — 1. This is enough to ensure optimal basic solutions to (/LP) (produced, for example, by the simplex algorithm for linear programming) are integer whenever right-hand-side coefficients are all integer. 

One of the model aims is to maximize the satisfaction of consumer demands. The maximum flow optimization method was used to achieve this goal. Simplex method of linear programing was used to find the maximum flow in the pipeline network. The mathematical model of this problem could be written as ... 

The optimization problem of the MF problem can be solved by various approaches, for example by linear programming or by Ford-Fulkerson algorithm, which finds directed paths from the source node to the sink node with available capacity on edges in this path. In the algorithm, this pathsearching process is repeated until no additional flow can be added to this directed path. The algorithm uses the concept of so called residual networks (Ahuja et al., 1988), which represents the maximum additional flow that can be sent from any node i to any node j using the arcs i,j) and (/, /). 

---