\
FEASIBLE FLOWS IN MULTICOMMODITY
GRAPHS
by
Holly Sue Zullo
B. S., Rensselaer Polytechnic Institute, 1991
M. S., University of Colorado at Denver, 1993
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
Applied Mathematics
1995
This thesis for the Doctor of Philosophy
degree by
Holly Sue Zullo
has been approved by
David Fisher
Date ^ ; ~ S
Zullo, Holly Sue (Ph. D., Applied Mathematics)
Feasible Flows in Multicommodity Graphs
Thesis directed by Professor Harvey Greenberg
ABSTRACT
This thesis establishes the minimal representation of the neces
sary conditions for feasible supplies and demands for a given multicom
modity network. The fundamental theorem is an extension of the Wallace
Wets connectivity result for both directed and undirected graphs. A sys
tem of absolute value inequalities is developed for the undirected case, and
special properties of this system are explored. Additional results include
counting the number of nonredundant inequalities for specific classes of
graphs.
This abstract accurately represents the content of the candidates thesis.
I recommend its publication. Signed.,
m
Harvey Greenberg
CONTENTS
Chapter
1. Introduction............................................. 1
2. Technical Background.................................... 3
2.1 Terms and Concepts.................................. 3
2.2 The Literature...................................... 6
3. The WallaceWets Theorem................................ 13
4. Feasibility in Directed Multicommodity Graphs........... 22
4.1 Preliminaries...................................... 22
4.2 The System......................................... 25
4.3 Redundancy Theorem................................. 29
5. Feasibility in Undirected Multicommodity Graphs .... 35
5.1 The Absolute Value System.......................... 35
5.2 Redundancy Theorem................................. 42
5.3 Some Building Blocks............................... 47
6. Avenues for Further Research............................ 56
Glossary........................................................ 58
Bibliography ................................................... 59
1. Introduction
The set of feasible supplies and demands for a network flow prob
lem can be described by a system of linear inequalities. Wallace and Wets
have characterized the redundant inequalities in this system. The main
theorem of this thesis is an extension of the WallaceWets Theorem to
the case of undirected multicommodity graphs. In order to obtain the
extension, a special system of inequalities is developed and several char
acteristics of this system are discussed. Following the extension, we prove
several theorems on its usefulness.
In Chapter 2 we provide technical background on network flows.
We discuss some differences between single and multicommodity network
flows, as well as the pertinent literature on multicommodity flows. We
also discuss the background literature for the WallaceWets Theorem.
In Chapter 3 we present the WallaceWets Theorem for single
commodity networks along with a detailed proof of the theorem.
Chapters 4 and 5 contain the main results of the thesis. In Chap
ter 4 we show that the WallaceWets Theorem has a natural extension to
directed multicommodity graphs. In Chapter 5 we consider the case of
undirected multicommodity graphs, which is not as straightforward. A
system of inequalities which gives a necessary condition for feasible sup
plies and demands for undirected multicommodity graphs is developed,
and we explore properties of this system. Next we present our extension
of the WallaceWets Theorem. We also present several theorems related
to using the extension and the benefit realized.
In Chapter 6 we suggest avenues for further research. This in
cludes further work related to the system of inequalities developed in
Chapter 5, as well as evaluating the effects of preclassification of nodes
as supply, demand, and transshipment nodes.
2
2. Technical Background
2.1 Terms and Concepts
Let G = [V, E] be a finite graph with node set V and edge set
E. For the problems we will consider in this thesis, there is no loss in
generality to assume G does not contain any parallel edges. We therefore
denote an edge by its endpoints: (i,j). This is an unordered pair in the
context of undirected graphs, but an ordered pair in the context of directed
graphs. We also assume, without loss in generality, that G is connected.
For any Y C V, let ~ Y denote the complement of Y: ~ Y
{i G V : i T}. Then the associated cut is the edge set:
G E : i G Y and j G~ T}. Note that for undirected graphs, < Y, ~
Y > = <~ Y,Y >, but that this is not true for directed graphs. For each
{i,j) G E there is a capacity Uij which limits total flow across the edge.
This extends naturally to subsets of E: U(Y,~ Y) = Zi(Jj)e Uij.
For each Y C V, we let G(Y) denote the induced subgraph on the node
set Y.
For each i G F, we let the demand at node i be given by 6,. That
is, if bi > 0 then node i has a demand, if b{ < 0 then node i has a supply,
and if b{ = 0 then node i has neither demand nor supply.
In the context of multicommodity graphs, and will denote
the origin and destination, respectively, of commodity fc, k = l,2,...,p.
We will let represent the demand for commodity k. If the origin and
destination of each commodity are not known, then b\ represents the de
mand for commodity k at node i.
The work in this thesis deals mainly with multicommodity graphs.
It is well known that many of the nice properties associated with network
flow problems do not extend to the multicommodity case. A complicat
ing matter in multicommodity flows is that flows in opposite directions
on an edge do not cancel if they are different commodities. This leads to
a variety of problems. In a single commodity network flow problem, the
maximum flow is equal to the minimum cut, and given integer capacities,
the maximum flow is guaranteed to be integer. Neither of these proper
ties extend to the general multicommodity case. Additionally, in single
commodity network flow problems, the condition that the capacity of any
cut is greater than or equal to the demand across the cut, is a necessary
as well as sufficient condition for feasibility of the network. That is, if q is
the required amount of flow to be sent through the network, the network
is feasible if and only if
q
The analogous multicommodity condition
^2(qk Y separates sk and tk ) < U(Y,~ Y) MY C V
is necessary for undirected graphs, but it is not sufficient for feasibility in
general. Much work has been done to determine specific classes of graphs
for which this condition is sufficient, and we will examine several of the
results in the next section. We now present some examples of the above
statements.
4
Example
S2 ^3
34 12
Assume a capacity of 1 on each edge. A maximum flow is given
by the following, where X{ is the flow vector for edge i.
Also, the value of the maximum flow, which is the sum of the flows for
each commodity, isl +  +  +  = 3. The notion of a cut in single
commodity graphs translates to a disconnecting set in multicommodity
graphs, that is, a set of edges whose removal will disconnect the origin and
destination of each commodity. For more on disconnecting sets, see [3]. A
The flow is fractional, even though the capacities are integer.
minimum disconnecting set for this graph consists of the edges {a, c, d, /}.
The capacity of this set is 4, which is not equal to the maximum flow.
Example
Si ti
Suppose the capacity of each edge is 1, and the demand for each
commodity is 1. That is, we wish to send one unit of commodity 1 from
si to 11, and so on. It can be verified that the cut condition,
^2(qk y separates sk and tk ) < U(Y,~ T),
holds for every set Y. For example, if Y = {si}, then < Y, ~ Y > =
{a, 6, c}, so U(Y, ~ Y) = 3. The only commodity separated by Y is
commodity 1, so the lefthandside of the cut condition is 1. Thus the
inequality holds, as could be shown for every Y. However, it is not possible
to satisfy all of the demands simultaneously, so the problem is not feasible.
2.2 The Literature
As discussed in the previous section, a central issue in the study
of multicommodity network flow problems is that the cut condition,
JJ(qk : Y separates sk and tk ) < U(Y,~ V'),
6
is not always a sufficient condition for feasibility. Here we will present
several of the results which characterize graphs for which this condition is
sufficient for feasibility. We refer the reader to the appropriate papers for
the proofs. As the results are very diiferent for the undirected and directed
cases, we will discuss them separately, beginning with the undirected case.
Some of the pioneering work on this subject was done by T.C.
Hu ([16],[17]). Hu proved that the cut condition is sufficient for feasibility
if there are only two commodities. Additionally, he proved that in the
twocommodity case, the maximum sum of the flows is equal to the min
imum capacity of all cuts separating the origins and destinations of both
commodities (the minimum disconnecting set). He provided an algorithm
for constructing the flows. Finally, Hu showed that if the demands and
the capacities are all even integers, then a twocommodity flow will have
the property that the flows for each commodity on each edge are integer.
This is commonly referred to as a halfinteger property, and it arises in
other cases as well.
Hus result is the only one that relies on a specific number of
commodities, and it does not generalize to three or more commodities.
All other results rely on the graph having special characteristics.
A few definitions are in order before we discuss the next result.
A planar graph is a graph that can be drawn in the plane so that no edges
cross. Given a fixed drawing of a planar graph, we can identify various
regions, which are simply the areas enclosed by the edges of the graph. The
infinite region is the entire region outside the graph, and the boundary of
the infinte region consists of the nodes and edges that separate the infinite
i
1
2
C
Figure 2.1: A Planar Graph and Its Regions
region from the interior of the graph. For example, in Figure 2.1, A is
the region enclosed by the edges (1,2), (2,3), and (1,3); B is the region
enclosed by the edges (1,3), (3,4), and (1,4); C is the infinite region. The
boundary of the infinite region is 1, (1,2), 2, (2,3), 3, (3,4), 4, (4,1). Note
that we could also draw the graph with edge (1,3) on the other side of
node 2. This would still be a planar representation, but different regions
would be defined. The boundary of the infinite region for that drawing
would be 1, (1,3), 3, (3,4), 4, (4,1).
We are now ready for the theorem of Okamura and Seymour
([28]).
Theorem 2.1 (Okamura and Seymour, 1981) If G is pla
nar and can be drawn in the plane so that si, 52, ., sp, G, t2, ,tp are
all on the boundary of the infinite region, then
^2{qk ' y separates Sk and tk ) < U(Y,~ Y)
is a sufficient condition for feasibility. Further, if the demands and capac
ities are all integers, then there exists a set of feasible flows with the flow
for each commodity on each edge being integer.
8
That is, if a graph can be drawn in the plane so that all the
sources and sinks are on the boundary of the infinite region, then the cut
condition is sufficient for feasibility. There have been some extensions of
this theorem which relax slightly the condition of all the sources and sinks
being on the boundary of the infinite region. Okamura ([27]) proved that
the cut condition is sufficient if G is a planar graph and can be drawn
with one set of sources and sinks on the boundary of any region, and the
remainder of the sources and sinks on the boundary of the infinite region,
with the source and sink for any one commodity on the same boundary. In
the same paper, it is shown that the cut condition is also sufficient if G is
planar and can be drawn with the sources and sinks for some commodities
located on the boundary of the infinite region, and all other commodities
share the same sink, also located on the boundary of the infinite region,
but those sources may be located anywhere. Seymour ([39]) proved that
the cut condition is sufficient if G is a planar graph and if the source
and sink for each commodity may be joined by an edge without violating
planarity. For a discussion of all of the above results plus algorithms for
finding planar multicommodity flows, the reader is referred to [26],
The final class of undirected graphs that we will present here
actually relies on the configuration of the sources and sinks of the com
modities. We call this configuration the commodity graph. Given a con
nected undirected network G = [V, E\ with sources $2,. , sp and sinks
ti,t2,. .tp, let the commodity graph. H = [T,U],(T C V) be the undi
rected graph whose edges correspond the the sourcesink pairs of G. That
is, e 6 U <==> e = (sk,tk). Note that U is not necessarily a subset of E.
9
Example Given the following graph
S2 ts
by drawing each node and then con
The resulting graph is
we construct the commodity graph
necting Si to A, S2 to t2, and so on.
Karzanov ([19]) presents a result of Papernov regarding the com
modity graph.
Theorem 2.2 (Papernov, 1976) (1) If H is A'4 (the com
plete graph on four nodes), C5 (the cycle on five nodes), or a union
of two stars, and if the cut condition is satisfied, then the problem is
feasible.
(2) If H is a graph which does not belong to the collection above, then
there exists a graph G, capacities U, and demands <7, such that the
cut condition is satisfied and yet the problem is not feasible.
10
In other words, the cut condition can be known to be sufficient
based only on the commodity graph if and only if the commodity graph is
a complete graph on four nodes, a cycle on five nodes, or a union of two
stars. If the commodity graph is other than the graphs mentioned, then
it is possible to construct a graph which has that commodity graph and
for which the cut condition is not sufficient for feasibility.
We are now ready to discuss some results on feasibility in directed
graphs. As mentioned earlier, the directed case is very different from the
undirected case, and it has received much less attention in the literature.
Note that in the case of directed graphs, the cut condition changes slightly
to become
XX: sk e Ytk X UiYi~ Y)
It is known that Hus result for twocommodity graphs does not extend to
the multicommodity case ([21]). However, the cut condition is sufficient
for feasibility if the network is planar with all the sources on the left side
and all the sinks on the right side (a transportation network) and if the
sources and sinks appear in the same order (see [29]). The main work is by
Nagamochi and Ibaraki, and we will give a brief overview of their results.
In several papers and a Ph.D. thesis ([22], [23], [24]), Nagamochi
and Ibaraki studied directed multicommodity networks. They developed
three classes of networks, capacity balanced (CB), capacity semibalanced
(CS), and capacity semibalanced unilateral (CU). In a CB network, the
capacity is balanced at each node. That is, for every node, the capacity
on outgoing arcs plus the demand at the node is equal to the capacity on
incoming arcs plus the supply at the node. It is shown that the maxflow
11
mincut theorem holds for multicommodity networks in CB, and also that
the flows will be integer if the capacities and demands are integer. The
class CS is shown to be a relaxation of class CB, and the same properties
shown for CB networks also hold for CS networks. Finally, it is shown
that the properties do not extend to CU networks.
For a more general survey of multicommodity network flows, see
either [1] or [21].
The foundations needed for the WallaceWets Theorem come
from the work done by Gale and Hoffman for singlecommodity network
flow problems. In [11], Gale gives a system of linear inequalities which are
necessary and sufficient for feasibility of a set of supplies and demands in
a network. Hoffman ([15]) extends this result to feasible circulations. The
inequalities are those generated by considering all bipartitions of the ver
tices of the network. It is assumed that any node may be a supply node,
demand node, or transshipment node. The resulting system of inequalities
is
Â£ bt
ie~Y
for all Y C V. This is the system which Wallace and Wets work with, and
the inequalities will be referred to as the GaleHoffman inequalities.
12
3. The WallaceWets Theorem
In [43], [44], [45], Wallace and Wets examine the system of in
equalities which describe the feasible supplies and demands for a network.
The inequalities are the ones given by Gale and Hoffman, and Wallace
and Wets determine the mimimum number of inequalities needed.
The WallaceWets Theorem gives a characterization of the redun
dant inequalities based on a connectedness criterion. The GaleHoffman
inequalities can be generated from all possible partitions of the vertices
into two sets. Wallace and Wets prove that the resulting inequality is
redundant if and only if the induced subgraph on at least one of the par
titions is not connected. Their theorem is the following.
Theorem 3.1 [WallaceWets Theorem] For all nonempty Y C
V', the associated inequality,
Â£ bi
is redundant in the cut system if and only if either G(Y) or G(~ Y) is not
connected.
It is important to note that this theorem applies to the case
where all supplies must be used and all demands must be met exactly.
Thus, the cut system also includes the equation XkeV" 6, = 0, or supply
equals demand. For more on this and other aspects of the WallaceWets
Theorem, see [14].
We present a proof of the WallaceWets Theorem for complete
ness and to clarify several of their steps. The sufficiency part of the proof
is done by construction. We assume that either G(Y) or G(~ Y) is not
connected, and we show how to construct the dependency set for the in
equality corresponding to Y. For the necessity part of the proof, we first
prove a lemma showing that we may restrict our consideration of the right
handsides to an arc membership function. We then show that the only
sets which may be used in constructing a redundant inequality are those
whose cutset arcs are a subset of the cutset arcs of the original set. If both
G(Y) and G'(~ Y) are connected, then there are no sets which have that
characteristic. Thus, the original inequality is not redundant.
Lemma 3.2 Let Yi define a partition of the vertices. If the in
equality corresponding to Y) is redundant, then the arcs in the union of the
cutsets for partitions corresponding to the inequalities in the dependency
set must be exactly the arcs in < Yi, ~ Y] > .
Proof: Since the inequality corresponding to Yi is redundant, there exist
Aj, A > 0, j = 1,2,..., such that
E fc = Â£ E a^aE^Ea
i Yi j*1 i Yj ieV
Let J be the set of j's such that Aj > 0.
First, assume there exists a E< Y/,~ Yt > such that a Yj, ~
Yj > \/j e J. Let a (a, (3) (a
contradiction. For any j E J if a Â£ Yj then 0 E Yj (or else a E< Yj,~
Yj >. Thus, 0 is in at least as many sets Yj as a, so 0 is in at most as
many sets ~ Yj as a. But since 0 Yi and a E Y[, we must have 0
14
in exactly one more set ~ Yj than a in order for the lefthandside of the
inequality to work out. So we have a contradiction. Thus, there does not
exist a G< V/,~ V/ > such that a Yj > Vj G J. This tells us
that the arcs of the cutset from Yi are a subset of the union of all arcs in
the cutsets from Yj for j G J
What we have left to show is that there is no arc in any set
< Yj,~ Yj >,j G J such that the arc is not in < Y/,~ V/ >. Let
a G< V/,~ Yi >,a = (a,0) where a G V/,/3 G~ V/. If the inequality from
Yi is redundant, then the following must be true:
E ^
J ' 0 Yj
A = 1
E
AJ = A
j : o G~ Yj
where the first equation comes from setting bp 1 and all other Vs to
zero, and the second equation comes from setting ba = 1 and all other 6,s
to zero. From the two equations above, we get that
Â£ ^
j : P <=~ Yj
This can be rewritten as
E
j : a G~
Aj = 1.
E A? + E ^ E ^ ~ E ^jy
j : 0 G~ Yj j : 0 G~ Yj a G~ Yj a G~ Yj
a G Y;i a G~ V 0 G V} /J G~ V)
The second and fourth terms cancel. Since the third term is nonnegative,
we have
Â£ A, > i.
j:(a,0)E
So the capacity of each edge in < V;. ~ V/ > is added in to Ylj^i ^jU(Vj, ~
Yj). Therefore, we cannot have a G< V},~ Yj >,j G J, and a (Â£<
15
V/,~ Yi > because that would give us Yljjzi ~ Yj) > U(Yi,~ Yi).
We are now ready to prove the WallaceWets Theorem. We re
state the theorem for convenience. Note that this theorem holds for both
the directed and undirected cases.
Theorem 3.1 For all nonempty Y C V, the associated inequal
ity,
Â£ k
is redundant in the cut system if and only if either G(Y) or G(~ Y) is not
connected.
Proof: We begin with the if direction. First, suppose G[Y) is not
connected. Let Y Y\ U Y2 where Y\ fl Y2 = 0 and there are no edges
between Y\ and Y2 (See Figure 3.1). Since there are no edges between Y\
and Y2, we know that < Vi,~ Yi > U < Y2,~ Y2 > < Y, ~ Y >. The
inequality from Y is
E l>i < ~Y) = Wi, ~ Yi) + U(Y2, ~ Y2).
The inequality from Y\ is
E b<= E6 + E bi = U{Yu~Y1).
ieY2
The inequality from Y2 is
E bi= E^ + E bi = U{Y2,~Y2).
iE~Y2 iEYi iÂ£~V
Summing, we get
E6+ E bi+'Â£bi+ E 6. = E6* + 2 E bi
iey2 ieYi ie~y ieY ie~Y
16
r^/
Y
Figure 3.1: Illustration of Y and ~ Y
Subtracting Yliev k = 0 leaves us with
Â£ bi
Therefore, the inequality from Y is redundant.
Next, suppose G(~ Y) is not connected. Let ~ Y = Yi U Y2
where Yi ft Y2 = 0 and there are no edges between Y\ and Y2. Thus,
< Y, ~ Y > = <~ Y\, Y\ > U <~ Y2, Y2 > Again the inequality from Y is
Â£ bt < U(Y, ~ Y) = tf(~ YUY1) + Ef(~ Y2, Y2).
iÂ£~V
The inequality from ~ Y\ is
Â£ bt < 6r(~ Vi, Vi).
ieYi
The inequality from ~ Y2 is
Â£ bt
ieY2
Summing, we get
Â£&,+Â£&; = Â£ bi
i&i iÂ£Y2 ie~Y
Therefore, the inequality from Y is redundant.
17
We now prove the only if direction. We assume that G(Yi)
and G(~ Yi) are both connected, and we will show that the inequality
corresponding to Vj cannot be redundant.
Let / index the set that is the complement of Y;, that is, Y] =~ V/.
Let o be the arc membership vector for the cut defined by Yj (cÂ£ = 1 <==>
a Â£< Yj, ~ Yj >). Also, let dJ be the node membership vector for the set
Yj (d{ 1 i Yj). Let Ji = {1,2,... ,2^vl} \ {/,{}. Let e be
the vector of ones. The term A0e will account for being able to subtract
multiples of the equation that states that total supply equals total demand.
We want to show that the following system has no solution:
c'= Â£ XjC3 + \i_cf
j g Ji
d! = Y. AjcP + XLdL X0e,
J G JI
Ao, A i_, A j > 0 Vj Â£ Ji
Suppose the system is feasible, and let {X,Xi_,(Xj,j Â£ J;)) be a solution.
Let
J? {j G Ji\Xj > 0}.
That is, indexes the inequalities which are used in constructing the
redundancy of inequality l.
If k (Â£< Vf, ~ Yi >, then clk = 0 and so
0 = ^ Xs4 + A/4 Vk Â£< Yh ~ Yi > .
j G
This equation tells us that <{. = 0 if k 9< l/,~ V/ > and if j Â£ J(+.
Written another way, this says: k 3< Y},~ Yj >> k 3< Yj,~ Yj > if
18
Yj
Figure 3.2: Illustration of Yj and Yj
j G If we negate the implication, we get that j 6 J,+ implies k G<
Yj, ~ Yj >> k G< T), ~ V; >. This then is the same as saying
j G J,+ +< Yj,~Yj >C< Yh~Y,>.
That is, we cannot use any sets whose cutset arcs are not a subset of the
arcs in < Y/,~ V/ >.
For all Yj C V, we define two new sets (see Figure 3.2):
Yj = Yj Pi Yi and Yj = Yj D V).
We will show that if Yj is such that either Yj is a proper subset
of 1) (0 ^ Yj + Y) or Yj is a proper subset of Tj (0 ^ Yj / Vj) then
j
constructing the redundancy of inequality /.
First we will work with Yj. If we write the equation for d\ (refer
ring back to the equation for dl) we have
d[ = '\(li + Mi ^0 e,.
J Ji
19
When G Yh d\ = 1, so we have
1 ^2 \jdj + 0 Ao
3 Ji
1 + A0= Â£ Xjdi VieY.
j Â£ ^
If g G /;+ and Yq is a proper subset of Yp then either there is
an arc from Yq to Yi \Yq, or there is an arc from YJ \Yq to Yq. Since
< Yq ~ Yq >C< Y/,~ Y/ >, there cannot be any arcs from Yq to Y) \ Y^.
Hence, there must be an arc from Yj \ Yq to Yq. Let this arc be
Now consider any set Yj such that i G Yj and j G J;+. Since
< Y},~ Yj >C< Y/,~ YJ >, we must also have F G Yp Thus, any set Yj
that contains i must also contain i'. This means that the following must
be true:
1 + A0 = ^2 Xjd{ < \ + ^2 'M;  = 1 + Ao,
j e j e j e
which is a contradiction. Therefore, there is no g G J;+ with Yq a proper
subset of YJ.
The same argument is used to show that there is not q G J;+ with
Yq a proper subset of Yp For this case, note that i G YJ => d\ 0, so we
have the equation
0 = ^2 ^jdi + A^ Aq
3 4+
A,A0= Â£ Xj^ VieYL.
j e J2
If q G J;+ and T9 is a proper subset of Yp then either there is
an arc from Yq to Y/ \ Yq or there is an arc from Yi_\Yq to Yq. Since
20
C< Yh ~ Yi >, there cannot be any arcs from Yq to Y\ \ Yq.
Hence, there must be an arc from Y\ \ Yq to Yq. Let this arc be
Now consider any set Yj such that i Â£ Yj and j Â£ J+. Since
< Yj,~ Yj >C< V/,~ Y\ >, we must also have i' Â£ Yj. Thus, any set Yj
that contains i must also contain i'. This means that the following must
be true:
A/ A0 = Â£ \ ^3 (^i = V),
J G
which is a contradiction. Therefore, there is no g Â£ J;+ with a proper
subset of Vp
Thus, the only index that could possibly belong to J;+ is the one
corresponding to V, say Yp = V. But then we would have
1 + Ao = Ap
Ao Ap
Ao 7 Ap Ap ^ b
which is not possible. Thus, Jf must be empty, but then we have
d! Xid1 Age
Ao,Ap > 0
which is also not possible.
Therefore, when G(T) and G(~ Y) are both connected,
Â£ bi
t e~y
is never redundant. I
21
4. Feasibility in Directed Multicommodity Graphs
4.1 Preliminaries
This thesis deals with linear multicommodity flows, ignoring in
teger restrictions. We begin by noting that a multicommodity network
with multiple sources and sinks for each commodity can be transformed
into a multicommodity network that has a single source and sink for each
commodity. This transformation is analogous to the transformation from
multiple sources/sinks to a single source/sink as given by Ford and Fulk
erson ([9]).
Theorem 4.1 A capacitated multicommodity network
N = [V, E, U] with multiple sources and multiple sinks for each com
modity can be transformed into an equivalent multicommodity network
N' = \V', E', U'} that has a single source and single sink for each commod
ity.
Proof: Let Sk C V and Tk C V be the indices for the set of sources and
sinks, respectively, for commodity k. Let bk : V > 9? be such that bk = 0
for i ^ Sk U Tk, bk < 0 for i Â£ Ski bk > 0 for i Â£ Tk, and Ylbk = 0 for each
k.
Construct N' as follows. V = V U {Ok,Dk}, and E E U
{(Ok,i : i e Sk),(i : i e Tk,Dk)}. U\Ok,i) = bk for i Â£ Sk, U\i,Dk) =
b, for i Â£ Tk, and U'{e) = U(e) for e Â£ E. b'^ T,t Â£ Skb^ b>Dk =
E* G Tk bkn % = 0 for i Â£ V \ (Sk U Tk).
Let x be any feasible flow in N. We will construct a feasible
flow x1 in AT Let (xke)' = xke for e Â£ E, (xQk )' = U'(Ok,i) for i Â£
S'jt, and (xkjjk)f = U'(i,Dk) for i Â£ Tk The capacity constraints are
satisfied for all edges by definition. We also need flow conservation at
each node. Ejxf,)' Y.i{x),i)' = E, E,^, = OVfc for i G V \
(S u n). E; S* E, e nCW =
E; g n b = V*' E,(i,)' ZMJ = (*Â£,*/ + E, 4, E,=
6 + 4f = OVi for i St. E,(4,)' T.,(xl,)' = Ejxj.i (Ejx^ +
(rj nk)') fof f>f = OVfc for r G Tk Therefore, t' is feasible in N'.
i,LJ
Conversely, let x' be any feasible flow in N'. We will construct
a feasible flow x in N. Let xk = (xk)' for e Â£ E. Since U'(e) = U(e)
for e Â£ E, = YLk{x
satisfied. Ei Ei Zj,; = E.fay'Ei^*,)' = OVA: for Â£ V\(SkUTk).
If Â£ Sk then E,(t>)' = (xqk )' + Ej}., Ejxfj = 0
=> Ej arj.t Ej xtj = bt If Tfc then Ejfaj,;)' Ej(xi,j)' = Ej xj,t ~
Ej ix>cpkY = 0 => Ej ^ Ej x^j = bi Therefore, x is feasible in
n. m
We illustrate this theorem with the following example.
Example
The following graph illustrates the addition of superorigins and
superdestinations for each commodity.
23
i
i
!
 For this example, node 01 has a supply of 4 (sj + and node
O2 has a supply of 6 + s^). Placing a capacity of 1 on edge (Oi,,sJ)
and a capacity of 3 on edge (O1,^) will insure that nodes s} and will
send the proper amounts of commodity 1. Similarly, we place a capacity
of 2 on edge (02,sf) and a capacity of 4 on edge (02,s2).
Node D2 has a demand of 6 {t\ + t^) and node Dl has a demand
of 4 (t\ + ^2) Placing a capacity of 4 on edge (t2, D2) and a capacity of
2 on edge (t%, D2) will insure that nodes t2 and t2 will receive the proper
amounts of commodity 2. Similarly, we place a capacity of 3 on edge
D1) and a capacity of 1 on edge (t\, D1).
Thus, we see that any flow that is feasible in the original network
is feasible in the new network, and vice versa.
Note that this theorem holds whether the graph is directed or
undirected. For the remainder of this thesis we will assume, without loss
24
of generality, that each commodity has a single origin and a single desti
nation.
4.2 The System
Wallace and Wets work with a system of inqualities which define
feasibility for a set of supplies and demands when the supply and demand
nodes are not known a priori. We wish to develop an analogous system
for the multicommodity case, and then we will characterize the redundant
inequalities in that system.
If the source and sink is known for each commodity, then a nec
essary condition for feasibility of a set of demands q is
: 1
This condition is sufficient for the classes of graphs identified by Nag
amochi and Ibaraki (see Chapter 2). In order to place this condition in
the Wallace and Wets setting, we need to generalize this condition for the
case where the supply and demand nodes are not know a priori.
Looking at the system for a single commodity,
Â£ bi
ie~Y
one might guess that the system for multicommodities can be obtained by
simply summing over each commodity. The resulting system is
Â£ Â£ <>
k=1
The following example shows that this is not enough.
25
Example
b\ Ul b2
O*
bl
6?
U2
O
bl
bl
The inequalities are:
Y = {1} : b\ + b22 + b32
Y = {2} : + fej < U2
This system allows for b\ = 1, b\ = 1, b\ = 1, b\ = 1, b\ = 1,
b\ = 1, and U\ = 1, u2 = 1. However, it is easily seen that this set of
demands and capacities are not feasible. Thus, we try a stronger system.
We actually need to sum over all possible combinations of com
modities. This results in
Â£ Â£ b$
kÂ£K iE~Y
where K is a nonempty set of commodities. This condition gives us the
desired system.
Theorem 4.2 The set of inequalities
Â£ Â£*?
keK
is a necessary condition for feasibility of 6, the vector of demands.
Proof: We start with the system of constraints for a directed multicom
modity flow problem,
Â£ x% Â£ ^
j(j>i)e<4 j\(hj)Â£A
X= 6?
\/l
26
E4
k=1
4 o vk,i,j
and we want to show that this system implies the inequality
E E t? = t/(v, ~ >')
kÂ£K iÂ£~Y
Recall that U(Y,~ Y) = Eu,i)ieY,ie~Y uji
We begin by working with the first constraint in the multicom
modity flow problem. First, we sum both sides of the equation over i Y
to obtain
E if = E ( E 4 E 4)
iÂ£~Y tÂ£~Y j(j,i)Â£i4 j\(i,j)Â£A
We next sum both sides over k 6 K, obtaining
E E % = E E.( E 4 E 4)
kÂ£K iÂ£~Y kÂ£K tÂ£~V j\(j,i)Â£A j\(i,j)Â£A
= EE E 4 EE E 4
kÂ£h iÂ£~Y j\(j,i)Â£A kÂ£K j'e~5 j\(iJ)EA
= E (E 4 + E 4 E 4 E 4)
kÂ£K ie~Y >e~v i6~r .e~y
ieE je~y jev' ie~y'
= E E 4 E E 4
fceA' te~v fcÂ£A' >e~y
jev' jev
Since > 0, we now have
E E < E E 4
keK ie~y keK
iey
Now if we work with the second constraint in the multicommodity flow
problem, again using the constraint that xfj > 0, we have
E 4 ^ E 4
keK k=1
27
This gives us
Â£ Â£4< Â£  = c/(v',~v').
JEY keK
This gives us our desired inequality,
Â£ Â£ $
kKie~Y
The next lemma relates this system to the system of inequali
ties for a directed multicommodity graph when the sources and sinks are
known a priori.
Lemma 4.3 The set of inequalities
Â£ Â£tf
keK te~y
contains the set of inequalities
: 1 < k
Proof: We know that qk = 6^ = ~bkSk and bk = 0 for i ^ Sk,tk for all
k. We have a set of inequalities for each set of commodities; in particular,
pick K' such that Vfc G K', s^Gf and tk G~ Y. So our system contains
the inequalities
Â£ Â£4f < u(Y, ~ Y) vy c v.
keK> ie~v
The left side of this inequality has bk for i = tk and bk = 0 for all other
i G~ y. For i = tk, bk = qk, so the summation yields J2kei< Qk M
We now have a system of linear inequalities which serve as a
necessary condition for feasibility of multicommodity flows in a directed
28
graph when the supply and demand nodes are not known a priori. In the
next section, we will extend the WallaceWets Theorem to this system.
4.3 Redundancy Theorem
The WallaceWets Theorem extends quite naturally to the di
rected case. Using the system from the previous section, along with the
requirement that supply equals demand for each commodity, we are able
to characterize the redundancy in the system. This characterization is
the same as the WallaceWets characterization for the single commodity
system with one exception. For our system we need to separate the cases
of U{Y, ~ Y) = 0 and [7(~ Y, Y) = 0.
Theorem 4.4 [Redundancy Theorem for Directed Graphs] Let
G be a connected, capacitated, directed, multicommodity graph with p
commodities, where each commodity has one origin and one destination.
(1) If U(Y,~ Y) > 0 and f/(~ Y,Y) > 0, then the inequality corre
sponding to the cut < Y, ~ Y >,
Â£ Â£
kÂ£K ie~Y
is redundant in the cut system if and only if either G(Y) or G(~ Y)
is not connected.
(2) If U(Y, rsj Y) = 0 (connectedness of the graph then implies that
U( Y,Y) > 0), then all sets I\ with more than one element yield
redundant inequalities. The inequalities
Y,bi
ie~Y
29
are redundant in the cut system if and only if either G(Y) or G( Y)
is not connected.
(3) If f/(~ Y,Y) 0 (connectedness of the graph then implies that
U(Y,~ Y) > 0), then all sets K yield redundant inequalities except
for K = {1,2,... ,p}. The inequality
E Â£ $
k=11e~v
is redundant in the cut system if and only if either G{Y) or G( Y)
is not connected.
Proof:
(1) We will first prove the if direction. Assume that one of G(Y)
and G(~ Y) is not connected.
Case 1: G(Y) is not connected.
Let Y = Yi U Y2 where Yf fi Y2 = 0 and there are no edges between
Y\ and Y2.
We examine the inequalities
Â£ Â£ ti
kÂ£K
The inequalities from Vf are
E E 6? = E E + E E < u(y,~ in VA.
keK ie~vri kei< ieY2 keK ie~Y
The inequalities from Y2 are
E E = E E *?+ E E
fceA' ie~y2 yte/\ tsvi re/c tg~v
Summing these inequalities gives
EE^2E E $
kÂ£K iÂ£Y kK t*^Y
v/c
30
Subtracting T,keK IZiev b,=0 gives
EEb"
keK ie~Y
Thus, those inequalities are redundant.
Case 2: G(~ Y) is not connected.
Let ~ Y = Yi U V2 where Xi fl Y2 = 0 and there are no edges
between Y\ and Y2. We examine the inequalities
E E tf
kSK iÂ£~Y
The inequalities from ~ Vi are
E Eb$^u(~YuYi) VAT.
kÂ£K iÂ£Yi
The inequalities from ~ Y2 are
E E6?<Â£/(~u,u) va'.
kÂ£K 16 Vi
Summing these two inequalities gives
E(E <>f+E 6?) = E E <>? < Cf(~ YY,)+V{~ Y2,Y2) = Â£7(K,~ V) V.
fceA' ieVi tevi tÂ£~v
Thus, the inequalities are redundant.
These proofs are sufficiently general to hold for U(Y, Y) > 0.
Thus, we have also proved the if direction for (2) as well.
We now prove the only if direction. We assume that an in
equality is redundant, and we will show that at least one of the
corresponding graphs is not connected. If
E E
kÂ£K' iÂ£~Yq
31
is redundant, then it is a nonnegative combination of linear in
equalities from sets other than Yq. To see this, assume that the
above inequality is a nonnegative combination of linear inequal
ities in the cut system, some of which may be generated by the
set Yq. Clearly the only way the inequality can be a nonnega
tive combination of inequalities generated only by the set Yq is
if U{Y, Y) = 0. This exception is treated in part (2) of the
theorem. So the dependency set must contain at least one in
equality generated by a set other than Yq. However, it may not
contain any edges not in < Yq,~ Yq > We assume that G(Yq)
and G( n) are both connected, and we will derive a contradic
tion. First we will show that an inequality from Ys, V^fl
Yn n/ Yg, cannot be in the dependency set. Since G(~ Yq)
is connected, there is an edge in < Yq/Yj > or there is
an edge in <~ Yq/Yj,Yj > If the former is true, we are done
with this case. If the former is false, then the latter is true. Call
the edge (a,/?). Sine a and /? must be counted an equal number
of times, there must be some set, containing a and not contain
ing /3, whose corresponding inequality is in the dependency set.
But then this cutset contains the edge (a,(3), which is not possi
ble. Thus, an inequality corresponding to Ys with Wfl ~ Yq ^ 0,
Ysn Y't Yq, cannot be in the dependency set. The same can
be shown for a set Yt with Yt Pi Yq / 0, Ys fl Yq ^ Yq. The only
remaining possibility is that an inequality corresponding to ~ Yq
is in the dependency set. This can only occur if U(~ Yq,Yq) = 0,
32
which is handled in part (3) of the theorem. Thus, we have shown
that the redundant inequality
E E
keK1 ie~Yq
must be a nonnegative combination of linear inequalities from sets
oV
other than Yq. That is, 3A G such that
E E = EE E bi = E E^ E &?
kÂ£K' iÂ£~Yq s^q kÂ£K' iÂ£~Ks kÂ£_K' sj:q tÂ£~E
Note that the above equation holds for all b. In particular, for any
choice of k, we can set b\ to be zero for all i and for all j ^ k.
Therefore,
E bi = E A< E 6i
iÂ£~Yq S^q iÂ£Ys
for each k. This gives us that
E ti
tÂ£~y,
is redundant in the cut system for each commodity k. Thus, each
inequality corresponding to Yq is redundant for each commodity
k. We can now apply the WallaceWets Theorem to conclude that
either G(Yq) or G(~ Yq) is not connected.
(2) Assume U(Y, ~ Y) 0. We have the inequalities
E 6 < U(Y, ~ Y) = 0 Vfc.
ie~Y
Summing over k Â£ K : \K\ > 1 gives
E E ti<0 = U(Y,~Y) VA':A'>1.
kÂ£K iE~Y
33
Thus, the inequalities
E E $ 1
kÂ£K iÂ£~K
are always redundant when U(Y, Y) = o.
(3) Assume Â£/(~ Y,Y) = 0. Let K' be any proper subset of the com
modities. We will show that the inequality
Â£ Â£ 6f
keK> te~Y
is redundant.
From the set ~ Y, we have the inequalities
Â£Â£!,
keK iev
In particular, if Kv is the set of all commodities, we have the
inequality
Â£ Â£6f
keKP/K' iÂ£Y
Since E.eK 6? =  this gives us
 Â£ Â£ h? < o.
keKP/K' iÂ£~Y
Adding this to the inequality
keKp te~v
results in the original inequality.
We note that when p = 1 (one commodity) this system reduces
to the system used by Wallace and Wets. The inequality for the set Y
becomes h < U(Y,~ Y).
We proceed now to the undirected case, which is not as straight
forward as the directed case.
34
1
5. Feasibility in Undirected Multicommodity Graphs
5.1 The Absolute Value System
! We will now work with undirected multicommodity graphs, mean
! ing that the edges are not oriented and flow may travel in either direction

 on an edge. In particular, flow from different commodities may travel in
i
I opposite directions on the same edge. In working towards an extension
I
I
 of the WallaceWets Theorem to the undirected multicommodity case, we
!
 need to have a system of inequalities which is a necessary condition for
feasible demands (and which will be sufficient for the cases discussed in
Chapter 2). The traditional system of cut inequalities,
! Â£(<3% : 1 ^ Pi Y separates Sk and tk) < U(Y, ~ Y) W C V,
I
i
 assumes that the origin and destination nodes for each commodity are
I
' known a priori. We need to develop a system in which the origin and
destination nodes do not need to be known a priori. As a first attempt,
one might try generalizing the single commodity cut system by summing
over all commodities, as in the directed case. If we use the system from
the directed case, we have:
1
i
i
i
j Â£(> = o
 iev
Â£ Â£ $
I kÂ£l\ iÂ£~Y
However, this system is not restrictive enough in the undirected
case. Consider the following graph.
b\ u b\
%*5
The above system would give rise to the following set of inequalities
b\ + b\ 0
b\ + b] = 0
Y={1}: I< = {1} : b\ < u
I< = {2} : b\ < u
A'= {1,2}: b\ T b\ < u
Y = { 2}: I< = {1} : b\ < u
I< = {2} : b\
AT = {1,2} : b\ + b\ < u
This system allows for b\ = 1,&2 = l,^i = 1, = 1) and u
1.
However, we can easily see that this set of demands, along with the given
capacity, is not feasible. In order to satisfy the demands, we would have to
send a total of 2 units of flow across the edge, when only 1 unit is allowed.
The problem is that at each node, the demand for one commodity cancels
with the supply for the other commodity.
This problem is alleviated by taking the absolute value of the
sum of the b,s for each commodity. That is, we use the system
= o v*
iEV
36
VYcV.
ElEtfl
k=l i&
Now the system for the above graph is:
b\ + b\ 0
b\ + Â£>2 = 0
v = {1} : fcl! + 1*11 <
r = {2} : 6 + 6? < u
We see that the set of 6fs that was feasible in the old system is not
feasible in this system. In fact, this gives us the correct system for every
multicommodity graph, as the next theorem shows.
Note that we do not need to sum over k 6 K because the in
equalities corresponding to sets K other than the full set of commodities
will be dominated by the inequality above. For example, for the graph in
the above example, we would get
Y = {l}:K = {l}:\b\\
which is dominated by the inequality obtained by summing over all com
modities.
Theorem 5.1 The set of inequalities
Â£Â£>
k\ iev
is equivalent to the set of inequalities
separates Sk and tk) < U(Y, ~ Y) VV C V.
37
Proof: Since qk = bkSk and bf = 0 for i ^ sk,tk for all fc, we will
treat separately the cases when Y does and does not separate sk and tk.
Case 1: Y does not separate sk and tk.
Then Sk and tk are either both in Y or both in ~ Y. If Sk and
tk are both in Y, then
IEfl = l^ + iJ = o.
iÂ£Y
If Sk and tk are both in ~ Y, then bf = 0 Vi G Y. Therefore, if sk and
tk are not separated, then ieY b! 0.
Case 2: Y does separate sk and tk.
Then either sk G Y or tk G Y, but not both, bf = 0 for all other
i G Y. Then
lE^I = i>l=qt
iEY
Thus, the absolute value inequality is equivalent to limiting Y
to sets that separate sk and tk, in which case the two inequalities are the
same.
This system of inequalities, which we will refer to as the cut
system, has many properties which are not common to a general system
of absolute value inequalities. First, we know that every inequality in
the cut system contains absolute values. Further, for a given inequality,
the number of terms within each absolute value is the same, and it is
equal to the cardinality of the set Y. So, for example, we cannot have
xi  + x2 + Â£31 < u in a cut system. Similarly, each inequality in the cut
system has the same number of absolute value terms, which is equal to
the number of commodities. That is, we cannot have both xi < u and
38
xi  + s2 < u in the same system. Additionally, a term that appears inside
of one absolute value will not appear anywhere else in that inequality.
That is, we cannot have \x\ + x2\ + \x2 + x3\ < u in a cut system. Finally,
we note that the coefficients on all terms within the absolute values, as well
as on the absolute value quantities themselves, are 01, and the righthand
side is always nonnegative. These observations lead us to some lemmas
about the cut system.
An absolute value inequality from the cut system is equivalent to
a system of 2P linear inequalities. We can express the yth linear inequality
as
k=1 ieY
where 8kj G { 1,1}. In the proof of the next lemma, we will simply write
U for U(Y, ~ Y). To illustrate the equivalent system of linear inequalities,
consider the following absolute value inequality:
l^i + x2\ + x3 + x4 < u.
The corresponding system of linear inequalities is:
+ x2 + Â£3 + x4
(xi + x2) + x3 + x4 < u
x\ + x2 (x3 + x4) < u
(xi + x2) )(2:3 + X4) ^ u.
We will sometimes refer to this system as a family of linear inequalities.
We next show that we cannot obtain an inequality in this system as a
nonnegative combination of only other inequalities in this system.
39
Lemma 5.2 The family of linear inequalities corresponding to
a given absolute value inequality from the cut system is internally nonre
dundant.
Proof: Consider the jth linear inequality corresponding to a given abso
lute value inequality:
E E < u.
k=1 tSY
Reverse the sense of the inequality and make it strict:
Y.h, Ei?>c.
k=1 iÂ£Y
The system with this new inequality in place of the old one is feasible if
and only if the old inequality is nonredundant. We will construct a feasible
solution to the reversed system:
Vi Y, bk
ypi 11 kJ
u
Tlpi
if Skj = 1
if Skj = 1
Then
v
E^Etf =
k=l ieY \Y\p 1
Further, changing any Skj from 1 to 1 or from 1 to 1 decreases
the sum by making it equal to U. Thus, this b satisfies all of the
linear inequalities in this family, so the jth inequality is not implied by
the others. I
This lemma does not hold for the linear system corresponding to
a general absolute value inequality. The following example will illustrate
this.
40
Example
Consider the inequality
zi + \x2\ + xi + x2\ < u
A partial enumeration of the corresponding linear inequalities gives:
X\ + x2 + x\ f x2 < u => 2x\ + 2x2 < u
xi + x2 + Xi + x2 < u => 2x2 < u
Xi x2fx1jx2
Xi + X2 Xi x2 < u => 0 < u
The last two inequalities are copies of each other. Thus, this system is not
internally nonredundant.
We can also make some observations about an inequality which
is known to be redundant.
Lemma 5.3 A redundant linear inequality cannot be formed as
a nonnegative combination of linear inequalities which are all from one
family, different from the family of the redundant linear inequality.
Proof: Let a!? be the node membership function for the set Yq: =
1 iff i Â£ Yq. Let ceq be the edge membership function for the cut defined
by Yq: ceq = 1 iff e Â£< Yq, ~ Yq > We want to show that
Â£ hi Â£ rf < U(Y~ Yq) = Â£ c"U'
k= 1 iÂ£V eeE
cannot be formed as
E ^ E hr E < U{YU ~ Yt) = E ceiCe, (Ar > 0, E Ar = 1, A, = 0).
r k=1 j'eV eeE r
41
Assume the two inequalities are equal. Then ctJ2rXr = cq. This gives
us that J2r = 1 and ct = cq. If the network is connected then either
Yt = Yq or Yt =~ Yq. Since this is not possible, the two inequalities cannot
be equal.
Lemma 5.4 If a linear inequality from the cut system is redun
dant, then it is redundant for each commodity.
Proof: If
E^E^f
k= 1 ieV
is redundant, then it is a nonnegative combination of linear inequalities
qp y qTI
from sets other than q. That is, 3A 6 9?+ such that
Â£ = E E k. Â£ 4. E = Â£ Â£ Â£ 4A. E iM
k=1 iÂ£V r s^q k=1 iÂ£V k=1 ** s^q iÂ£V
Note that the above equation holds for all b. In particular, for any choice
of k, we can set b\ to be zero for all i and for all j ^ k.
Therefore,
Skj Â£ Ar Â£ ai^i fr each
iÂ£V r s^q iÂ£V
Which gives us that
iev
is redundant in the cut system for commodity k. H
5.2 Redundancy Theorem
We have seen many characteristics of single commodity flows that
do not extend to the case of multicommodity flows. The question which
motivated this thesis was whether the WallaceWets Theorem holds in the
42
multicommodity case. In this section we prove that using the absolute
value system, the WallaceWets Theorem can be extended to undirected
multicommodity graphs.
In what follows, we assume the cut system to be
p
EIE*?  < U(Y, ~ Y) MY CV
k= 1 ieY
Ebr= 0 (fc = l,.,P).
iev
Theorem 5.5 [Redundancy Theorem for Undirected Graphs]
Let G be a connected, capacitated, undirected, multicommodity graph
with p commodities, where each commodity has one origin and one desti
nation.
(1) Only one of the pair of inequalities
ElEtfl
k=i ieY
El E tfl
k= 1 t'6~V
is ever necessary. That is, we need only consider the inequality from
Y or ~ Y, but not both.
(2) The inequality corresponding to the cut < Y, ~ Y >,
El E 4l < U(Y,~Y),
k1 e~y
is redundant in the cut system if and only if either G(Y) or G(~ Y)
is not connected (Y ^ 0, ~ Y ^ 0).
43
Proof:
(1) Since J2ievbi = 0 (A: = we have that J2i Â£Y bi 
I2,e~y bi Therefore,
k=1 iÂ£Y k=l iÂ£~Y k=l iÂ£~Y
So only one of each pair of inequalities is needed.
(2) We will first prove the if direction. If G(Y) and G(~ Y) are not
both connected, we may assume, without loss of generality, that
G(~ Y) is not connected. Let ~ Y = Yi U Y2 where Yi D Y2 = 0
and there are no edges between Yi and Yi. We will show that
the inequality from Y is dominated by the sum of the inequalities
from Yi and rs_/ Y2.
The inequality from Y is
EI E I = EIE <>?+ E tfl < v(y,~y) = u(y,u)+c/(r,n).
k=l iÂ£~Y k=1 iÂ£Yi ieY2
The inequality from ~ Y\ is
EiE'>fl
fc= 1 iÂ£Yi
The inequality from ~ Y2 is
ElEtfl
k=1 ieY2
Summing the inequalities from ~ Yi and ~ Y2? we get
E(l E 6,l +1E tfl) < c(K~ y.) + u{y3,~y,).
k= 1 ieVi ieY2
However, since there are no edges between Yi and Y2 we get that
U(YU~Y) + U(Y2,~Y2) = U(YUY) + U(Y2,Y). Thus
E l E tfl < Ed E 6?l +1E &l) < v(Y~ y).
k= 1 k=1 t'E^i 16^2
44
We next prove the only if direction. If the gth inequality
El E 6?I
k=1 i G~ Yq
is redundant, then some linear inequality (of the 2P corresponding
to it) is redundant. Assume it is the jth linear inequality. By
Lemma 5.4, if the jth inequality is redundant, then it is redun
dant for some single commodity. At this point, we can apply the
Wallace and Wets Theorem (Theorem 3.1) to this inequality, and
we conclude that either G(Yq) or G( Yq) is not connected.
We note that when p = 1 (one commodity), the system of ab
solute value inequalities reduces to the same system of linear inequalities
that is used in the WallaceWets Theorem. We get that the inequality
from set Y is
E
This is equivalent to the following two linear inequalities,
E bi
 E bi = Y,bi^u(Y~Y)>
