Ravindra K. Ahuja.

Network flows online

. (page 1 of 18)
Online LibraryRavindra K. AhujaNetwork flows → online text (page 1 of 18)
Font size
QR-code for this ebook


^"V.



^^




Dewey



WORKING PAPER
ALFRED P. SLOAN SCHOOL OF MANAGEMENT



NETWORK FLOWS



Ravindra K. Ahuja
Thomas L. Magnanti
James B. Orlin



Sloan W.P. No. 2059-88



August 1988
Revised: December, 1988



MASSACHUSETTS

INSTITUTE OF TECHNOLOGY

50 MEMORIAL DRIVE

CAMBRIDGE, MASSACHUSETTS 02139



NETWORK FLOWS



Ravindra K. Ahuja
Thomas L. Magnanti
James B. Orlin



August 1988
Sloan W.P. No. 2059-88 Revised: December, 1988



NETWORK FLOWS



Ravindra K. Ahuja* , Thomas L. Magnanti, and James B. Orlin
Sloan School of Management
Massachusetts Institute of Technology
Cambridge, MA. 02139



On leave from Indian Institute of Technology, Kanpur - 208016, INDIA



MIT. LffiRARF

JUN 1 - ^



NETWORK FLOWS
OVERVIEW



Introduction

1.1 Applications

1.2 Complexity Analysis

1.3 Notation and Definitions

1.4 Network Representations

1.5 Search Algorithms

1.6 Developing Polynomial Time Algorithms

Basic Properties of Network Flows

21 Flow Decomposition Properties and Optimality Conditions
Z2 Cycle Free and Spanning Tree Solutions
Z3 Networks, Linear and Integer Programming
24 Network Transformations

Shortest Paths

3.1 Dijkstra's Algorithm

3.2 Dial's Implementation

3.3 R-Heap Implementation

3.4 Label Correcting Algorithms

3.5 All Pairs Shortest Path Algorithm

Maximum Flows

4.1 Labeling Algorithm and the Max-Flow Min-Cut Theorem

4.2 Decreasing the Number of Augmentations

4.3 Shortest Augmenting Path Algorithm

4.4 Preflow-Push Algorithms

4.5 Excess-Scaling Algorithm

Minimum Cost Flows

5.1 Duality and Optimality Conditions

5.2 Relationship to Shortest Path and Maximum Flow Problems

5.3 Negative Cycle Algorithm

5.4 Successive Shortest Path Algorithm

5.5 Primal-Dual and Out-of-Kilter Algorithnns

5.6 Network Simplex Algorithm

5.7 Right-Hand-Side Scaling Algorithm

5.8 Cost Scaling Algorithm

5.9 Double Scaling Algorithm

5.10 Sensitivity Analysis

5.11 Assignment Problem

Reference Notes
References



Network Flows

Perhaps no subfield of mathematical programming is more alluring than
network optimization. Highway, rail, electrical, communication and many other
physical networks pervade our everyday lives. As a consequence, even non-specialists
recognize the practical importance and the wide ranging applicability of networks.
Moreover, because the physical operating characteristics of networks (e.g., flows on arcs
and mass balance at nodes) have natural mathematical representations, practitioners and
non-specialists can readily understand the mathematical descriptions of network
optimization problems and the basic ruiture of techniques used to solve these problems.
This combination of widespread applicability and ease of assimilation has undoubtedly
been instrumental in the evolution of network planning models as one of the most
widely used modeling techniques in all of operatior^s research and applied mathematics.

Network optimization is also alluring to methodologists. Networks provide a
concrete setting for testing and devising new theories. Indeed, network optimization has
inspired many of the most fundamental results in all of optimization. For example,
price directive decomposition algorithms for both linear programming and
combinatorial optimization had their origins in network optimization. So did cutting
plane methods and branch and bound procedures of integer programming, primal-dual
methods of linear and nonlinear programming, and polyhedral methods of
combinatorial optimization. In addition, networks have served as the major prototype
for several theoretical domaiiis (for example, the field of matroids) and as the core model
for a wide variety of min/max duality results in discrete mathematics.

Moreover, network optimization has served as a fertile meeting ground for ideas
from optimization and computer science. Many results in network optimization are
routinely used to design and evaluate computer systems, and ideas from computer
science concerning data structures and efficient data manipulation have had a major
impact on the design and implementation of many network optimization algorithms.

The aim of this paf>er is to summarilze many of the fundamental ideas of network
optimization. In particular, we concentrate on network flow problems and highlight a
number of recent theoretical and algorithmic advances. We have divided the discussion
into the following broad major topics:



Applications

Basic Prof)erties of Network Flows
Shortest Path Problems ''

Maximum Flow Problems
Minimum Cost Flow Problems
AssigTunent Problems

Much of our discussion focuses on the design of provably good (e.g.,
polynomial-time) algorithms. Among good algorithms, we have presented those that
are simple and are likely to be efficient in practice. We have attempted to structure our
discussion so that it not only provides a survey of the field for the specialists, but also
serves as an introduction and summary to the non-specialists who have a basic working
knowledge of the rudiments of optimization, particularly linear programming.

In this chapter, we limit our discussions to the problems listed above. Some
important generalizations of these problems such as (i) the generalized network flows;
(ii) the multicommodity flows; and (iv) the network design, will not be covered in our
survey. We, however, briefly describe these problems in Section 6.6 and provide some
important references.

As a prelude to the remainder of our discussion, in this section we present
several important preliminaries . We discuss (i) different ways to measure the
performance of algorithms; (ii) graph notation and vtirious ways to represent networks
quantitively; (iii) a few basic ideas from computer science that underUe the design of
many algorithms; and (iv) two generic proof techniques that have proven to be useful
in designing polynomial-time algorithms.

1.1 Applications

Networks arise in numerous application settings emd in a variety of guises. In
this section, we briefly describe a few prototypical applications. Our discussion is
intended to illustrate a range of applications and to be suggestive of how network flow
problems arise in practice; a more extensive survey would take us far beyond the scope
of our discussion. To illustrate the breadth of network applications, we consider some
models requiring solution techniques that we will not describe in this chapter.

For the purposes of this discussion, we will consider four different types of
networks arising in practice:



• Physical networks (Streets, railbeds, pipelines, wires)

• Route networks

• Space-time networks (Scheduling networks)

• Derived networks (Through problem trai^formations)

These four categories are not exhaustive and overlap in coverage. Nevertheless,
they provide a useful taxonomy for summarizing a variety of applications.

Network flow models are also used for several purposes:

• Descriptive modeling (answering "what is?" questions)

• Predictive modeling (answering "what will be?" questions)

• Normative modeling (answering "what should be?" questions, that is,

performing optimization)

We will illustrate models in each of these categories. We first introduce the basic
underlying network flow model and some useful notation.

The Network Flow Model

Let G = (N, A) be a directed network with a cost Cjj, a lower bound /,;, and a
capacity Uj; associated with every arc (i, j) e A. We associate with each node i e N an

integer number b(i) representing its supply or demand. If b(i) > 0, then node i is a supply
node; if b(i) < 0, then node i is a demand node; and if b(i) = 0, then node i is a transhipment
node. Let n = | N | and m = | A |. The minimum cost network flow problem can be
formulated as follows:

Minimize ^ C;; x;: (1.1a)

(i,j)€A^ '

subject to

X^ii - Xxji =b(i), foralli€N, (1.1b)

{j:(i,j)e]\} {j:(j,i)6^A}

/jj < Xjj S u^ . for all (i, j) e A. (1 .Ic)

We refer to the vector x = (xjj) as the flow in the network. The constraint (1.1b)
implies that the total flow out of a node minus the total flow into that node must equal