ie~Y ieY
which are the inequalities that Wallace and Wets would generate from
the sets Y and ~ Y. Thus, if p = 1, our theorem is equivalent to the
WallaceWets Theorem.
45
Example
We illustrate the preceeding theorem using the following graph.
1
Assume there are p commodities. The inequalities from Y =
{1,2,3} and Y = {1,2,5}, as well as others, are nonredundant. Both
G(Y) and (7(~ y) are connected. The inequality from Y = {1,2,3} is
p
y^ i &4 + 651 < U2 + ^3 + uq.
k=1
Y = {2,4,5} is an example of G(Y) connected but Cr(~ Y) not
connected. The (redundant) inequality is
p
yy \b\ + 631 < ui + U3+U5+uq .
k=1
To construct the inequalities which dominate this one, let Y\ = {1} and
Y2 = {3}. The inequality from ~ Y\ is
p
y i^ii < u\ + u3.
k= 1
The inequality from ~ V} is
p
y I63I < U5 + ug.
k= 1
46
Summing these gives
p
+ 1^31) G ^1 + U3 + U5 + Uq
k=1
which dominates the inequality from Y.
Finally, Y {3,5} is an example of G(Y) and G(~ Y) both not
connected, so the inequality from Y is redundant.
5.3 Some Building Blocks
This section contains two types of results. The first several the
orems demonstrate how our knowledge of redundant inequalities for one
graph may be used to determine redundant inequalities for a related graph.
The last several theorems count the number of redundant or nonredun
dant inequalities in general and for some specific graphs. These theorems
give a measure of the usefulness of the Redundancy Theorem.
As a corollary to the Redundancy Theorem, we see that any
inequality that is redundant in a graph is redundant in all graphs formed
by removing only edges from the original graph.
Theorem 5.6 [Corollary to Redundancy Theorem] If
G' [V, E'], E' C E, then any inequalities that are redundant for G
are redundant for G'.
Proof: If either G(F) or G(~ F) is not connected in G, then it is also
not connected in Gh M
47
Example To illustrate, consider the following graphs G and G'.
12 12
G
G'
We see that G and G' have the same vertex set, and that the
edge set of G' is a subset of the edge set of G. The set Y = {1,3} gives
a redundant inequality in G because G(~ Y) is disconnected. The same
set also gives a redundant inequality in G'.
However, if we allow G' to be any subgraph of Gr, that is, if we
allow the vertex set of G' to be a proper subset of the vertex set of G1
then the corollary is not true. To illustrate, consider the following graphs
G and G1.
1 2 1
3
G G'
Now the set Y = {1,3} gives a redundant inequality for G, but
not for G'.
48
Corollary 5.7 If G = [V,E], G' = [V,E'],G" = [V,E'%... is
a sequence of graphs such that E D E' D E" D ..., then the number
of nonredundant inequalities for G is at least as large as the number of
nonredundant inequalities for G', which is at least as large as the number
of nonredundant inequalities for G".
Proof: By Theorem 5.6, every inequality which is redundant for G is
also redundant for G'. Every inequality which is redundant for G' is also
redundant for G", and so on.
In order to use the Redundancy Theorem, we must find all ver
tex partitions Y of V such that G(Y) and G(~ Y) are both connected.
However, if we have already done this for two graphs and we then form a
new graph by joining the first two in a specific way, then we may not have
to recompute which sets give necessary inequalities. We may be able to
find all the necessary inequalities through appropriate combinations of the
sets we already have. One specific way of combining two graphs is with a
bridge, that is, an edge joining one vertex of the first graph to one vertex
of the second graph. Then we can find all the necessary inequalities for
the new graph by combining the entire vertex set of each original graph
with one of the vertex partitions from the other original graph which is
already known to give a necessary inequality for that graph.
Theorem 5.8 Let G\ = [Vi,^], G2 = [V2: E2] be connected
graphs, Vif]V2 = 0. Let G = G\ U G2 U(^i ,v2) = [V, E], where v\ Â£
Vj and v2 Â£ V2 (See Figure 5.1). Let = {N{, IVj2,..., Ar"1} be the
collection of vertex partitions which give nonredundant inequalities for
the graph G\. Let hl2 = {A^1, iVf,..., IV22} be the collection of vertex
49
Figure 5.1: Graph with a bridge
partitions which give nonredundant inequalities for the graph G2. The
vertex partitions which give nonredundant inequalities for the graph G
are
Vj (J{A^ G Mi : i>2 G N'2} and
V2\J{NieMx : ui N[} and Vx.
Proof: By construction, the induced subgraphs on each of the sets listed
above and each of their complements are connected. We need to show that
there are no other vertex partitions of V (TJ ~ Y = V, Y fj ~ Y = 0)
such that G(Y) and G(~ Y) are both connected. We have already used
all partitions which completely contain either \\ or Vi. The only other
possibility is that Y contains a proper subset of vertices from both V\ and
V2. That is, Y = Y\ U T25 where Yx C Vi, Yx / 0, and Y2 C V2, Y2 0. If
vx G Y and v2 Y, then G(Y) and G(~ Y) must both be disconnected
since neither contains the edge (vx,v2), the only edge joining vertices of
Vi and V2. The same is true if vx Â£ Y and v2 G Y. If vx,v2 G Y then it is
possible that G(Y) is connected, but G(~ Y) is necessarily disconnected.
If vx,v2 G~ Y, then it is possible that G(~ Y) is connected, but G(Y)
is necessarily disconnected. Thus, there are no other partitions of G with
G(Y) and G(~ Y) both connected.
50
A similar result holds if G has an articulation vertex. That is,
G is the union of two graphs G\ and G2 that share a common vertex v,
but no common edges. The one difference is that in this case Vi gives a
nonredundant inequality only if G2 \ v is connected.
Theorem 5.9 Let G\ = [Vi,Â£i], G2 = [V2,E2} be connected
graphs with E1f)E2 = 0, Vif\V2 = {v}. Let G = Gi\}G2. Let Afi =
{Ar11, A^,2,..., A^1} be the collection of vertex partitions which give nonre
dundant inequalities for the graph G\. Let M2 {A^1, A,..., N22} be
the collection of vertex partitions which give nonredundant inequalities for
the graph G2. The vertex partitions which give nonredundant inequalities
for the graph G are
Vi \J{Nl2 e M2 : U e Nfi and
mj {NieAfi.veNi}.
Proof: By construction, the induced subgraphs on each of the sets listed
above and each of their complements are connected. We need to show that
there are no other vertex partitions of V (T (J ~ Y = V, Y f) ~ Y = 0)
such that G(Y) and G(~ Y) are both connected. We have already used
all partitions which completely contain either Vi or V2. The only other
possibility is that Y contains a proper subset of vertices from both Vi and
V2. That is, Y = Yi{JY2, where Vi C Vi, Vi / 0, and Y2 C V^V^ 7^ 0.
If v Y, then G(~ Y) is necessarily disconnected. If v Y, then G(Y)
is necessarily disconnected. Thus, there are no other partitions of G with
G(Y) and G(~ Y) both connected. H
We now know that when checking the necessary conditions for
51
feasibility of a multicommodity graph, we need only check inequalities
corresponding to sets Y which have both G(Y) and G(~ Y) connected. Do
we really see much reduction when we discard inequalities corresponding
to sets Y which have either G(Y) or G(~ K) (or both) disconnected? The
following theorem gives a lower bound on the amount of reduction.
Theorem 5.10 Let G be a graph on n vertices, and let the
degree of the minimum degree vertex be S(G). Then using the Redundancy
Theorem results in a reduction of at least
n15(G)
E
n 1 8(G) '
9nl5(G) j
absolute value inequalities that must be checked for feasibility.
Proof: We want to count the number of disconnected induced subgraphs
of G. However, if G' [W, E'\ is a disconnected induced subgraph and
G" = [V", E"} is also an induced subgraph, with V" = V \ V', then we
only want to count one of that pair. A lower bound on this number can
be computed by forming all sets consisting of the minimum degree vertex,
v, and at least one vertex not adjacent to v. We count that by taking
combinations of one or more of the n 1 5{G) vertices that are neither
v nor adjacent to r. I
Corollary 5.11 If G is a complete graph, then no reduction is
provided by the Redundancy Theorem.
We note that the above bound is tight for the class of graphs
that have an induced subgraph on n 1 nodes which is complete.
Sometimes it makes more sense to look at how many inequalities
are left to be checked after applying the Redundancy Theorem, rather
52
than how much reduction was realized. Note that without this theorem,
we would always have to check an exponential number of inequalities. For
some special cases, we can show that after applying the theorem, we only
need to check a linear number of absolute value inequalities. That is,
there are a linear number of partitions of the vertices so that the induced
subgraphs on both partitions are connected.
Theorem 5.12 If G is a tree on n vertices, then n 1 absolute
value inequalities are needed.
Proof: Removing any edge from a tree disconnects the graph. Removing
any more than one edge separates the graph into more than two com
ponents. Thus, the only partitions of the vertices so that the induced
subgraphs on both partitions are connected are those that consist of all
the vertices on one side of a particular edge. Since a tree on n vertices
has n 1 edges, there are n 1 partitions which meet the stated criteria.
Hence, there are n 1 necessary inequalities. I
We also know of a case when a quadratic number of inequalities
need to be checked.
Theorem 5.13 If G is a cycle on n vertices, then n(n 1)
absolute value inequalities are needed.
Proof: There are connected subgraphs on 1,2,..., n 1 nodes, and there
are n connected subgraphs of each size. The subgraph on the complement
of each of these node sets is also connected. However, since we want to
count each graph and its complement only once, we must divide the
total number of connected subgraphs by two. Thus, there are n(n 1)
53
partitions of V such that both G(Y) and (?(~ Y) are connected.
If a graph contains a bridge or an articulation vertex, as in The
orem 5.8 and Theorem 5.9 then we can find the number of necessary
inequalities just by looking at the subgraphs on either side of the bridge
or articulation vertex.
Theorem 5.14 Let G be a graph with a bridge, such as de
scribed in Theorem 5.8. The number of nonredundant inequalities is
ni + n2 + 1, where ny and n2 are the number of nonredundant inequalities
for graphs Gy and G2, respectively.
Proof: In Theorem 5.8, we construct A/i + \M2\ + 1 vertex partitions of
G which give nonredundant inequalities. If we let = ny and \M2\ = n2
then this number is ny + n2 + 1.
Theorem 5.15 Let G be a graph with an articulation vertex,
such as described in Theorem 5.9. The number of nonredundant inequali
ties is ny+n2, where ny and n2 are the number of nonredundant inequalities
for graphs Gy and G2, respectively.
Proof: In Theorem 5.9, we construct A/j + \Af2\ vertex partitions of G
which give nonredundant inequalities. If we let A/i = ny and \M2\ = n2
then this number is ny + n2. I
Using combinations of the above theorems, we can compute the
number of necessary inequalities for several graphs with special structures.
For example, if G has a bridge, and Gy is a cycle and G2 is a tree, then
we know that ny = \n'(n' 1) and n2 = n" 1, where n' and n" are the
54
number of vertices of Gi and G2, respectively. Therefore, the number of
nonredundant inequalities for G is l) + n"1 + 1 = n'(ra' l) + n".
55
6. Avenues for Further Research
This thesis opens several avenues for further research. We be
lieve that there are some further special properties of the absolute value
inequalities used in Chapter 5. We have not yet been able to find coun
terexamples or proofs of the following conjectures.
Conjecture 6.1 The dependency set for a redundant linear in
equality contains at most one linear inequality from each family corre
sponding to a given absolute value inequality.
The proof of this conjecture would lead us to a proof for the if
direction of the following conjecture. The only if direction of the next
conjecture is readily apparent.
Conjecture 6.2 The inequality J2l=i  Zaev frfl < U(Y,~ Y) is
nonredundant in the cut system if and only if the 2P linear inequalities
corresponding to it are all nonredundant in the cut system.
Another direction would be to consider the classification of nodes
as supply, demand, or transshipment nodes. The work in this thesis as
sumes that no node classifications are known a priori. Greenberg ([14])
has demonstrated that the WallaceWets Theorem does not extend imme
diately to the situation when nodes are preclassified as supply, demand,
and transshipment nodes. It is not known how the theorem must be
changed for this case. Classification of nodes can also be looked at in the
multicommodity setting. Additionally, one could consider the effects of a
partial classification of the nodes, which in the multicommodity setting
may mean that different nodes are classified for different commodities.
Some further work is also possible in the area of counting the
number of necessary inequalities for special graph structures. There are
many special cases that have not been covered in this thesis. One partic
ular possibility is to find a bound on the number of necessary inequalities
for an arbitrary /connected graph.
57
Glossary
articulation vertex A vertex whose removal increases the number of
components of the graph
bridge An edge whose removal increases the number of components of
the graph
complete graph A graph with an edge between every pair of vertices
connected graph A graph in which there is a path between every pair
of vertices.
dependency set A system of inequalities which implies a redundant in
equality.
feasible network A network in which the required flow can be shipped
without violating the capacities of any edges.
multicommodity graph A graph in which flow must be sent from spe
cific origins to specific destinations.
redundant inequality An inequality which is implied by other inequal
ities in the system.
58
BIBLIOGRAPHY
[1] A. A. Assad, 1978. Multicommodity Network Flows A Survey, Net
works 8, 3791.
[2] D. Avis and M. Deza, 1991. The Cut Cone, L1 Embeddability, Com
plexity, and Multicommodity Flows, Networks, 21, 595617.
[3] M. Bellmore, H. J. Greenberg, and J. J. Jarvis, 1970. Multi
Commodity Disconnecting Sets, Management Science 16:6, B427
B433.
[4] C. Berge, 1985. Graphs, NorthHolland, Amsterdam.
[5] R. C. Burk and J. S. Provan, 1995. Multiterminal and Multicommod
ity Cuts in TerminalPlanar Graphs, UNC/OR TR9411.
[6] Y. L. Chen and Y. H. Chin, 1992. Multicommodity Network Flows
with Safety Considerations, Operations Research 40:S1, S48S55.
[7] P. L. Erdos and L. A. Szekely, 1992. Evolutionary Trees: An Integer
Multicommodity MaxFlow MinCut Theorem, Advances in Applied
Mathematics 13, 375389.
[8] J. M. Farvolden, W. B. Powell, and I. J. Lustig, 1993. A Primal Parti
tioning Solution for the ArcChain Formulation of a Multicommodity
Network Flow Problem, Operations Research 41'4i 669693.
[9] L. R. Ford, Jr. and D. R. Fulkerson, 1962. Flows in Networks, Prince
ton University Press, Princeton, NJ.
[10] D. R. Fulkerson, 1968. Networks, Frames, Blocking Systems, in Math
ematics of the Decision Sciences: Part 1 (B. B. Dantzig and A. F.
Veinott, Jr., eds.), Lectures in Applied Mathematics 11, American
Mathematical Society, Providence, RI, 303334.
[11] D. Gale, 1957. A Theorem on Flows in Networks, Pacific Journal of
Mathematics 7, 10731082.
[12] S. Ghannadan and S. W. Wallace, 1994. Feasibility in Capacitated
Networks: The effect of individual arcs and nodes, Preprint.
[13] F. Glover, D. Klingman, and N. V. Phillips, 1992. Network Models
in Optimization and Their Applications in Practice, John Wiley &
Sons, Inc., New York.
[14] H. J. Greenberg, 1993. Consistency, Redundancy, and Implied Equal
ities in Linear Systems, UCD/CCM Report No. 14.
[15] A. J. Hoffman, 1960. Some Recent Applications of the Theory of
Linear Inequalities to Extremal Combinatorial Analysis, Proceedings
of Symposia in Applied Mathematics 10.
[16] T. C. Hu, 1963. Multicommodity Network Flows, Operations Re
search If 344360.
[17] T. C. Hu, 1969. Integer Programming and Network Flows, Addison
Wesley Publishing Co., Reading, MA.
[18] M. Iri, 1971. On an Extension of the MaximumFlow MinimumCut
Theorem to Multicommodity Flows, Journal of the Operations Re
search Society of Japan, 13:3, 129135.
[19] A. Karzanov, 1985. Metrics and Undirected Cuts, Mathematical Pro
gramming, 32, 183198.
[20] A. V. Karzanov, 1987. HalfIntegral FiveTerminus Flows, Discrete
Applied Mathematics 18, 263278.
[21] J. L. Kennington, 1978. A Survey of Linear Cost Multicommodity
Network Flows, Operations Research, 26, 209236.
[22] H. Nagamochi, 1988. Studies on Multicommodity Flows in Directed
Networks, Ph.D. Thesis, Kyoto University, Japan.
[23] H. Nagamochi and T. Ibaraki, 1989. MaxFlow MinCut Theorem
for the Multicommodity Flows in Certain Planar Directed Networks,
Electronics and Communications in Japan, Part 3, 72:3, 5871.
[24] H. Nagamochi and T. Ibaraki, 1989. On MaxFlow MinCut and Inte
gral Flow Properties for Multicommodity Flows in Directed Networks,
Information Processing Letters, 31, 279285.
[25] H. Nagamochi, M. Fukushima, and T. Ibaraki, 1990. Relaxation
Methods for the Strictly Convex Multicommodity Flow Problem with
Capacity Constraints on Individual Commodities, Networks 20, 409
426.
60
[26] T. Nishizeki and N. Chiba, 1988. Planar Graphs: Theory and Algo
rithms, Annals of Discrete Mathematics, 32, NorthHolland, Amster
dam.
[27] H. Okamura, 1983. Multicommodity Flows in Graphs, Discrete Ap
plied Mathematics, 5562.
[28] H. Okamura and P. D. Seymour, 1981. Multicommodity Flows in
Planar Graphs, Journal of Combinatorial Theory, Series B, 31, 75
81.
[29] D. T. Phillips and A. GarciaDiaz, 1981. Fundamentals of Network
Analysis, PrenticeHall, Inc., EnglewoodCliffs, NJ.
[30] S. Rajagopalan, 1994. Two Commodity Flows, Operations Research
Letters 15, 151156.
[31] B. Rothschild and A. Whinston, 1966. On Two Commodity Network
Flows, Operations Research 14:3, 377387.
[32] B. Rothschild and A. Whinston, 1966. Feasibility of Two Commodity
Network Flows, Operations Research 14:6, 11211129.
[33] M. Sakarovitch, 1973. Two Commodity Network Flows and Linear
Programming, Mathematical Programming 4, 120.
[34] R. Schneur, 1991. Scaling Algorithms for Multicommodity Flow Prob
lems and Network Flow Problems with Side Constraints, Ph.D. The
sis, Massachusetts Institute of Technology.
[35] A. Sebo, 1987. Dual Integrality and Multicommodity Flows, in Infi
nite and Finite Sets, Proceeding of a Conference held in Eger, North
Holland, July 1987 (A. Hajnal and V. T. Sos, eds.), 453469.
[36] A. Sebo, 1993. Integer Plane Multiflows with a Fixed Number of
Demands, Journal of Combinatorial Theory, B, 59:2, 163171.
[37] P. D. Seymour, 1980. FourTerminus Flows, Networks 10, 7986.
[38] P. D. Seymour, 1981. Matroids and Multicommodity Flows, European
Journal of Combinatorics 2, 257290.
[39] P. D. Seymour, 1981. On Odd Cuts and Plane Multicommodity
Flows, Proceedings of the London Mathematical Society (3) 4%> 178
192.
61
[40] V. I. Shevchik, 1993. Multicommodity Flow Problem, Journal of So
viet Mathematics, 6/1/93, 14621464.
[41] H. Soroush and P. B. Mirchandi, 1990. The Stochastic Multicommod
ity Flow Problem, Networks 20, 121155.
[42] J. A.Tomlin, 1966. MinimumCost Multicommodity Network Flows,
Operations Research 14:1, 4551.
[43] S. W. Wallace and R. J.B. Wets, 1989. Preprocessing in Stochastic
Programming: The Case of Uncapacitated Networks, ORSA Journal
on Computing 1:4, 252270.
[44] S. W. Wallace and R. J.B. Wets, 1993. Preprocessing in Stochastic
Programming: The Case of Capacitated Networks, ORSA Journal on
Computing (to appear).
[45] S. W. Wallace and R. J.B. Wets, 1993. The Facets of the Polyhe
dral Set Determined by the GaleHoffman Inequalities, Mathematical
Programming 62, 215222.
[46] R. D. Wollmer, 1972. Multicommodity Networks with Resource Con
straints : The Generalized Multicommodity Flow Problem, Networks
1, 245263.
62

PAGE 1
FEASIBLE FLOWS IN MULTICOMMODITY GRAPHS by Holly Sue Zullo B. S., Rensselaer Polytechnic Institute, 1991 M. S., University of Colorado at Denver, 1993 A thesis submitted to the Faculty of the Graduate School of the University of Colorado at Denver in partial fulfillment of the requirements for the degree of Doctor of Philosophy Applied Mathematics 1995 '. j ,_; i l .... \ ;..., . _..i
PAGE 2
This thesis for the Doctor of Philosophy degree by Holly Sue Zullo has been approved by David Fisher I ;, J /q Date G' S
PAGE 3
Zullo, Holly Sue (Ph. D., Applied Mathematics) Feasible Flows in Multicommodity Graphs Thesis directed by Professor Harvey Greenberg ABSTRACT This thesis establishes the minimal representation of the necessary conditions for feasible supplies and demands for a given multicommodity network. The fundamental theorem is an extension of the WallaceWets connectivity result for both directed and undirected graphs. A systern of absolute value inequalities is developed for the undirected case, and special properties of this system are explored. Additional results include counting the number of nonredundant inequalities for specific classes of graphs. This abstract accurately represents the content of the candidate's thesis. I recommend its publication. Signed Harvey Greenberg lll
PAGE 4
CONTENTS Chapter 1. Introduction 2. Technical Background 2.1 Terms and Concepts 2.2 The Literature ... 3. The WallaceWets Theorem 4. Feasibility in Directed Multicommodity Graphs 4.1 Preliminaries 4.2 The System 4.3 Redundancy Theorem 5. Feasibility in Undirected Multicommodity Graphs 5.1 The Absolute Value System 5.2 Redundancy Theorem 5.3 Some Building Blocks 6. A venues for Further Research Glossary ... Bibliography iv 1 3 3 6 13 22 22 25 29 35 35 42 47 56 58 59
PAGE 5
1. Introduction The set of feasible supplies and demands for a network flow prob lem can be described by a system of linear inequalities. Wallace and Wets have characterized the redundant inequalities in this system. The main theorem of this thesis is an extension of the WallaceWets Theorem to the case of undirected multicommodity graphs. In order to obtain the extension, a special system of inequalities is developed and several characteristics of this system are discussed. Following the extension, we prove several theorems on its usefulness. In Chapter 2 we provide technical background on network flows. We discuss some differences between single and multicommodity network flows, as well as the pertinent literature on multicommodity flows. We also discuss the background literature for the WallaceWets Theorem. In Chapter 3 we present the WallaceWets Theorem for single commodity networks along with a detailed proof of the theorem. Chapters 4 and .s contain the main results of the thesis. In Chap ter 4 we show that the vVallaceWets Theorem has a natural extension to directed multicommodity graphs. In Chapter .j we consider the case of undirected multicommodity graphs, which is not as straightforward. A system of inequalities which gives a necessary condition for feasible sup plies and demands for undirected multicommodity graphs is developed, and we explore properties of this system. Next we present our extension of the WallaceWets Theorem. We also present several theorems related
PAGE 6
to using the extension and the benefit realized. In Chapter 6 we suggest avenues for further research. This in cludes further work related to the system of inequalities developed in Chapter 5, as well as evaluating the effects of preclassification of nodes as supply, demand, and transshipment nodes. 2
PAGE 7
2. Technical Background 2.1 Terms and Concepts Let G = [V, E] be a finite graph with node set V and edge set E. For the problems we will consider in this thesis, there is no loss in generality to assume G does not contain any parallel edges. We therefore denote an edge by its endpoints: (i,j). This is an unordered pair in the context of undirected graphs, but an ordered pair in the context of directed graphs. We also assume, without loss in generality, that G is connected. For any Y V, let "' Y denote the complement of Y: "' Y = {i E V: i tf_ Y}. Then the associated cut is the edge set: < Y,rv Y >= {(i,j) E E: i E Y and j Erv Y}. Note that for undirected graphs, < Y,"' Y >=, but that this is not true for directed graphs. For each ( i, j) E E there is a capacity U;j which limits total flow across the edge. This extends naturally to subsets of E: U(Y,"' Y) = Uij For each Y V, we let G(Y) denote the induced subgraph on the node set Y. For each i E V, we let the demand at node i be given by b;. That is, if b; > 0 then node i has a demand, if b; < 0 then node i has a supply, and if b; = 0 then node i has neither demand nor supply. In the context of multicommodity graphs, sk and will denote the origin and destination, respectively, of commodity k, k = 1, 2, ... p. We will let represent the demand for commodity k. If the origin and
PAGE 8
destination of each commodity are not known, then bf represents the demand for commodity k at node i. The work in this thesis deals mainly with multicommodity graphs. It is well known that many of the "nice" properties associated with network flow problems do not extend to the multicommodity case. A complicat ing matter in multicommodity flows is that flows in opposite directions on an edge do not cancel if they are different commodities. This leads to a variety of problems. In a single commodity network flow problem, the maximum flow is equal to the minimum cut, and given integer capacities, the maximum flow is guaranteed to be integer. Neither of these proper ties extend to the general multicommodity case. Additionally, in single commodity network flow problems, the condition that the capacity of any cut is greater than or equal to the demand across the cut, is a necessary as well as sufficient condition for feasibility of the network. That is, if q is the required amount of flow to be sent through the network, the network is feasible if and only if q ::; U(Y,"' Y) \iY V. The analogous multicommodity condition 'L)qk: Y separates sk and tk)::; U(Y,"' Y) \iY V is necessary for undirected graphs, but it is not sufficient for feasibility in general. Much work has been done to determine specific classes of graphs for which this condition is sufficient, and we will examine several of the results in the next section. We now present some examples of the above statements. 4
PAGE 9
Example s2 = t3 a b S3 = t4 sr tr c d e f s4 = t2 Assume a capacity of 1 on each edge. A maximum flow is given by the following, where Xi is the flow vector for edge i. Xa = Xb = { 0} Xc = Xd = l:e = { 0, The flow is fractional. even though the capacities are integer. Also, the value of the maximum flow, which is the sum of the flows for each commodity, is 1 + + + = 3. The notion of a cut in single commodity graphs translates to a disconnecting set in multicommodity graphs, that is, a set of edges whose removal will disconnect the origin and destination of each commodity. For more on disconnecting sets, see [3]. A
PAGE 10
minimum disconnecting set for this graph consists of the edges {a, c, d, f}. The capacity of this set is 4, which is not equal to the maximum flow. Example Suppose the capacity of each edge is 1, and the demand for each commodity is 1. That is, we wish to send one unit of commodity 1 from s1 to t1 and so on. It can be verified that the cut condition, L(qk : Y separates Sk and tk ) :S: U(Y,"' Y), holds for every set Y. For example, if Y = {si}, then < Y,"' Y >= {a, b, c }, so U(Y,"' Y) = 3. The only commodity separated by Y is commodity 1, so the lefthandside of the cut condition is 1. Thus the inequality holds, as could be shown for every Y. However, it is not possible to satisfy all of the demands simultaneously, so the problem is not feasible. 2.2 The Literature As discussed in the previous section, a central issue in the study of multicommodity network flow problems is that the cut condition, L(qk : Y separates Sk and tk ) :S: U(Y,"' Y), 6
PAGE 11
is not always a sufficient condition for feasibility. Here we will present several of the results which characterize graphs for which this condition is sufficient for feasibility. We refer the reader to the appropriate papers for the proofs. As the results are very different for the undirected and directed cases, we will discuss them separately, beginning with the undirected case. Some of the pioneering work on this subject was done by T.C. Hu ([16],[17]). Hu proved that the cut condition is sufficient for feasibility if there are only two commodities. Additionally, he proved that in the twocommodity case, the maximum sum of the flows is equal to the minimum capacity of all cuts separating the origins and destinations of both commodities (the minimum disconnecting set). He provided an algorithm for constructing the flows. Finally, Hu showed that if the demands and the capacities are all even integers, then a twocommodity flow will have the property that the flows for each commodity on each edge are integer. This is commonly referred to as a halfinteger property, and it arises in other cases as well. H u's result is the only one that relies on a specific number of commodities, and it does not generalize to three or more commodities. All other results rely on the graph having special characteristics. A few definitions are in order before we discuss the next result. A planar graph is a graph that can be drawn in the plane so that no edges cross. Given a fixed drawing of a planar graph. we can identify various regions, which are simply the areas enclosed by the edges of the graph. The infinite region is the entire region outside the graph, and the boundary of the infinte region consists of the nodes and edges that separate the infinite 7
PAGE 12
1 2 4 3 Figure 2.1: A Planar Graph and Its Regions region from the "interior" of the graph. For example, in Figure 2.1, A is the region enclosed by the edges (1,2), (2,3), and (1,3); B is the region enclosed by the edges (1,3), (3,4), and (1,4); Cis the infinite region. The boundary of the infinite region is 1, (1,2), 2, (2,3), 3, (3,4), 4, (4,1). Note that we could also draw the graph with edge (1 ,3) on the other side of node 2. This would still be a planar representation, but different regions would be defined. The boundary of the infinite region for that drawing would be 1, (1,3), 3, (3,4), 4, (4,1). \Ve are now ready for the theorem of Okamura and Seymour ([28]). Theorem 2.1 (Okamura and Seymour, 1981) If G is planar and can be drawn in the plane so that s1 Sz, ... sP, t1 t2 . tp are all on the boundary of the infinite region, then is a sufficient condition for feasibility. Further, if the demands and capacities are all integers, then there exists a set of feasible flows with the flow for each commodity on each edge being integer. 8
PAGE 13
That is, if a graph can be drawn in the plane so that all the sources and sinks are on the boundary of the infinite region, then the cut condition is sufficient for feasibility. There have been some extensions of this theorem which relax slightly the condition of all the sources and sinks being on the boundary of the infinite region. Okamura ([27]) proved that the cut condition is sufficient if G is a planar graph and can be drawn with one set of sources and sinks on the boundary of any region, and the remainder of the sources and sinks on the boundary of the infinite region, with the source and sink for any one commodity on the same boundary. In the same paper, it is shown that the cut condition is also sufficient if G is planar and can be drawn with the sources and sinks for some commodities located on the boundary of the infinite region, and all other commodities share the same sink, also located on the boundary of the infinite region, but those sources may be located anywhere. Seymour ([39]) proved that the cut condition is sufficient if G is a planar graph and if the source and sink for each commodity may be joined by an edge without violating planarity. For a discussion of all of the above results plus algorithms for finding planar multicommodity flows, the reader is referred to [26]. The final class of undirected graphs that we will present here actually relies on the configuration of the sources and sinks of the com modities. We call this configuration the commodity graph. Given a con nected undirected network G = [V, ] with sources s1 s2 .. sp and sinks t1 t2 ... tP, let the commodity graph. H = [T, U], (T C V) be the undi rected graph whose edges correspond the the sourcesink pairs of G. That is, e E U e = (sk, tk) Note that U is not necessarily a subset of E.
PAGE 14
Example Given the following graph we construct the commodity graph by drawing each node and then con necting s1 to lt, s 2 to t2 and so on. The resulting graph is Karzanov ([19]) presents a result of Papernov regarding the commodity graph. Theorem 2.2 (Papernov, 1976) (1) If H is /\"4 (the com plete graph on four nodes), c5 (the cycle on five nodes), or a union of two stars, and if the cut condition is satisfied, then the problem is feasible. (2) If H is a graph which does not belong to the collection above, then there exists a graph G, capacities U, and demands q, such that the cut condition is satisfied and yet the problem is not feasible. 10
PAGE 15
In other words, the cut condition can be known to be sufficient based only on the commodity graph if and only if the commodity graph is a complete graph on four nodes, a cycle on five nodes, or a union of two stars. If the commodity graph is other than the graphs mentioned, then it is possible to construct a graph which has that commodity graph and for which the cut condition is not sufficient for feasibility. We are now ready to discuss some results on feasibility in directed graphs. As mentioned earlier, the directed case is very different from the undirected case, and it has received much less attention in the literature. Note that in the case of directed graphs, the cut condition changes slightly to become It is known that Hu's result for twocommodity graphs does not extend to the multicommodity case ([21]). However, the cut condition is sufficient for feasibility if the network is planar with all the sources on the left side and all the sinks on the right side (a transportation network) and if the sources and sinks appear in the same order (see [29]). The main work is by Nagamochi and Ibaraki, and we will give a brief overview of their results. In several papers and a Ph.D. thesis ([22], [23], [24]), Nagamochi and lbaraki studied directed multicommodity networks. They developed three classes of networks, capacity balanced (CB), capacity semibalanced (CS), and capacity semibalanced unilateral (CC). In a CB network, the capacity is "balanced" at each node. That is. for every node, the capacity on outgoing arcs plus the demand at the node is equal to the capacity on incoming arcs plus the supply at th<:> node. It is shown that the maxflow ll
PAGE 16
mincut theorem holds for multicommodity networks in CB, and also that the flows will be integer if the capacities and demands are integer. The class CS is shown to be a relaxation of class CB, and the same properties shown for CB networks also hold for CS networks. Finally, it is shown that the properties do not extend to CU networks. For a more general survey of multicommodity network flows, see either [I] or [21]. The foundations needed for the WallaceWets Theorem come from the work done by Gale and Hoffman for singlecommodity network flow problems. In [11], Gale gives a system of linear inequalities which are necessary and sufficient for feasibility of a set of supplies and demands in a network. Hoffman ([15]) extends this result to feasible circulations. The inequalities are those generated by considering all bipartitions of the vertices of the network. It is assumed that any node may be a supply node, demand node, or transshipment node. The resulting system of inequalities IS L b; :::; U(Y,"' Y) for allY C \1. This is the system which Wallace and Wets work with, and the inequalities will be referred to as the GaleHoffman inequalities. 12
PAGE 17
3. The WallaceWets Theorem In [43], [44], [45], Wallace and Wets examine the system of inequalities which describe the feasible supplies and demands for a network. The inequalities are the ones given by Gale and Hoffman, and Wallace and Wets determine the mimimum number of inequalities needed. The WallaceWets Theorem gives a characterization of the redundant inequalities based on a connectedness criterion. The GaleHoffman inequalities can be generated from all possible partitions of the vertices into two sets. Wallace and Wets prove that the resulting inequality is redundant if and only if the induced subgraph on at least one of the partitions is not connected. Their theorem is the following. Theorem 3.1 [WallaceWets Theorem] For all nonempty Y C V, the associated inequality, L b; U(Y, '"V Y) is redundant in the cut system if and only if either G(Y) or G('"" Y) is not connected. It is important to note that this theorem applies to the case where all supplies must be used and all demands must be met exactly. Thus, the cut system also includes the equation LiEV b; = 0, or supply equals demand. For more on this and other aspects of the WallaceWets Theorem, see [14].
PAGE 18
We present a proof of the WallaceWets Theorem for completeness and to clarify several of their steps. The sufficiency part of the proof is done by construction. We assume that either G(Y) or G("' Y) is not connected, and we show how to construct the dependency set for the inequality corresponding to Y. For the necessity part of the proof, we first prove a lemma showing that we may restrict our consideration of the righthandsides to an arc membership function. We then show that the only sets which may be used in constructing a redundant inequality are those whose cutset arcs are a subset of the cutset arcs of the original set. If both G(Y) and G("' Y) are connected, then there are no sets which have that characteristic. Thus, the original inequality is not redundant. Lemma 3.2 Let Yt define a partition of the vertices. If the inequality corresponding to Y{ is redundant, then the arcs in the union of the cutsets for partitions corresponding to the inequalities in the dependency set must be exactly the arcs in < }/,"' Y{ > Proof: Since the inequality corresponding to }i is redundant, there exist lVI ).J, ). 2 0, J 1, 2, ... 2 such that L b; = L L Ajbi). L b; L Aj['(Y:j,"'"' Yj) U(Yt,"' Y/). i Erv }[ J:l:l i Erv }j iEV jf.l Let J be the set of j's such that Aj > 0. First, assume there exists a E < }/, "' }/ > such that a tf. < Yj, "' Yj > Vj E J. Let a = (a,/3) (a E }/,/3 E'"'' }/). We will derive a contradiction. For any j E J if a E }j then j] E Yj (or else a E< lj, Yj >. Thus, J3 is in at least as many sets Yj as a, so (J is in at most as many sets "' 'tj as a. But since ;3 E'"'' Yt and a E }/, we must have ;3
PAGE 19
in exactly one more set "' }j than a in order for the lefthandside of the inequality to work out. So we have a contradiction. Thus, there does not exist a E< }J,"' }/ > such that a tf.< }j,"' }j > Vj E J. This tells us that the arcs of the cutset from }/ are a subset of the union of all arcs in the cutsets from }j for j E J. What we have left to show is that there is no arc in any set < }j,"' }j >,j E J such that the arc is not in < }/,"' }/ >. Let a E< Y/,"' }/ >,a = (a, {J) where a E }/, {J Erv }[. If the inequality from }/ is redundant, then the following must be true: L Aj)... = 1 J : {J Erv }'j L Aj =A j : a E"' }j where the first equation comes from setting b13 = 1 and all other bi 's to zero, and the second equation comes from setting bo = 1 and all other b/s to zero. From the two equations above, we get that L AjL Aj = 1. j : (J E"' Yj j : a E"' }'j This can be rewritten as L Aj + L Aj L )...) L Aj = 1. j : {J E"' }j j : (J E"' }j a Erv }j a Erv }j a E }j a E"' }j {J E }j {J Erv }j The second and fourth terms cancel. Since the third term is nonnegative, we have 2::: A.i 2: 1. j:(o,/3)E So the capacity of each edge in < l'i,"' l/ > is added in to LJ#L >..iU(rj,"' Yj). Therefore, we cannot have a E< }j,"' lj >,j E J, and a tf.< 15
PAGE 20
}/,"' }/ > because that would give us E#1 >.jU(}j,"' }j) > U(}[,"' }[) We are now ready to prove the WallaceWets Theorem. We restate the theorem for convenience. Note that this theorem holds for both the directed and undirected cases. Theorem 3.1 For all nonempty Y C V, the associated inequality, L b; :::; U(Y,"' Y) is redundant in the cut system if and only if either G(Y) or G("' Y) is not connected. Proof: We begin with the "if" direction. First, suppose G(Y) is not connected. Let Y = Yi U Yi where Yi n Y2 = 0 and there are no edges between Y1 and Y2 (See Figure 3.1). Since there are no edges between Y1 and Y2, we know that < Yi,"' Y1 > U < Y2,"' Y2 >=< Y,"' Y >. The inequality from Y is L b; :::; U(Y,"' Y) = U(YI' f"V YI) + U(Y2, f"V Y2) The inequality from Y1 is The inequality from Y2 is Summing, we get L b; + L b; + L b; + L b; = L b; + 2 L b; :::; u ( Y, f"V y). iEY lG
PAGE 21
w y 0 ,..__y Figure 3.1: Illustration of Y and"' Y Subtracting L:iEV b; = 0 leaves us with 2:: b; :::; U(Y,"' Y). iE"'Y Therefore, the inequality from Y is redundant. Next, suppose G("' Y) is not connected. Let "' Y = Y1 U Y2 where Y1 n Y2 = 0 and there are no edges between Y1 and Y2 Thus, < Y,"" Y >=<"' Yt, Yt > U <"' Y2, 1'2 >. Again the inequality from Y is 2:: b; :::; U(Y,"' Y) = U("' Yr, YI) + U("' Y2, 1';). iE"'Y The inequality from "' Y1 is 2:: b; :::; U("' Y1 Yt). iEY1 The inequality from "' Y2 is 2:: bi :::; U("' Y2, Y2). iEY2 Summing, we get Therefore, the inequality from Y is redundant. 11
PAGE 22
We now prove the "only if" direction. We assume that G(Yt) and G( ,..._ }/) are both connected, and we will show that the inequality corresponding to }/ cannot be redundant. Let l index the set that is the complement of}/, that is, }[ =rv }/. Let d be the arc membership vector for the cut defined by }j ( = 1 {::=::} a E< }j, ,..._ }j > ). Also, let dJ be the node membership vector for the set }j ( d{ = 1 {::=::} i E Yj). Let 11 = { 1, 2, ... 21V I} \ { L, l}. Let e be the vector of ones. The term Aoe will account for being able to subtract multiples of the equation that states that total supply equals total demand. We want to show that the following system has no solution: 'i/j E k Suppose the system is feasible, and let (5., ).L, E J1)) be a solution. Let 1/ = {j E lJ! > 0}. That is, 1/ indexes the inequalities which are used in constructing the redundancy of inequality /. If k rt.< }/, rv Yt >, then = 0 and so 0 = L 'jet+ 'Lei j E 1/ 'if k rt. < "' }/ > This equation tells us that q, = 0 if k 3< 1'/,"' Y/ > and if j E 11+. Written another way, this says: k 3< }/,"' Y/ >* k 3< }j,,...., }j > if 18
PAGE 23
y. J y. J Figure 3.2: Illustration of YJ and fj j E Jt If we negate the implication, we get that j E J1+ implies k E< }j, rv }j >+ k E < }/, rv Y/ >. This then is the same as saying That is, we cannot use any sets whose cutset arcs are not a subset of the arcs in < }/, rv }/ >. For all }j C V, we define two new sets (see Figure 3.2): Yj = }j n and fj = Yj n }{_. We will show that if }j is such that either Yj is a proper subset of }/ (0 1Yj 1}[) or fj is a proper subset of }{_ (0 1fj 1Y!_) then j (j_ Jr That is, then the inequality corresponding to }j is not used in constructing the redundancy of inequality l. First we will work with )7j. If we write the equation for (refer ring back to the equation for d1 ) we have 19
PAGE 24
When i E Y/, = 1, so we have 1 = L J.j d{ + 0 J.0 j E 11 1 + J.o = L J.j d{ j E 11 Vi E Y/. If q E 1/ and is a proper subset of Yt, then either there is an arc from Yq to Yt \ or there is an arc from Yt \ Yg to Yg. Since < Yq "' Yq > C < Yt, "' Yt >, there cannot be any arcs from to Yt \ Hence, there must be an arc from Yt \ to Let this arc be ( i, i'). Now consider any set lj such that i E lj and j E 1/. Since < lj,"' lj >C< Yl,"' Yt >,we must also have i' E lj. Thus, any set lj that contains i must also contain i'. This means that the following must be true: 1 + J.o = 2:: J.jdi < J.g + 2:: J.jd{ :==:; 2:: = 1 + J.o, j E 1/ j E 1/ j E 11+ which is a contradiction. Therefore, there is no q E 1/ with Yg a proper subset of Y/. The same argument is used to show that there is not q E 1/ with a proper subset of }{_. For this case, note that i E }{_ ::::} = 0, so we have the equation 0 = L J.jd{ + J.LJ.o j E 11+ J.1 J.o = L J.jd{ j E 11+ ViE }{_. If q E 1/ and Yq is a proper subset of }{_, then either there is an arc from to }{_ \ Yq or there is an arc from }{_ \ Yg to Since 20
PAGE 25
< Yq f'J Yq > C < }/, "" }/ >, there cannot be any arcs from to YL \ Hence, there must be an arc from }{_ \ to Yq. Let this arc be ( i, i'). Now consider any set }j such that i E }j and j E J/. Since < }j,"" }j > C < }/, f'J }/ >, we must also have i' E }j. Thus, any set }j that contains i must also contain i'. This means that the following must be true: = L < + L s; L = j E J1+ j E Jl+ j E J/ which is a contradiction. Therefore, there is no q E J/ with a proper subset of}[. Thus, the only index that could possibly belong to J/ is the one corresponding to V, say Yp = V. But then we \Vould have which is not possible. Thus, J/ must be empty, but then we have which is also not possible. Therefore, when G(Y) and G( f'J Y) are both connected, L b; s; U(Y,"" Y) iE....,y is never redundant. 21
PAGE 26
4. Feasibility in Directed Multicommodity Graphs 4.1 Preliminaries This thesis deals with linear multicommodity flows, ignoring in teger restrictions. We begin by noting that a multicommodity network with multiple sources and sinks for each commodity can be transformed into a multicommodity network that has a single source and sink for each commodity. This transformation is analogous to the transformation from multiple sources/sinks to a single source/sink as given by Ford and Fulkerson ([9]). Theorem 4.1 A capacitated multicommodity network N = [V, E, U] with multiple sources and multiple sinks for each commodity can be transformed into an equivalent multicommodity network N' = [V', E', U'] that has a single source and single sink for each commod ity. Proof: Let Sk V and Tk V be the indices for the set of sources and sinks, respectively, for commodity k. Let bk : V T be such that b7 = 0 for i tf. Sk u Tk, b7 < 0 for i E Sk, b7 > 0 for i E Tk, and I: b7 = 0 for each k. Construct N' as follows. V' = V U {Ok, Dk}, and E' = E U {(Ok,i: i E Sk),(i: i E Tk,Dk)}. U'(Ok,i) = b7 fori E Sk, U'(i,Dk) = bi for i E Tk, and U'(e) = U(e) for e E E. b0k = LiE Sk b7, b'Dk = Li E Tk b7, = 0 for i E V \(Sku Tk).
PAGE 27
Let x be any feasible flow in N. We will construct a feasible flow x' inN'. Let (x;)' = fore E E, (x0k)' = U'(Ok,i) fori E Sk, and = U'(i, Dk) for i E Tk. The capacity constraints are satisfied for all edges by definition. We also need flow conservation at each node. Li(xf.J' Li(xj,;)' = Li xf.i Li xj,i = OVk for i E V \ (sku Tk)LiE sk(x0k)' =LiE sk b7 = b0k vk. LiE = LiE Tk bf = biJk Vk. Lj(xJJ'Lj(xf.J)' = (x0k)' + Lj xj,iLj xf,i = bk + bk = OVk for i E Sk. 2:(xk )'2:(xk)' = "" xk. ("" xk. + 1 1 ] J, I ] I,] L..., J J, 1 L..., J I ,J (xkDk)') = bfbf = OVk fori E Tk. Therefore, x' is feasible inN'. 1, Conversely, let x' be any feasible flow in N'. We will construct a feasible flow x in N. Let = (x;)' for e E E. Since U'(e) = U(e) for e E E, Lk x; = Lk(x;)' :::; = Ue So the capacity constraints are satisfied. Li .rf.iLi xj,i = Li(xL)'Li(xj,;)' = OVk fori E V\ (Sk uTk) If i E sk then Lj(xJ.J' Lj(x7)' = (xok / + Lj xj,i Lj xL = 0 =? Lj xj,i Lj xf,j = bf. If i E Tk then Lj ( xj,i )' Lj ( xf,j )' = Lj xj,i Lj x7,j(xkDk)' = 0 =? Lj :rj,iLj x7,j = b7. Therefore, x is feasible in I, N. We illustrate this theorem with the following example. Example The following graph illustrates the addition of superorigins and superdestinations for each commodity. 23
PAGE 28
= 1 ti = 4 si = 2 = 3 = 3 = 1 For this example, node 01 has a supply of 4 + and node 02 has a supply of 6 (si + Placing a capacity of 1 on edge ( Oh st) and a capacity of 3 on edge ( 01 sD will insure that nodes and will send the proper amounts of commodity 1. Similarly, we place a capacity of 2 on edge ( 02 si) and a capacity of 4 on edge ( 02 sD. Node D2 has a demand of 6 (ti + tn and node D1 has a demand of 4 (tt + tD. Placing a capacity of 4 on edge (ti, D2 ) and a capacity of 2 on edge D2 ) will insure that nodes ti and will receive the proper amounts of commodity 2. Similarly, we place a capacity of 3 on edge (tt, D1 ) and a capacity of 1 on edge D1 ). Thus, we see that any flow that is feasible in the original network is feasible in the new network, and vice versa. Note that this theorem holds whether the graph is directed or undirected. For the remainder of this thesis we will assume, without loss 24
PAGE 29
of generality, that each commodity has a single origin and a single destination. 4.2 The System Wallace and Wets work with a system of inqualities which define feasibility for a set of supplies and demands when the supply and demand nodes are not known a priori. We wish to develop an analogous system for the multicommodity case, and then we will characterize the redundant inequalities in that system. If the source and sink is known for each commodity, then a neeessary condition for feasibility of a set of demands q is \fY c V. This condition is sufficient for the classes of graphs identified by Nagamochi and Ibaraki (see Chapter 2). In order to place this condition in the Wallace and Wets setting, we need to generalize this condition for the case where the supply and demand nodes are not know a priori. Looking at the system for a single commodity, L b; ::; U(Y, "' Y) \fY c V, iEY one might guess that the system for multicommodities can be obtained by simply summing over each commodity. The resulting system is p L L b7 ::; U(Y, "' Y) \fY c V. k=l iEY The following example shows that this is not enough. 25
PAGE 30
Example The inequalities are: Y = { 1} : + + :S U 1 Y = { 2} : + + bi :S u2 = 1, and u1 = 1, u2 = 1. However, it is easily seen that this set of demands and capacities are not feasible. Thus, we try a stronger system. We actually need to sum over all possible combinations of commodities. This results in L L b7 :S U(Y,rv Y) \fY c V, \f K, kEl\ iE,..,y where I< is a nonempty set of commodities. This condition gives us the desired system. Theorem 4.2 The set of inequalities L L b7 :S U ( Y, rv Y) \fY c V, \f I< kEK iE,..,y is a necessary condition for feasibility of b, the vector of demands. Proof: We start with the system of constraints for a directed multicommodity flow problem, "'"' xk "'"' Xk = bk L.....1' L.....lJ Vi jl(j,i)EA jl(i,j)EA 26
PAGE 31
p L x7j Uij Vi,j k=l xt20 Vk,i,j and we want to show that this system implies the inequality L L b7 = U(Y,"' Y). kEK iE"'Y Recall that U(Y,"' Y) = l:::(j,i):jEY,iE"'Y Uji We begin by working with the first constraint in the multicommodity flow problem. First, we sum both sides of the equation over i E"' Y to obtain I: b7 = I: ( I: xj;I: x7j) iE"'Y iE"'Y jl(j,i)EA jl(l,j)EA We next sum both sides over k E /\., obtaining = I: I: I: ;r); I: 2: I: xt kEf{ iE"'Y jl(j,i)EA kEK iE"'Y jl(i,j)EA = I: ( I: xj; + I: :rj; I: xt I: x7j) kEK iEY El. iEY iEY jEY jE"'1. jEY jE"'Y Since x71 2 0, we now have kEK El' jEY I: I: I: I: :rJ; kEf{ iE"'Y kEK EY jEY Now if we work with the second constraint in the multicommodity flow problem, again using the constraint that xt 2 0, we have
PAGE 32
This gives us L L xji ::; L Uji = U(Y,""' Y). ]EY kEK jEY This gives us our desired inequality, L L b7 ::; U(Y, "' Y). The next lemma relates this system to the system of inequalities for a directed multicommodity graph when the sources and sinks are known a priori. Lemma 4.3 The set of inequalities L L b7::; U(Y,""' Y) \fY c V, \f I< kEK contains the set of inequalities \fY c V. Proof: We know that qk = = and b7 = 0 for i =/:sk, tk for all k. We have a set of inequalities for each set of commodities; in particular, pick [{'such that Vk E I<', sk E Y and tk E"' Y. So our system contains the inequalities L L b7::; U(Y,""' Y) \fY c V. kEK' The left side of this inequality has bf for i = tk and bf = 0 for all other i E"' Y. Fori = tk, bf = qk, so the summation yields LkEK' qk. We now have a system of linear inequalities which serve as a necessary condition for feasibility of multicommodity flows in a directed 28
PAGE 33
graph when the supply and demand nodes are not known a priori. In the next section, we will extend the WallaceWets Theorem to this system. 4.3 Redundancy Theorem The WallaceWets Theorem extends quite naturally to the directed case. Using the system from the previous section, along with the requirement that supply equals demand for each commodity, we are able to characterize the redundancy in the system. This characterization is the same as the WallaceWets characterization for the single commodity system with one exception. For our system we need to separate the cases of U(Y,"' Y) = 0 and U("' Y, Y) = 0. Theorem 4.4 [Redundancy Theorem for Directed Graphs] Let G be a connected, capacitated, directed, multicommodity graph with p commodities, where each commodity has one origin and one destination. (1) If U(Y,"' Y) > 0 and U("' Y, Y) > 0, then the inequality corresponding to the cut < Y,"' Y >, L L b7 ::; U(Y,"' Y) v K, kEK is redundant in the cut system if and only if either G(Y) or G("' Y) is not connected. (2) If U(Y,"' Y) = 0 (connectedness of the graph then implies that U("' Y, Y) > 0), then all sets [{ with more than one element yield redundant inequalities. The inequalities L b7 ::; U(Y,'"" Y) Vk 29
PAGE 34
are redundant in the cut system if and only if either G(Y) or G( rv Y) is not connected. (3) If U("' Y, Y) = 0 (connectedness of the graph then implies that U(Y,"' Y) > 0), then all sets I< yield redundant inequalities except for I<= {1, 2, ... ,p}. The inequality p L L b7 :S: U(Y, "' Y) k=l iEY is redundant in the cut system if and only if either G(Y) or G( rv Y) is not connected. Proof: (1) We will first prove the "if" direction. Assume that one of G(Y) and G( rv Y) is not connected. Case 1: G(Y) is not connected. Let Y = Y1 U Y2 where Y1 n Y2 = 0 and there are no edges between We examine the inequalities L L b7 ::::: U(Y, "' Y) \;/I<. kEK iE ..... }' The inequalities from Y1 are The inequalities from Y2 are L L b7 = L L b7 + L L b7::; U(Y2, "' Y2) VI<. kEK iE"'Y2 kEf,iEY1 kEK iEY Summing these inequalities gives kEK iEY 30
PAGE 35
Subtracting LkEK LiEV b7 = 0 gives L L b7 U(Y,rv Y) VI<. kEK Thus, those inequalities are redundant. Case 2: G("' Y) is not connected. Let "' Y = Yi U Y2 where Y1 n Y 2 = 0 and there are no edges between Y1 and Y2 We examine the inequalities L L b7 U(Y,rv Y) VI<. kEK The inequalities from "' Yi are L VJ{. kEK iEY, The inequalities from "' Y2 are L L b7 U(rv Y2, Y2) VJ{. kEK iEY2 Summing these two inequalities gives Thus, the inequalities are redundant. These proofs are sufficiently general to hold for U(Y,""' Y) 0. Thus, we have also proved the "if" direction for (2) as well. We now prove the "only if" direction. We assume that an mequality is redundant, and we will show that at least one of the corresponding graphs is not connected. If L L b7 ::; u ( Yq ""' Yq) kEf\' 31
PAGE 36
is redundant, then it is a nonnegative combination of linear in equalities from sets other than Yg. To see this, assume that the above inequality is a nonnegative combination of linear inequal ities in the cut system, some of which may be generated by the set Yq. Clearly the only way the inequality can be a nonnega tive combination of inequalities generated only by the set Yg is if U(Y,'"" Y) = 0. This exception is treated in part (2) of the theorem. So the dependency set must contain at least one in equality generated by a set other than Yg. However, it may not contain any edges not in < Yq,'"" Yq > We assume that G(Yq) and G('"" Yg) are both connected, and we will derive a contradic tion. First we will show that an inequality from Ys, Ysn "' Yq # 0, Ysn"' Yq #'"" Yq, cannot be in the dependency set. Since G("' Yq) is connected, there is an edge in < }j,"' Yq/Yj > or there is an edge in <"' Yq / }j, }j > If the former is true, we are done with this case. If the former is false, then the latter is true. Call the edge (a, (3). Sine a and (3 must be counted an equal number of times, there must be some set, containing a and not contain ing (3, whose corresponding inequality is in the dependency set. But then this cutset contains the edge (a, (3), which is not possi ble. Thus, an inequality corresponding to Ys with Ysn "' Yq # 0, Ysn"' Yg #'"'' Yq, cannot be in the dependency set. The same can be shown for a set Yt with Yt n Yq # 0, Ys n Yq =/:Yq The only remaining possibility is that an inequality corresponding to "' Vq is in the dependency set. This can only occur if U(rv Yq, Vq) = 0, 32
PAGE 37
which is handled in part (3) of the theorem. Thus, we have shown that the redundant inequality L L b7 S U(Yq, rv Yq) kEK' must be a nonnegative combination of linear inequalities from sets 21VI other than Yq. That is, :3.X E such that Note that the above equation holds for all b. In particular, for any choice of k, we can set bi to be zero for all i and for all j =/= k. Therefore, L b7 = L As L b7 s#q iEY, for each k. This gives us that L b7 S U(Yq, rv Yq) is redundant in the cut system for each commodity k. Thus, each inequality corresponding to Yq is redundant for each commodity k. We can now apply the WallaceWets Theorem to conclude that either G(Yq) or G("' Yq) is not connected. (2) Assume U(Y,"' Y) = 0. We have the inequalities L b7 S U ( Y, "' Y) = 0 V k. Summing over k E l\: IKI > 1 gives L L b7 S 0 = U ( Y, rv Y) VI<: II 1. kEK 33
PAGE 38
Thus, the inequalities L L b7 ::; U(Y,"' Y) VK: II 1 kEK iEY are always redundant when U(Y,"' Y) = 0. (3) Assume U("' Y, Y) = 0. Let [{' be any proper subset of the commodities. We will show that the inequality L L b7 ::; U(Y,"' Y) kEK' iEY is redundant. From the set "' Y, we have the inequalities L L b7::; U("' Y, Y) = 0 VK. kEK iEY In particular, if f{P is the set of all commodities, we have the inequality I: I: b7::; o. kEKP(K' iEY Since LiEY b7 =LiEY b7, this gives us I: I: b7::; o. kEKP(K'iEY Adding this to the inequality L L b7 ::; U(Y,"' Y) kEKP iEY results in the original inequality. We note that when p = 1 (one commodity) this system reduces to the system used by Wallace and Wets. The inequality for the set Y becomes LiEY bi ::; U(Y,"' Y). We proceed now to the undirected case, which is not as straightforward as the directed case. 34
PAGE 39
5. Feasibility in Undirected Multicommodity Graphs 5.1 The Absolute Value System We will now work with undirected multicommodity graphs, meaning that the edges are not oriented and flow may travel in either direction on an edge. In particular, flow from different commodities may travel in opposite directions on the same edge. In working towards an extension of the WallaceWets Theorem to the undirected multicommodity case, we need to have a system of inequalities which is a necessary condition for feasible demands (and which will be sufficient for the cases discussed in Chapter 2). The traditional system of cut inequalities, l:)qk: 1::::; k:=:; p, Y separates Sk and tk):=:; U(Y,"' Y) V, assumes that the origin and destination nodes for each commodity are known a priori. We need to develop a system in which the origin and destination nodes do not need to be known a priori. As a first attempt, one might try generalizing the single commodity cut system by summing over all commodities, as in the directed case. If we use the system from the directed case, we have: I>7 = o vk iEV L L b7::::; U(Y,"" Y) VY c V, VI<. kE/\ iE"'Y However, this system is not restrictive enough in the undirected case. Consider the following graph.
PAGE 40
u The above system would give rise to the following set of inequalities: + = 0 bi + = 0 y = {1}: K={1}: b1 < u 2J{ = {2} : b2 < u 2 f{ = {1,2}: b1 + b2 < u 2 2y = {2}: I<={1}: b1 < u 1 [{ = {2} : b2 < u 1f{ = {1,2}: b1 + b2 < u 1 1 This system allows for = 1, = 1, bi = 1, = 1, and u = 1. However, we can easily see that this set of demands, along with the given capacity, is not feasible. In order to satisfy the demands, we would have to send a total of 2 units of flow across the edge, when only 1 unit is allowed. The problem is that at each node, the demand for one commodity cancels with the supply for the other commodity. This problem is alleviated by taking the absolute value of the sum of the b;'s for each commodity. That is, we use the system 36
PAGE 41
p I: I I: b71 :::; U(Y,"' Y) \IY c V. k=l iEY Now the system for the above graph is: + = 0 Y = { 1} : I I + I I :::; u Y = {2} : I+ lbil :::; u We see that the set of b7's that was feasible in the old system is not feasible in this system. In fact, this gives us the correct system for every multicommodity graph, as the next theorem shows. Note that we do not need to sum over k E [{ because the inequalities corresponding to sets [{ other than the full set of commodities will be dominated by the inequality above. For example, for the graph in the above example, we would get Y = { 1 } : K = { 1 } : 1 1 :::; u, which is dominated by the inequality obtained by summing over all commodi ties. Theorem 5.1 The set of inequalities p L I L b71:::; U(Y,"' Y) VYc v k=l iE}' is equivalent to the set of inequalities L(qk: 1 ::=; k ::=; p, Y separates Sk and tk) ::=; U(Y,"' Y) \lYe v. 37
PAGE 42
Proof: Since Qk = bik = and bf = 0 for i 1sk, tk for all k, we will treat separately the cases when Y does and does not separate Sk and tk. Case 1: Y does not separate Sk and tk. Then sk and tk are either both in Y or both in "' Y. If sk and tk are both in Y, then 12: b71 = + = o. iEY If Sk and tk are both in "' Y, then bf = 0 Vi E Y. Therefore, if Sk and tk are not separated, then I::iEY bf = 0. Case 2: Y does separate sk and tk. Then either Sk E Y or tk E Y, but not both. bf = 0 for all other i E Y. Then I 2: b71 = = Qk iEY Thus, the absolute value inequality is equivalent to limiting Y to sets that separate Sk and tk, in which case the two inequalities are the same. This system of inequalities, which we will refer to as the cut system, has many properties which are not common to a general system of absolute value inequalities. First, we know that every inequality in the cut system contains absolute values. Further, for a given inequality, the number of terms within each absolute value is the same, and it is equal to the cardinality of the set Y. So, for example, we cannot have lx1l + lx2 + x31 :::; u in a cut system. Similarly, each inequality in the cut system has the same number of absolute value terms, which is equal to the number of commodities. That is, we cannot have both lx11 :::; u and 38
PAGE 43
jx11 + lx2l s; u in the same system. Additionally, a term that appears inside of one absolute value will not appear anywhere else in that inequality. That is, we cannot have jx1 + x2i + lx2 + x3l s; u in a cut system. Finally, we note that the coefficients on all terms within the absolute values, as well as on the absolute value quantities themselves, are 01, and the righthand side is always nonnegative. These observations lead us to some lemmas about the cut system. An absolute value inequality from the cut system is equivalent to a system of 2P linear inequalities. We can express the jth linear inequality as p L 6kj L b7 s; U(Y, rv Y), k=l iEY where 6kj E { 1, 1}. In the proof of the next lemma, we will simply write U for U(Y, rv Y). To illustrate the equivalent system of linear inequalities, consider the following absolute value inequality: The corresponding system of linear inequalities is: We will sometimes refer to this system as a family of linear inequalities. We next show that we cannot obtain an inequality in this system as a nonnegative combination of only other inequalities in this system. 39
PAGE 44
Lemma 5.2 The family of linear inequalities corresponding to a given absolute value inequality from the cut system is internally nonredundant. Proof: Consider the jth linear inequality corresponding to a given absolute value inequality: p 2::: rS kj 2::: b7 s u. k=1 iEY Reverse the sense of the inequality and make it strict: p L rS kj L b7 > U. k=1 iEY The system with this new inequality in place of the old one is feasible if and only if the old inequality is nonredundant. \Ve will construct a feasible solution to the reversed system: Then ViE Y bk = { ' if rSki = 1 if rSicj = 1 .f" k IYI P L...t rSkj L...t bi = I I [1 > U. k=1 iEY y ]J 1 Further, changing any rS kJ from 1 to 1 or from 1 to 1 decreases the sum by making it equal to U. Thus, this b satisfies all of the linear inequalities in this family, so the jth inequality is not implied by the others. This lemma does not hold for the linear system corresponding to a general absolute value inequality. The following example will illustrate this. 40
PAGE 45
Example Consider the inequality A partial enumeration of the corresponding linear inequalities gives: The last two inequalities are copies of each other. Thus, this system is not internally nonredundant. We can also make some observations about an inequality which is known to be redundant. Lemma 5.3 A redundant linear inequality cannot be formed as a nonnegative combination of linear inequalities which are all from one family, different from the family of the redundant linear inequality. Proof: Let aiq be the node membership function for the set Yq: aiq 1 iff i E Yq. Let Ceq be the edge membership function for the cut defined by Yg: Ceq = 1 iff e E< Yg, rv Yg > We want to show that p L Okj L aiqb7 S: U(Yq, rv Yg) = L CeqUe k=1 iEV eEE cannot be formed as p L Ar L Okr L aitb7 s: U(Yt, rv = L CetUe, (.\r 0, L Ar = 1, Aj = 0). r k=l iEV eEE r 41
PAGE 46
Assume the two inequalities are equal. Then Ct Lr Ar = cq. This giVes us that Lr Ar = 1 and Ct = Cq If the network is connected then either Yt = Yq or Yt =rv Yq. Since this is not possible, the two inequalities cannot be equal. Lemma 5.4 If a linear inequality from the cut system is redundant, then it is redundant for each commodity. Proof: If p L bkj L a;qb7 U(Yq,"' Yq) k=1 iEV is redundant, then it is a nonnegative combination of linear inequalities 2P X 21VI from sets other than q. That ts, :J). E such that k=1 iEV r s;j:q k=1 iEV k=1 r s;j:q iEV Note that the above equation holds for all b. In particular, for any choice of k, we can set b1 to be zero for all i and for all j 1k. Therefore, iEV Which gives us that r s;j:q iEV bkJ La;qb7 U(Yq,"' Yq) iEV is redundant in the cut system for commodity k. 5.2 Redundancy Theorem We have seen many characteristics of single commodity flows that do not extend to the case of multicommodity flows. The question which motivated this thesis was whether the WallaceWets Theorem holds in the 42
PAGE 47
multicommodity case. In this section we prove that using the absolute value system, the WallaceWets Theorem can be extended to undirected multicommodity graphs. In what follows, we assume the cut system to be p L I L b71 :::; U(Y, "' Y) V k=l iEY 2:: b7 = o ( k = 1, ... p). iEV Theorem 5.5 [Redundancy Theorem for Undirected Graphs) Let G be a connected, capacitated, undirected, multicommodity graph with p commodities, where each commodity has one origin and one destination. (1) Only one of the pair of inequalities p L I L b71 :S U(Y, rv Y) k=l iEY p L I L b71 :S U(Y,rv Y) k=l is ever necessary. That is, we need only consider the inequality from Y or""' Y, but not both. ( 2) The inequality corresponding to the cut < Y, rv Y >, p L I L b71 :S U(Y,rv Y), k=l is redundant in the cut system if and only if either G(Y) or G(""' Y) is not connected (Y =/:0, rv Y =/:0). t13
PAGE 48
Proof: (k 1, ... p), we have that LiEY bf LiE,...,y bf. Therefore, k=l iEY So only one of each pair of inequalities is needed. (2) We will first prove the "if" direction. If G(Y) and G(,....., Y) are not both connected, we may assume, without loss of generality, that G(,....., Y) is not connected. Let ,....., Y = Y1 U Y2 where Y1 n Y2 = 0 and there are no edges between Yi and }2. We will show that the inequality from Y is dominated by the sum of the inequalities The inequality from Y is p p L I L b71 = L I L b7+ L b71:::; U(Y,,....., Y) = U(Y, Yi)+U(Y, }2). The inequality from ,....., Y1 is p L I L bfl:::; U(Yl,"' Y!). k=l iEY1 The inequality from ,....., Y2 is p L I L b71:::; U(Y2,,....., Y2) k=l iEY2 Summing the inequalities from,....., Y1 and ,....., Y2 we get p 2:::(1 L bfl +I L bfl):::; U(Y!,,....., Y!) + U(Y2,,....., Y2) k=l iEY1 iEY2 However, since there are no edges between Y1 and Y2 we get that 44
PAGE 49
We next prove the "only if" direction. If the qth inequality p L I L b71 :::; U(Yq, "' Yg) k=l i E"' Yq is redundant, then some linear inequality (of the 2P corresponding to it) is redundant. Assume it is the jth linear inequality. By Lemma 5.4, if the jth inequality is redundant, then it is redundant for some single commodity. At this point, we can apply the Wallace and Wets Theorem (Theorem 3.1) to this inequality, and we conclude that either G(Yg) or G("' Yg) is not connected. We note that when p = 1 (one commodity), the system of absolute value inequalities reduces to the same system of linear inequalities that is used in the WallaceWets Theorem. We get that the inequality from set Y is I L b; I :::; u ( Y, "' y). iE"'Y This is equivalent to the following two linear inequalities, L b; :S U(Y, rv Y) iE"'Y L b; = L b; :::; U(Y, ,..,_ Y), iE"'Y iEY which are the inequalities that Wallace and Wets would generate from the sets Y and "' Y. Thus, if p = 1, our theorem is equivalent to the WallaceWets Theorem. 45
PAGE 50
Example We illustrate the preceeding theorem using the following graph. 1 U3 ul 5 2 u2 u4 Us 4 U6 3 Assume there are p commodities. The inequalities from Y = {1, 2, 3} and Y = {1, 2, 5}, as well as others, are nonredundant. Both G(Y) and G(rv Y) are connected. The inequality from Y = {1,2,3} is p L I + I :::; u2 + u3 + u6. k=l Y = {2, 4, 5} is an example of G(Y) connected but G( rv Y) not connected. The (redundant) inequality is p L + b;l :::; tt1 + U3 + tts + u6. k=l To construct the inequalities which dominate this one, let Y1 = {1} and Y2 = {3}. The inequality from ,....., Y1 is p L :::; u1 + U3. k=l The inequality from ,....., Y2 is p L lb;l:::; Us+ u6. k=l 46
PAGE 51
Summing these gives p + lb;l) Ut + U3 + U5 + U6 k=l which dominates the inequality from Y. Finally, Y = {3, 5} is an example of G(Y) and G("' Y) both not connected, so the inequality from Y is redundant. 5.3 Some Building Blocks This section contains two types of results. The first several theorems demonstrate how our knowledge of redundant inequalities for one graph may be used to determine redundant inequalities for a related graph. The last several theorems count the number of redundant or nonredundant inequalities in general and for some specific graphs. These theorems give a measure of the usefulness of the Redundancy Theorem. As a corollary to the Redundancy Theorem, we see that any inequality that is redundant in a graph is redundant in all graphs formed by removing only edges from the original graph. Theorem 5.6 [Corollary to Redundancy Theorem] If G' = [V, '], E' C E, then any inequalities that are redundant for G are redundant for G'. Proof: If either G(Y) or G("' Y) is not connected in G, then it is also not connected in G'. 47
PAGE 52
Example To illustrate, consider the following graphs G and G'. 1 2 1 2 [SJ[SJ 4 3 4 3 G G' We see that G and G' have the same vertex set, and that the edge set of G' is a subset of the edge set of G. The set Y = { 1, 3} gives a redundant inequality in G because G("' Y) is disconnected. The same set also gives a redundant inequality in G'. However, if we allow G' to be any subgraph of G, that is, if we allow the vertex set of G' to be a proper subset of the vertex set of G, then the corollary is not true. To illustrate, consider the following graphs G and G'. 1 2 1 4 3 4 3 G G' Now the set Y = {1, 3} gives a redundant inequality for G, but not for G'. 48
PAGE 53
Corollary 5. 7 If G = [V, EJ, G' = [V, E'], G" = [V, E"J, ... is a sequence of graphs such that E :::> E' :::> E" :::> .. then the number of nonredundant inequalities for G is at least as large as the number of nonredundant inequalities for G', which is at least as large as the number of nonredundant inequalities for G". Proof: By Theorem 5.6, every inequality which is redundant for G is also redundant for G'. Every inequality which is redundant for G' is also redundant for G", and so on. In order to use the Redundancy Theorem, we must find all ver tex partitions Y of V such that G(Y) and G("""' Y) are both connected. However, if we have already done this for two graphs and we then form a new graph by joining the first two in a specific way, then we may not have to recompute which sets give necessary inequalities. We may be able to find all the necessary inequalities through appropriate combinations of the sets we already have. One specific way of combining two graphs is with a bridge, that is, an edge joining one vertex of the first graph to one vertex of the second graph. Then we can find all the necessary inequalities for the new graph by combining the entire vertex set of each original graph with one of the vertex partitions from the other original graph which is already known to give a necessary inequality for that graph. Theorem 5.8 Let G1 = [V1 EI], G2 = [V2 E2 ] be connected graphs, v! n v2 = 0. Let G = Gl u G2 U(vl, v2) = [V, E], where V[ E V1 and v2 E \12 (See Figure 5.1). Let JV1 = {Nf, N{, ... be the collection of vertex partitions which give nonredundant inequalities for the graph G1 Let JV2 = { NL Ni, ... be the collection of vertex 49
PAGE 54
Figure 5.1: Graph with a bridge partitions which give nonredundant inequalities for the graph G2 The vertex partitions which give nonredundant inequalities for the graph G are V1 E N2 : v2 E and v2 E Nl :VI and vl. Proof: By construction, the induced subgraphs on each of the sets listed above and each of their complements are connected. We need to show that there are no other vertex partitions of V (Y U "' Y = V, Y n "' Y = 0) such that G(Y) and G("' Y) are both connected. We have already used all partitions which completely contain either v1 or V2 The only other possibility is that Y contains a proper subset of vertices from both V1 and V2. That is, Y = Y1 U Y2 where Y1 c \il., Y1 =f. 0, and Y2 c \12, Y2 =f. 0. If v1 E Y and v2 rf. Y, then G(Y) and G("' Y) must both be disconnected since neither contains the edge ( v1 v2), the only edge joining vertices of vl and v2. The same is true if Vt rt. y and v2 E Y. If Vt, v2 E y then it is possible that G( Y) is connected, but G("' Y) is necessarily disconnected. If v1 v2 Erv Y, then it is possible that G("' Y) is connected, but G(Y) is necessarily disconnected. Thus, there are no other partitions of G with G(Y) and G( rv Y) both connected so
PAGE 55
A similar result holds if G has an articulation vertex. That is, G is the union of two graphs G1 and G2 that share a common vertex v, but no common edges. The one difference is that in this case V1 gives a nonredundant inequality only if G2 \ v is connected. Theorem 5.9 Let Gr = [\/1 1], G 2 = [V2 E2 ] be connected graphs with ErnE2 = 0, VinV2 = {v}. Let G = GrUG2. Let N1 = { Nl, N{, ... be the collection of vertex partitions which give nonredundant inequalities for the graph G1 Let N2 = {Ni,N:f, ... ,N;2 } be the collection of vertex partitions which give nonredundant inequalities for the graph G2 The vertex partitions which give nonredundant inequalities for the graph G are Vr U { E Nz : v E and VzU{N{ E Nr: v EN{}. Proof: By construction, the induced subgraphs on each of the sets listed above and each of their complements are connected. We need to show that there are no other vertex partitions of V (Y U "" Y = V, Y n "" Y = 0) such that G(Y) and G(""' Y) are both connected. We have already used all partitions which completely contain either V1 or V2 The only other possibility is that Y contains a proper subset of vertices from both V1 and V 2 That is, Y = YiUY 2 where Yr c Vr,Yr # 0, and Yz c V2,Y2 # 0. If v E Y, then G(rv Y) is necessarily disconnected. If v rf. Y, then G(Y) is necessarily disconnected. Thus, there are no other partitions of G with G(Y) and G( rv Y) both connected. V./e now know that when checking the necessary conditions for 51
PAGE 56
feasibility of a multicommodity graph, we need only check inequalities corresponding to sets Y which have both G(Y) and G(,...., Y) connected. Do we really see much reduction when we discard inequalities corresponding to sets Y which have either G(Y) or G(,...., Y) (or both) disconnected? The following theorem gives a lower bound on the amount of reduction. Theorem 5.10 Let G be a graph on n vertices, and let the degree of the minimum degree vertex be o( G). Then using the Redundancy Theorem results in a reduction of at least n1S(G) ( n1o(G) ) L = 2n!S(G) 1 i=l i absolute value inequalities that must be checked for feasibility. Proof: We want to count the number of disconnected induced subgraphs of G. However, if G' = [V', E'] is a disconnected induced subgraph and G" = [V", E"] is also an induced subgraph, with V" = V \ V', then we only want to count one of that pair. A lower bound on this number can be computed by forming all sets consisting of the minimum degree vertex, v, and at least one vertex not adjacent to v. We count that by taking combinations of one or more of then1 <5( G) vertices that are neither v nor adjacent to v. Corollary 5.11 If G is a complete graph, then no reduction is provided by the Redundancy Theorem. We note that the above bound is tight for the class of graphs that have an induced subgraph on n1 nodes which is complete. Sometimes it makes more sense to look a.t how many inequalities are left to be checked after applying the Redundancy Theorem, rather 52
PAGE 57
than how much reduction was realized. Note that without this theorem, we would always have to check an exponential number of inequalities. For some special cases, we can show that after applying the theorem, we only need to check a linear number of absolute value inequalities. That is, there are a linear number of partitions of the vertices so that the induced subgraphs on both partitions are connected. Theorem 5.12 If G is a tree on n vertices, then n1 absolute value inequalities are needed. Proof: Removing any edge from a tree disconnects the graph. Removing any more than one edge separates the graph into more than two com ponents. Thus, the only partitions of the vertices so that the induced subgraphs on both partitions are connected are those that consist of all the vertices on one side of a particular edge. Since a tree on n vertices has n1 edges, there are n1 partitions which meet the stated criteria Hence, there are n 1 necessary inequalities. We also know of a case when a quadratic number of inequalities need to be checked. Theorem 5.13 If G is a cycle on n vertices, then 1) absolute value inequalities are needed. Proof: There are connected subgraphs on 1, 2, ... n 1 nodes, and there are n connected subgraphs of each size. The subgraph on the complement of each of these node sets is also connected. However, since we want to count each graph and its "complement" only once, we must divide the total number of connected subgraphs by two. Thus, there are 1) 53
PAGE 58
partitions of V such that both C(Y) and C("' Y) are connected. If a graph contains a bridge or an articulation vertex, as in Theorem 5.8 and Theorem 5.9 then we can find the number of necessary inequalities just by looking at the subgraphs on either side of the bridge or articulation vertex. Theorem 5.14 Let C be a graph with a bridge, such as de scribed in Theorem 5.8. The number of nonredundant inequalities is n1 + n2 + 1, where n1 and n 2 are the number of nonredundant inequalities for graphs C1 and C2 respectively. Proof: In Theorem 5.8, we construct IN11 + IN21 + 1 vertex partitions of C which give nonredundant inequalities. If we let INti = n1 and IN21 = n 2 then this number is n1 + n2 + 1. Theorem 5.15 Let C be a graph with an articulation vertex, such as described in Theorem 5.9. The number of nonredundant inequali ties is n 1 +n2 where n 1 and n 2 are the number of nonredundant inequalities for graphs C1 and C2 respectively. Proof: In Theorem 5.9, we construct IN11 + IN21 vertex partitions of C which give nonredundant inequalities. If we let IN11 = n1 and !Nzl = nz then this number is n1 + nz. Using combinations of the above theorems, we can compute the number of necessary inequalities for several graphs with special structures. For example, if C has a bridge, and G1 is a cycle and C2 is a tree, then we know that n1 = 1) and n2 = n"1, where n' and n" are the 54
PAGE 59
number of vertices of G1 and G2 respectively. Therefore, the number of nonredundant inequalities for G is !n'(n'1)+n"1+1 = !n'(n'1)+n". 55
PAGE 60
6. A venues for Further Research This thesis opens several avenues for further research. We be lieve that there are some further special properties of the absolute value inequalities used in Chapter 5. We have not yet been able to find counterexamples or proofs of the following conjectures. Conjecture 6.1 The dependency set for a redundant linear inequality contains at most one linear inequality from each family corresponding to a given absolute value inequality. The proof of this conjecture would lead us to a proof for the "if" direction of the following conjecture. The "only if" direction of the next conjecture is readily apparent. Conjecture 6.2 The inequality I Z:::iEY bfl :'S: U(Y,,...., Y) is nonredundant in the cut system if and only if the 2P linear inequalities corresponding to it are all nonredundant in the cut system. Another direction would be to consider the classification of nodes as supply, demand, or transshipment nodes. The work in this thesis as sumes that no node classifications are known a priori. Greenberg ([14]) has demonstrated that the WallaceWets Theorem does not extend immediately to the situation when nodes are preclassified as supply, demand, and transshipment nodes. It is not known how the theorem must be changed for this case. Classification of nodes can also be looked at in the multicommodity setting. Additionally, one could consider the effects of a
PAGE 61
partial classification of the nodes, which in the multicommodity setting may mean that different nodes are classified for different commodities. Some further work is also possible in the area of counting the number of necessary inequalities for special graph structures. There are many special cases that have not been covered in this thesis. One partic ular possibility is to find a bound on the number of necessary inequalities for an arbitrary /connected graph. 57
PAGE 62
Glossary articulation vertex A vertex whose removal mcreases the number of components of the graph bridge An edge whose removal increases the number of components of the graph complete graph A graph with an edge between every pair of vertices connected graph A graph in which there is a path between every pair of vertices. dependency set A system of inequalities which implies a redundant in equality. feasible network A network in which the required flow can be shipped without violating the capacities of any edges. multicommodity graph A graph in which flow must be sent from spe cific origins to specific destinations. redundant inequality An inequality which is implied by other inequal ities in the system. 58
PAGE 63
BIBLIOGRAPHY [1] A. A. Assad, 1978. Multicommodity Network FlowsA Survey, Net works 8, 3791. [2] D. A vis and M. Deza, 1991. The Cut Cone, Embeddability, Com plexity, and Multicommodity Flows, Networks, 21, 595617. [3] M. Bellmore, H. J. Greenberg, and J. J. Jarvis, 1970. MultiCommodity Disconnecting Sets, Management Science 16:6, B427B433. [4] C. Berge, 1985. Graphs, NorthHolland, Amsterdam. [5] R. C. Burk and J. S. Provan, 1995. Multiterminal and Multicommod ity Cuts in TerminalPlanar Graphs, UNC/OR TR9411. [6] Y. L. Chen and Y. H. Chin, 1992. Multicommodity Network Flows with Safety Considerations, Operations Research 40:51, S48S55. [7] P. L. Erdos and L. A. Szekely, 1992. Evolutionary Trees: An Integer Multicommodity MaxFlowMinCut Theorem, Advances in Applied Mathematics 13, 375389. [8] J. M. Farvolden, W. B. Powell, and I. J. Lustig, 1993. A Primal Parti tioning Solution for the ArcChain Formulation of a Multicommodity Network Flow Problem, Operations Research 41:4, 669693. [9] L. R. Ford, Jr. and D. R. Fulkerson, 1962. Flows in Networks, Prince ton University Press, Princeton, NJ. [10] D. R. Fulkerson, 1968. Networks, Frames, Blocking Systems, in Math ematics of the Decision Sciences: Part 1 (B. B. Dantzig and A. F. Veinott, Jr., eds.), Lectures in Applied Mathematics 11, American Mathematical Society, Providence, RI, 303334. [11] D. Gale, 1957. A Theorem on Flows in Networks, Pacific Journal of Mathematics 7, 10731082. [12] S. Ghannadan and S. W. Wallace, 1994. Feasibility in Capacitated Networks: The effect of individual arcs and nodes, Preprint.
PAGE 64
[13] F. Glover, D. Klingman, and N. V. Phillips, 1992. Network Models in Optimization and Their Applications in Practice, John Wiley & Sons, Inc., New York. [14] H. J. Greenberg, 1993. Consistency, Redundancy, and Implied Equal ities in Linear Systems, UCD/CCM Report No. 14. [15] A. J. Hoffman, 1960. Some Recent Applications of the Theory of Linear Inequalities to Extremal Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics 10. [16] T. C. Hu, 1963. Multicommodity Network Flows, Operations Re search 11, 344360. [17] T. C. Hu, 1969. Integer Programming and Network Flows, Addison Wesley Publishing Co., Reading, MA. [18] M. Iri, 1971. On an Extension of the MaximumFlow MinimumCut Theorem to Multicommodity Flows, Journal of the Operations Re search Society of Japan, 13:3, 129135. [19] A. Karzanov, 1985. Metrics and Undirected Cuts, Mathematical Pro gramming, 32, 183198. [20] A. V. Karzanov, 1987. HalfIntegral FiveTerminus Flows, Discrete Applied Mathematics 18, 263278. [21] J. L. Kennington, 1978. A Survey of Linear Cost Multicommodity Network Flows, Operations Research, 26, 209236. [22] H. Nagamochi, 1988. Studies on Multicommodity Flows in Directed Networks, Ph.D. Thesis, Kyoto University, Japan. [23] H. Nagamochi and T. lbaraki, 1989. MaxFlow MinCut Theorem for the Multicommodity Flows in Certain Planar Directed Networks, Electronics and Communications in Japan, Part 3, 72:3, 5871. [24] H. Nagamochi and T. lbaraki, 1989. On MaxFlow MinCut and Inte gral Flow Properties for Multicommodity Flows in Directed Networks, Information Processing Letters, 31, 279285. [25] H. Nagamochi, M. Fukushima, and T. Ibaraki, 1990. Relaxation Methods for the Strictly Convex Multicommodity Flow Problem with Capacity Constraints on Individual Commodities, Networks 20, 409426. 60
PAGE 65
[26] T. Nishizeki and N. Chiba, 1988. Planar Graphs: Theory and Algorithms, Annals of Discrete Mathematics1 32, NorthHolland, Amster dam. [27] H. Okamura, 1983. Multicommodity Flows in Graphs, Discrete Applied Mathematics, 5562. [28] H. Okamura and P. D. Seymour, 1981. Multicommodity Flows in Planar Graphs, Journal of Combinatorial Theory1 Series B1 31, 7581. [29] D. T. Phillips and A. GarciaDiaz, 1981. Fundamentals of Network Analysis, PrenticeHall, Inc., EnglewoodCliffs, NJ. [30] S. Rajagopalan, 1994. Two Commodity Flows, Operations Research Letters 15, 151156. [31] B. Rothschild and A. Whinston, 1966. On Two Commodity Network Flows, Operations Research 14:3, 377387. [32] B. Rothschild and A. Whinston, 1966. Feasibility of Two Commodity Network Flows, Operations Research 14:6, 11211129. [33] M. Sakarovitch, 1973. Two Commodity Network Flows and Linear Programming, Mathematical Programming 4, 120. [34] R. Schneur, 1991. Scaling Algorithms for Multicommodity Flow Prob lems and Network Flow Problems with Side Constraints, Ph.D. Thesis, Massachusetts Institute of Technology. [35] A. Sebo, 1987. Dual Integrality and Multicommodity Flows, in Infinite and Finite Sets1 Proceeding of a Conference held in Eger1 North Holland1 July 1987 (A. Hajnal and V. T. Sos, eds. ), 453469. [36] A. Sebo, 1993. Integer Plane Multiflows with a Fixed Number of Demands, Journal of Combinatorial Theory1 B1 59:2, 163171. [37] P. D. Seymour, 1980. FourTerminus Flows, Networks 10, 7986. [38] P. D. Seymour, 1981. Matroids and Multicommodity Flows, European Journal of Combinatorics 2, 257290. [39] P. D. Seymour, 1981. On Odd Cuts and Plane Multicommodity Flows, Proceedings of the London Mathematical Society (3) 42, 178192. 61
PAGE 66
[40] V. I. Shevchik, 1993. Multicommodity Flow Problem, Journal of So viet Mathematics, 6/1/93, 14621464. [41] H. Soroush and P. B. Mirchandi, 1990. The Stochastic Multicommod ity Flow Problem, Networks 20, 121155. [42] J. A.Tomlin, 1966. MinimumCost Multicommodity Network Flows, Operations Research 14:1, 4551. [43] S. W. Wallace and R. J.B. Wets, 1989. Preprocessing in Stochastic Programming: The Case of Uncapacitated Networks, ORSA Journal on Computing 1:4, 252270. [44] S. W. Wallace and R. J.B. Wets, 1993. Preprocessing in Stochastic Programming: The Case of Capacitated Networks, ORSA Journal on Computing (to appear). [45] S. W. Wallace and R. J.B. Wets, 1993. The Facets of the Polyhe dral Set Determined by the GaleHoffman Inequalities, Mathematical Programming 62, 215222. [46] R. D. Wollmer, 1972. Multicommodity Networks with Resource Con straints : The Generalized Multicommodity Flow Problem, Networks 1, 245263. 62