the net supply /demand of the node. We henceforth refer to this constraint as the moss
balance constraint. The flow must also satisfy the lower bound and capacity constraints
(1.1c) which we refer to as the flow bound constraints. The flow bounds might model
physical capacities, contractual obligations or simply operating ranges of interest.
Frequently, the given lower bounds /j; are all zero; we show later that they can be made

zero without any loss of generality.

In matrix notation, we represent the minimum cost flow problem

minimize { ex : Nx = b and / < x S u ), (1.2)

in terms of a node-arc incidence matrix N. The matrix N has one row for each node of the
network and one column for each arc. We let Njj represent the column of N

corresponding to arc (i, j), and let e; denote the j-th unit vector which is a column vector

of size n whose entries are all zeros except for the )-th entry which is a 1. Note that each
flow variable x-; app>ears in two mass balance equations, as an outflow from node i with

a +1 coefficient and as an inflow to node j with a -1 coefficient. Therefore the column
corresponding to arc (i, j) is Nj; = Cj - e; .

The matrix N has very special structure: only 2m out of its nm total entries are
nonzero, all of its nonzero entries are +1 or -1, and each column h 0) i € {N : b(i) < 0)

Consequently, total supply must equal total demand if the mass balance

cor\straints are to have any feasible solution.

(ii) If the total supply does equal the total demand, then summing all the mass
balance equations gives the zero equation Ox = 0, or equivalently, any equation is
equal to minus the sum of all other equations, and hence is redundant.

The following special ccises of the minimum cost flow problem play a central role in the
theory and applications of network flows.





(a) An example network.



1
2
3
4

5



(1,2)


0,3)


(2,3)


(2,4)


(3,5)


(4,5)


(5,4)


1


1

















-1





1


1














-1


-1





1

















-1





1


-1














-1


-1


1



(b) The node-arc incidence matrix of the example network

Figure 1.1. An example of the matrix N.

The shortest path problem. The shortest path problem is to determine directed paths of
smallest cost from a given node 1 to all other nodes. If we choose the data in the
minimum cost flow problem as b(l) = (n - 1), b(i) = -1 for all other nodes, and /jj =
jmd Ujj = n for all arcs, then the optimum solution sends unit flow from node 1 to
every other node along a shortest path.

The maximum flow problem. The maximum flow problem is to send the maximum

possible flow in a network from a specified source node s to a specified sink node t. In the
minimum cost flow problem, if we add an additional arc (t, s) with c^ = -1 and u^^ =

«», set the supply/demand of all nodes cmd costs of all arcs to zero, then the mirumum
cost solution maximizes the flow on arc (t, s) which equals the maximum possible flow
from the source node to the sink node.

The assignment problem. The data of the assignment problem consists of a set N|, say
of persons, and a set N2, say of objects, satisfying | N^ | = | N2 I , a collection of node pairs



A c Nj X N2 representing possible person-to-object assignments, and a cost C;;
associated with each element (i, j) in A. The objective is to assign each person to exactly

one object in a way that minimizes the cost of the assignment. The Jissignment problem
is a minimum cost flow problem on a network G = (N^ u N2, A) with b(i) = 1 for all i

e Nj and b(i) = -1 for all i e N2 (we set l^:= and u^; = 1 for all (i, j) € A).

Physical Networks "^

The familiar city street map is perhaps the prototypical physical network, and the
one that most readily comes to inind when we envision a network. Many network
planning problems arise in this problem context. As one illustration, consider the
problem of managing, or designing, a street network to decide upon such issues as speed
limits, one way street assignments, or whether or not to construct a new road or bridge.
In order to make these decisions intelligently, we need a descriptive model that tells us
how to model traffic flows and measure the performance of any design as well as a
predictive model for measuring the effect of any change in the system. We can then use
these models to answer a variety of "what if planning questions.

The following type of equilibrium network flow model permits us to answer
these types of questions. Each line of the network has an associated delay function that
specifies how long it takes to traverse this link. The time to do so depends upon traffic
conditions; the more traffic that flows on the link, the longer is the travel time to
traverse it. Now also suppose that each user of the system has a point of origin (e.g., his
or her home) and a point of destination (e.g., his or her workplace in the central
business district). Each of these users must choose a route through the network. Note,
however, that these route choices affect each other; if two users traverse the same link,
they add to each other's travel time because of the added congestion on the link. Now let
us make the behavioral assumption that each user wishes to travel between his or her
origin and destination as quickly as possible, that is, along a shortest travel time path.
This situation leads to the following equilibrium problem vdth an embedded set of
network optimization problems (shortest path problems); is there a flow pattern in the
network with the property that no user can unilaterally change his (or her) choice of
origin to destination path (that is, all other ULsers continue to use their specified paths in
the equilibrium solution) to reduce his travel time. Operations researchers have
developed a set of sophisticated models for this problem setting, as well as related theory
(concerning, for example, existence and uniqueness of equilibrium solutions), and
algorithms for computing equilibrium solutions. Used in the mode of "what if



scenario analysis, these models permit analysts to answer the type of questions we posed
previously. These models are actively used in practice. Indeed, the Urban Mass Transit
Authority in the United States requires that communities perform a network
equilibrium impact analysis as part of the process for obtaining federal funds for highway
construction or improvement.

Similar types of models arise in many other problem contexts. For example, a
network equilibrium model forms the heairt of the Project Independence Energy Systems
(LPIES) model developed by the U.S. Department of Energy as an analysis tool for
guiding public policy on energy. The basic equilibrium model of electrical networks is
another example. In this setting. Ohm's Law serves as the analog of the congestion
function for the traffic equilibrium problem, and Kirkhoff s Law represents the network
mass balance equations.

Another type of physical network is a very large-scale integrated circuit (VLSI
circuit). In this setting the nodes of the network correspond to electrical components
and the links correspond to wires that connect these links. Numerous network
planning problems arise in this problem context. For example, how can we lay out , or
design, *.he smallest possible integrated circuit to make the necessary connections
between its components and maintain necessary sejjarations between the wires (to avoid
electrical interference).

Route Networks

Route networks, which are one level of abstraction removed from physical
networks, are familiar to most students of operations research and management science.
The traditional operations research transportation problem is illustrative. A shipper
with supplies at its plants must ship to geographically dispersed retail centers, each with
a given aistomer demand. Each arc connecting a supply point to a retail center incurs
costs based upon some physical network, in this case the transportation network. Rather
than solving the problem directly on the physical network, we preprocess the data and
construct transportation routes. Consequently, an arc connecting a supply point and
retail center might correspond to a complex four leg distribution channel with legs
(i) from a plant (by truck) to a rail station, (ii) from the rail station to a rail head
elsewhere in the system, (iii) from the rail head (by truck) to a distribution center, and
(iv) from the distribution center (on a local delivery truck) to the final customer (or even
in some cases just to the distribution center). If we assign the arc with the composite



distribution cost of all the intermediary legs, as well as with the distribution capacity for
this route, this problem becomes a classic network transportation model: find the flows
from plants to customers that minimizes overall costs. This type of model is used in
numerous applications. As but one illustration, a prize winning practice paper written
several years ago described an application of such a network planning system by the
Cahill May Roberts Pharmaceutical Company (of Ireland) to reduce overall distribution
costs by 20%, while improving customer service as well.

Many related problems arise in this type of problem setting, for instance, the
design issue of deciding upon the location of the distribution centers. It is possible to
address this type of decision problem using integer programming methodology for
choosing the distribution sites and network flows to cost out (or optimize flows) for any
given choice of sites; using this approach, a noted study conducted several years ago
permitted Hunt Wesson Foods Corporation to save over $1 million annually.

One special case of the transportation problem merits note — the assignment
problem that we introduced previously in this section. This problem has numerous
applications, particularly in problem contexts such as machine scheduling. In this
application context, we would identify the supply points with jobs to be performed, the
demand points with available machines, and the cost associated with arc (i, j) as the cost
of completing job i on machine j. The solution to the problem specifies the minimum
cost assignment of the jobs to the machines, assuming that each machine has the
capacity to perform only one job.

Space Time Networks

Frequently in practice, we wish to schedule some production or service activity
over time. In these instances it is often convenient to formulate a network flow problem
on a "space— time network" with several nodes representing a particular facility (a
machine, a warehouse, an airport) but at different points in time.

Figure 1.2, which represents a core planning model in production planning, the
economic lot size problem, is an important example. In this problem context, we wish to
meet prescribed demands d^ for a product in each of the T time periods. In each
period, we can produce at level Xj and /or we can meet the demand by drav^g upon
inventory I^ from the previous f)eriod. The network representing this problem has

T + 1 nodes: one node t = 1, 2, . . . , T represents each of the planning periods, and one



node represents the "source" of all production. The flow on arc (0, t) prescribes the
production level Xj in period t, and the flow on arc (t, t + 1) represents the inventory

level I^ to be carried from period t to period t + 1 . The mass balance equation for each

period t models the basic accounting equation: incoming inventory plus production in
that period must equal demand plus final inventory. The mass balance equation for
node indicates that all demand (assuming zero beginning and zero fir\al inventory
over the entire planning period) must be produced in some period t = 1, 2, . . . , T.
Whenever the production and holding costs are linear, this problem is easily solved as a
shortest path problem (for each demand period, we must find the minimum cost path of
production and inventory arcs from node to that demand point). If we impose
capacities on production or inventory, the problem becomes a minimum cost network
flow problem.

Id,




Figure 1^. Network flow model of the economic lot size problem.



One extension of this economic lot sizing problem arises frequently in practice.
Assume that production x^ in any period incurs a fixed cost: that is, whenever we

produce in period t (i.e., x^ > 0), no matter how much or how little, we incur a fixed cost

T^. In addition , we may incur a per unit production cost c^ in period t and a per unit

inventory cost h^ for carrying any unit of inventory from period t to i>eriod t + 1.

Hence, the cost on each arc for this problem is either linear (for inventory carrying arcs)
or linear plus a fixed cost (for production arcs). Consequently, the objective function for



10



the problem is concave. As we indicate in Section 2.2 , any such concave cost network
flow problem always has a special type of optimum solution known as a spanning trees
solution. This problem's spanning tree solution decomposes into disjoint directed paths;
the first arc on each path is a production arc (of the form (0, t)) and each other arc is an
inventory carrying arc. This observation implies the following production property: in the
solution, each time we produce, we produce enough to meet the demand for an integral
number of contiguous periods. Moreover, in no period do we both carry inventory from
the previous period and produce.

The production property permits us to solve the problem very efficiently as a
shortest path problem on an auxiliary network G' defined as follows. The network G'
consists of nodes 1 to T + 1, and for every pair of nodes i and j with i < j, it contains
an arc (i, j). The length of arc (i, j) is equal to the production and inventory cost of
satisfying the demand of the periods from i to j-1. Observe that for every production
schedule satisfying the production property, G' contair\s a directed path in G' from node
1 to node T + 1 of the same objective function veilue and vice-versa. Hence we can
obtain the optimum production schedule by solving a shortest path problem.

Many enhancements of the model are possible, for example (i) the production
facility might have limited production capacity or limited storage for inventory, or
(ii) the production facility might be producing several products that are linked by
common production costs or by changeover cost (for example, we may need to change
dies in an automobile stamping plant when making different types of fenders), or that
share common limited production facilities. In most cases, the enhanced models are
quite difficult to solve (they are NP


1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Online LibraryRavindra K. AhujaNetwork flows → online text (page 1 of 18)