SINGLY-CONSTRAINED MONOTROPIC NETWORK FLOW PROBLEMS: A LINEAR TIME TRANSFORMATION TO UNCONSTRAINED PROBLEMS AND QUALITATIVE SENSITIVITY ANALYSIS By ANTOINE GAUTIER Ingenieur Diplome de l'Ecole Centrale des Arts et Manufactures Paris, France. Promotion 1984 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in THE FACULTY OF GRADUATE STUDIES COMMERCE AND BUSINESS ADMINISTRATION We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA November 1990 © ANTOINE GAUTIER, 1990 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Commerce and Business Administration The University of British Columbia 6224 Agricultural Road Vancouver, Canada V6T 1W5 Date: Abstract This thesis examines several problems related to singly-constrained Monotropic Network Flow Problems. In the first part, a linear time algorithm that reduces the solution of a monotropic network Sow problem with an additional linear equality constraint to the solution of lower dimensional subproblems is presented. Of the subproblems, at most one is a singly-constrained monotropic network flow problem while the others are unconstrained. If none of the subproblems is constrained, the algorithm provides a linear-time transformation of constrained to unconstrained monotropic network flow problems. Extensions to nonlinear and inequality constraints are given. In the second part the qualitative theory of sensitivity analysis for Unconstrained Minimum-Cost Flow Problems presented by Granot and Veinott [GV85] is extended to Minimum-Cost Flow Problems with one additional linear constraint. The departure from the unconstrained network structure is shown to have a profound effect on computational issues. Two natu-ral extensions of the "less-dependent-on" partial ordering of the arcs given in [GV85] are presented. One is decidable in linear time while the other yields more information but is NP-complete in general. The Ripple Theorem gives upper bounds on the absolute value of optimal-flow variations as a function of variations in the problem parameter. Moreover, it shows how changes may "ripple down" throughout the network, decreasing in magnitude as one gets "further away" from the arc whose parameter initiated the change. The Theory of Substitutes and Complements presents necessary and sufficient conditions for optimal-flow changes to consistently have the same (or the opposite) sign in two given arcs. The complex-ity of determining Substitutes and Complements is shown to be NP-complete in general. However, for all intractable problems, families of cases arise from easily recognizable graph structures and can be computed in linear time. The Monotonicity Theory links the changes in the value of the parameters to the change in the optimal arc-flows. Bounds on the rates ii of changes are discussed. We further provide a number of practical situations where our theory may apply. We discuss some Multi-Period Multi-Product Inventory-Production models that can be formu-lated as nonlinear parametric network flow problems with one additional linear constraint. We then apply our theory to help decision makers understand qualitatively how to respond to changes in the environment such as machine breakdown, strike or variations in inven-tory carrying costs without additional computation. In a second example, we show how a Cash-Flow Management model can be formulated as a nonlinear parametric network flow problem with one additional linear constraint. The theory is then recommended as a method by which a decision maker could understand qualitatively how to respond to changes in the environment such as variations in interest rates, taxes or asset prices without any additional computation. iii Table of Contents Abstract ii List of Tables vii List of Figures viii Acknowledgement x I Foundations xii 1 Introduction 1 1.1 The Singly-Constrained Monotropic Network Flow Problem . . . . 1 1.2 Substitutes, complements and Ripples 4 1.3 Applications 5 1.4 Organization 6 2 Notation and Definitions 10 II Singly—Constrained Network Flow Problems 14 3 Transformation to an Unconstrained Network Flow Problem 15 3.1 Preliminary remarks 15 3.2 Tucker Representation and Elementary Vectors of C(a) 16 3.3 Dependency and Graph Decomposition 20 3.4 Decomposition Into Independent Monotropic Network Flow Problems 43 3.5 Extensions and Remarks 56 iv 4 Ripples, Complements and Substitutes 59 4.1 Introduction 59 4.2 The Ripple Theorem For Constrained Graphs 61 4.2.1 Less-Dependent-On Relation 63 4.2.2 Quantitative Less-Dependent-On Relation 68 4.2.3 The Ripple Theorem 69 4.2.4 Computing the Bounds in the Ripple Theorem 73 4.2.5 Complexity Issues Attached to the Qualitative Less-dependent-on Relation 78 4.3 Complements and Substitutes in Constrained Network Flows . . . . 81 4.4 The Monotonicity Theory 90 4.4.1 The Smoothing Theorem 94 4.4.2 Subadditivity of Minimum Cost in the Parameters 97 III Applications 99 5 A Constrained Inventory—Production Model 100 5.1 Introduction 100 5.2 The Multi-Product Multi-Period Model 101 5.3 Substitutes and Complements in The General Case 105 5.3.1 Pairs of Arcs Corresponding to the Same Product 106 5.3.2 Pairs of Arcs Corresponding to Two Different Products . . . 112 5.3.3 Computational Complexity , 114 5.4 Narrow constraints and pseudo—rims 118 5.4.1 Pseudo—rims and their properties 118 5.4.2 Application to Narrow Constraints 122 5.4.3 Recognition of pseudo-rims 127 5.5 First Period Constraints 127 v 5.5.1 Dependency 128 5.5.2 Positive Arcs, Complements and Substitutes 129 5.5.3 Less-dependent—on Relations 130 5.5.4 Variations in production capacity and inventory holding cost 132 6 A Cash-Flow Asset Allocation Management Model 137 6.1 A Cash-flow Management Model 137 6.2 Properties of the Graph G SCF 1 4 1 6.3 Qualitative Sensitivity Analysis 144 A index 147 Bibliography 152 vi List of Tables 5.1 Complements and Substitutes in the Unconstrained 105 5.2 Substitutes and Complements: Computations 115 5.3 Substitutes and Complements, / = 1 or 2 116 5.4 Substitutes and Complements: across products 1 and 2 116 5.5 Substitutes and Complements (J = 1,••• ,p) 124 5.6 Substitutes and Complements 126 5.7 First Period Example: 130 6.8 Table Signs of Respective Elementary Vector Entries 143 6.9 Substitutes and Complements in the Cash-flow Problem 143 6.10 Coefficients of the Ripple Theorem 144 vii List of Figures 3.1 Decomposition of the graph G 28 3.2 Rims and'Graphs 30 3.3 A one-rim (left) and its expanded version (right) 35 3.4 A palm graph with its branches 38 3.5 The coloring of the palm graph G 39 3.6 R i m Decomposition and Expansion 46 3.7 R i m Expansion 50 3.8 The r im G 54 4.9 Equally dependent pairs of arcs need not disconnect the graph . . . 64 4.10 Construction of the dependent graph G when G^e*} is a r im . . . . 66 4.11 Construction of the dependent graph G when G\{ek} is not bicon-nected 67 4.12 =•] does not imply =) 69 4.13 Tight bounds in the Ripple Theorem 72 4.14 The extended graph G" 75 4.15 Only bold arcs verify a, ^ 0 77 4.16 e,- <J e* - 80 4.17 Substitutes and complements in a constrained graph 82 4.18 Substitutes and complements 87 4.19 The r im G (left) and the constructed graph T(G')(right) 88 4.20 Arcs with common nodes need not be substitutes or complements. 90 5.21 The basic Inventory-Production Network 103 5.22 A Pseudo-Rim 119 viii 5.23 Projection of elementary vectors in pseudo-rims 121 5.24 A pseudo-rim with four pseudo—components: 123 5.25 The subgraph Gl is a r im with three r im components 128 5.26 Hasse Diagrams, e, = x\ 134 5.27 Hasse Diagrams, = y\ 136 6.28 The graph C G E N • 1 3 9 6.29 The graph G S C F • • - • • 1 4 0 ix Acknowledgement The longer one spends researching and writing a doctoral thesis, the more people one is lead to be thankful to at the end. Many are those who helped, one way or another, this long, enjoyable, and above all educational process. Thank you Frieda for bearing with me during the times of excitement, of discovery, of stalling and of learning. I feel deeply grateful for the patience, the guidance, and the wisdom to recognize where I was going when even I did not know. Grateful too for the many gallons of red ink patiently laid on dozens of successive drafts as, by osmosis, I absorbed some of the craft of academic writing. A special thanks to the staff here at the faculty of Commerce and Business Administra-tion, to Randy, Barbara who shared her printer and good humour, and Khim who smiled and witnessed my initiation to lATpjX. Also to my C290 Students who convinced me I was better suited for teaching than I previously thought, and made the experience fun and enjoyable. My thanks and love go to many of my friends in Vancouver who helped me see clearly, supported my spirits and helped me through the occasional doubt. For the music, thank you Lenka. Thanks to my good friends for helping balance the life of the aspiring Ph.D.; and to my surrogate parents, Don, Judy and June, aunts and uncles, who made my Thanksgivings and Christmases real family events. My recognition also goes to the people of Canada and.especially of Vancouver where I have felt more at home than anywhere else in the world, for keeping such a beautiful country and letting me be part of it. A special thanks to the Canadian Government and the World University Service of Canada for making it financially possible. Finalement, un grand Merci a ma famille, qui j'espere me pardonnera ma longue absence. Nul n'est prophete en son pays, mais est-ce bien une raison pour aller chercher le bonheur x si loin? Merci pour les nombreuses lettres, coups de telephone, et surtout le support qui se fait sentir par dela les mers et montagnes. xi Part I Foundations xii Chapter 1 Introduction 1.1 The Singly-Constrained Monotropic Network Flow Problem A Monotropic Programming Problem is an optimization problem in which the ob-jective function is variable-additive and the constraints are of the linear kind. In this work we discuss a special structured Monotropic Programming problem in which one is required to find a flow in a directed network that minimizes an arc-additive objective function, sub-ject to an additional linear constraint. This problem will be referred to as the Singly-Constrained Monotropic Network Flow Problem ( S C M F ) . To state SCMF explicitly, let G = (N, E) be a finite directed graph with a set of nodes N = {1,2, • • • , n} and a set of arcs E = {ei,e2, • • • ,em} (possibly with parallel arcs). Define the (node-arc) incidence matrix A = (A,j) >=i,-.» of G by Aij = 1 if node i is the head of arc (that is, e;- = for some I € N), A^ = -1 if i is its tail (ej = (i,£) for some t G N) and Axj = 0 otherwise. A demand vector (for G) is a real valued vector d £ 3£n for which £?=i = 0. For a given real-valued row-vector a 6 3?m and a real number ao € R we define the additional constraint ax = a 0 for x € 3£ m . With each arc e, £ E we associate a flow x,- 6 and a cost bj(xj) is incurred when the flow in arc ej is Xj, where bj(-) is a +co or real-valued function on 9t. The cost of a flow x = (ij) G 3ftm is the sum of the cost functions on all the arcs of the graph. SCMF can thus be written as P ( a , a 0 ) : Min Ylbi(xi) s.t. Ax = d ax — OLQ. 1 Chapter 1. Introduction 2 The usual non-negativity and upper/lower bound constraint(s), if any, are naturally incor-porated into the cost-function by setting bj(xj) equal to + 0 0 for all forbidden values of Xj. A problem similar to the above, but without the additional constraint, will be referred to as an Unconstrained Monotropic Network Flow Problem, or simply an unconstrained problem. SCMF is an important problem involved in many practical applications. It will occur, for example, within the framework of bicriterion decision analysis [Ba89], where a decision maker may be faced with optimizing a network flow over two criteria, say, for example, cost and project duration, where one of these criteria is a linear function of the arc-flows. In that case, a parametric analysis will optimize one criterion subject to a constraint on the other. Klingman [K177] gave an example of a newspaper distribution problem where the average delivery time is constrained, again resulting in a linear side constraint. Other examples include network flow problems with budget or resource constraints. The solution of the Minimum Convex-Cost Dynamic Network Flow Problem [Or82] involves solving a SCMF, which is the computational bottleneck of a strongly polynomial algorithm. The SCMF is also used by Spalti and Liebling [SL89] as a subroutine to solve a location problem for telecommunication satellites. The special case where no additional constraint is imposed has received considerable attention in the literature. Efficient solution techniques for problems with linear objective functions are too numerous to be surveyed here, while for nonlinear costs-one can see for example [Bert76,HK77,DK81,Ro84]. The majority of these algorithms exploit the particular structure of the constraint matrix and the combinatorial properties of network flows and circulations. However, the additional linear constraint partially destroys the attractive fea-tures of pure network flow problems. Even though, for linear objective functions, specialized solution methods may be used, see for example [CS77,GKKR78,BMM88], in the general case of non-linear arc-additive costs, one has to resort to solving a monotropic program (see [Ro84] for references), that is, treat the constraint matrix as not having any particular (combinatorial) properties. Chapter 1. Introduction 3 The question of whether the linearly constrained monotropic network flow problem is equivalent to an unconstrained monotropic network flow problem is therefore of interest, both from a practical and from a theoretical point of view. From a practical standpoint, network flow problems are easier to solve and can take advantage of proven efficient optimization codes. From a theoretical one, it is of interest to recognize a family of constrained problems which, although not in an obvious fashion, possess the desirable combinatorial properties of network flow problems. In the same spirit, a number of authors have looked for imbedded network structures in linear programs (see e.g. Bixby and Cunningham [BC80], Cunningham [Cu83] and Truemper [Tr83]). For linear network flow problems with a specific class of constraints, an answer was given by Klingman in [K177], where a procedure determines if the additional constraint is equivalent to a partial sum of flows on arcs all directed into or all directed away from a single node. If so, the topology of the network is modified in order to obtain an equivalent problem where one can drop the additional constraint (it will be shown that the procedure presented here covers these cases and is computationaly faster). However, in the event of a negative answer, it will be relevant to obtain the "smallest non-transformable" subproblem which, together with other subproblems transformed to unconstrained network flow problems, will solve the original SCMF. Computationaly, such a decomposition has the double advantage of both reducing the size of the "hard" (constrained) problem to a minimum, and of breaking down the original problem into more manageable subproblems. 1.2 Substitutes, complements and Ripples • In economics, the study of substitutes and complements has a long history, including works by Hicks and Allen [HA34], Hicks [Hi39], Samuelson [Sa47,Sa74], Lancaster [La62, La65,La66], and Gorman [Go64]. Samuelson [Sa47] poses the problem of whether it is pos-sible to predict the direction of change of certain variables in an economic model given the direction of change in some other variable(s). A first approach to this problem used Chapter 1. Introduction 4 the concept of qualitative determinacy where only the signs of the effect of one vari-able on another (Boolean variables) are taken into account. For example, one would use the information that "an increase in paper prices will increase paper recycling activities", combining it with "an increase in paper recycling activities will create employment" in a fashion reminiscent of artificial intelligence inference. In that framework, Lady [La67] first offered a solution to the problem posed by Samuelson, together with an algorithm based on graph theory to determine qualitative determinacy in economic systems. More results exploiting the structures of qualitative matrices of boolean "influence" between variables in an economic system stemmed from the works of Lancaster [La62,La65], Quirk and Ruppert [QR65], Maybee and Quirk [MQ69]. May [Ma73] developed the mathematics of such ma-trices. Refinements and extensions were provided by Greenberg [Gr81] for matricial forms where the concepts of determinacy and economic correlation were introduced (Greenberg's concept of connectivity is very close to our dependency), opening avenues for further the-oretical research by Greenberg, Lundgren and Maybee [GLM83,GLM84a,GLM84b]. More recently, the limitations of qualitative matrices which only partially describe inter-variable relation ("by how much does the increase in paper price affect recycling activity?") were removed as several authors studied linear programming-like systems. Provan [Pr83,Pr86] studies a general linear program and proposes to refine the concepts of substitutes and complements. The richness of the substitute and complement relations between variables is seen therein as a measure of organization of a system with interrelated factors. Provan and Kydes [PK80] further study determinacy in network models. Substitutes and comple-ments moved into the area of Network Flows with Shapley [Sh61,Sh62], and further with Veinott [Ve64,Ve65,Ve68] and Gale and Politof [GP81]. A rigorous theory of substitutes and complements for network flows, based partially on Topkis and Veinott's theory of Lattice Programming [Ve65,TV73,To78,Vefo.], was developed by Granot and Veinott [GV85]. The theory presented by Granot and Veinott explores many facets of sensitivity analysis, both qualitative and quantitative. An extension of that work to multicommodity flow problems was the topic of a doctoral dissertation by Ciurria [Ci89] under the supervision of Prof. Chapter 1. Introduction 5 Veinott (see also [CGV89a]). In [CGV89b], sensitivity analysis for multicommodity net-works transformable into regular (single-commodity) networks are studied. An application of that theory to multicommodity inventory-production models is given in [CGV89a]. Both the works of Granot and Veinott as well as that of Ciurria, Granot and Veinott rely on the combinatorial nature of (single commodity) network problems. As a byproduct of such structures, combinatorial, networklike algorithms are derived, keeping the complexity of an-swering most of Samuelson's questions in the class P with complexities which are linear to quadratic in the problem size. 1.3 Applications In the second part of this thesis, we provide illustrative examples of how our theory may be used to help managers make better decisions. We formulate a Multi-Period Multi-Product Inventory-Production model as a nonlinear parametric network flow problem with one additional linear constraint. We then apply our theory to help decision makers respond to changes in the economic and/or industrial environment such as machine breakdown, strike or variations in inventory carrying costs without additional computation. In a financial ap-plication, we show how a Cash-Flow Management model can be formulated as a nonlinear parametric network flow problem with one additional linear constraint. We then examine a number of scenarios and demonstrate how a decision maker could, using our theory, un-derstand qualitatively how to respond to changes in the environment such as variations in interest rates, taxes or asset prices without any additional computation. 1.4 Organization The following chapters are rather self-contained, each having its own introduction and set of definitions. The notation, as well as basic graph theoretic and network optimization terms are defined in Chapter 2. Further definitions and specific notation are introduced as needed Chapter 1. Introduction 6 throughout later chapters. In Chapter 3, we present a decomposition of the SCMF based on a decomposition of the underlying constrained graph1. The set of optimal solutions of the SCMF is shown to be the cartesian product of the sets of optimal solutions of a number of unconstrained monotropic network flow problems together with, possibly, a unique SCMF. The problem decomposition is based on a partition of the underlying constrained graph. Elementary vectors and their properties [Ro67] are the core of our theory. They behave like "building blocks" that hold the circulation space together, so that two arcs or subgraphs with no common "building block" will be separated by the partitioning process. Although most of the decomposition procedure could be exposed without relying on them, they are introduced for two reasons. First, they provide a rigorous framework and show how the results first emerged. Moreover, they are the basis for a proof of the fact that the decomposition is, in some sense, exhaustive, so that all transformable problems are actually characterized and detected. Chapter 3 is organized as follows. In section 3.2 the algebraic foundations of the decompo-sition theory are laid with the study of the circulation space associated with the feasible set, and the characterization of its elementary vectors. Section 3.3 starts with the introduction of the dependence r e l a t i on and of the dependen t c o m p o n e n t s of a singly-constrained graph. A series of five results is needed in order to establish the Graph Decomposition Theo-rem (Theorem 6), and a special type of graph structure, the r i m , is introduced. The second half of the section provides a theoretical characterization of rims, explores their connections with palm-graph structures, and finally a linear time algorithm that recognizes rims is given (Algorithm I). The implications of the graph decomposition for the SCMF are discussed in section 3.4 where we present a problem decomposition theorem for rims (Theorem 18) which leads to a linear-time algorithm (Algorithm II) that performs the problem decomposition. Some extensions are discussed in Section 3.5. In Chapter 4 we study the qualitative sensitivity analysis and the theory of substitutes XA version of Chapter 3 has appeared as a TJ.B.C. working paper under the title "A Linear Transformation of a Singly-constrained to an Unconstrained Monotropic Network Flow Problem" [GG89]. Chapter 1. Introduction 7 and complements2 (terms defined in section 4.3). The study of the unconstrained case was the object of [GV85]. Here, however, the additional linear constraint partially destroys the attractive features and some of the results obtained for pure network flow problems. Indeed, even the complexity of solving the problem is considerably increased by the presence of the additional constraint (for the treatment of linear costs, see [CS77,GKKR78,BMM88]). The cost function is, for most results, required to be convex in the arc-flow, and may reflect real costs as well as upper and/or lower bounds. The sensitivity analysis is performed by modifying the parameter associated with one or several given arcs. Any variation of the "cost structure can be represented in this fashion. Our results are concerned with the "reactions" of the optimal flows to such changes. For applications, such parameter variations may, for example, reflect changes in upper and/or lower bounds, additive or multiplicative increases in cost, pricing alternatives, technological advances, discounts, or even simulate the deletion/addition of an arc. In the case of multiple optima, our results are valid for at least one of the possible optimal flows. The Chapter is organized as follows. Section 4.2 focuses on bounds on the magnitude of changes of the optimal flow in two given arcs, the main results being given in the Rip-ple Theorem (Theorem 21). To that end, we define two partial orders on the set of arcs, the less—dependent—on relation and the quant i tat ive ly- less—dependent—on relation, as well as a coefficient Mjk which is associated with each pair of arcs (ej, ejt). Computational issues associated with the partial orders and the coefficients Mjk are discussed. In section 4.3 we introduce the notions of complements and substitutes pairs of arcs and present a result on the direction of changes in the optimal arc-flow for such pairs of arcs ih Lemma 25. Com-putational complexity is again addressed. The Monotonicity Theory presented in section 4.4 relates and compares the rate of change in the optimal flow of a given arc to that of another arc's parameter when the two arcs are either complements or substitutes, a result stated in the Monotone Optimal-Flow Selection Theorem (Theorem 31). The Smoothing Theorem (Theorem 33) provides an upper bound on the maximum arc-flow change over the network 2 A version of Chapter 4 has appeared as a U.B.C. working paper under the title "Ripples, Complements and Substitutes in Singly-Constrained Monotropic Parametric Network Flow Problems" [GG90a]. Chapter 1. Introduction 8 in terms of £ i - n o r m of the corresponding parameter variation. Finally Theorem 34 shows a subadditivity property of the minimum cost. Chapter 5 deals with an inventory/production problem3. We show how to provide poly-nomial time solutions to sensitivity analysis questions for the special graphs associated with singly-constrained multi-product inventory-production problems. An extension of the con-cept of rims is proposed which gives sufficient conditions for the qualitative sensitivity ques-tions to be answerable in linear time for some subsets of arcs. This concept of pseudo—rim is applied for a class of singly-constrained multi-product inventory-production problems, and examples are given. Lastly, another class of such problems is studied and illustrates the concept of rims. The qualitative theory developed in Chapter 4 is then fully informative, and comprehensive predictions are made for examples in which variations in production capacity and inventory holding cost are studied. Chapter 6 illustrates the application of our model to a Cash-Flow Managements problem4. Indeed, many cash-flow management models can be represented as network flow problems with arc-gains or losses, see e.g. [M84,GG90b]. In this chapter we show how one such model can be transferred into an equivalent singly-constrained network flow problem. We then apply the qualitative theory in order to help decision makers respond to changes in their environment without having to perform any additional computations. For example, given an existing set of assets, the problem is to decide what would be the "best" distribution of the assets over the next planning period. The objective may be to maximize expected return, to minimize a (quadratic) risk function, or some combination of both. Given the special graph structure that emerges, all sensitivity analysis questions posed in Chapter 4 are answered in time linear in the number of assets, and the theory is fully informative. For example, we are able to give bounds on the rates of change of disinvestment and reinvestment for all 3 A version of Chapter 5 has appeared as a U.B.C. working paper under the title "A Parametric Analysis of a Constrained Nonlinear Inventory-Production Model" [GG90c]. 4 A version of Chapter 6 has appeared as a U.B.C. working paper under the title "A Parametric Analysis of a Nonlinear Cash-Flow Asset Allocation Management Model" [GG90b]. Chapter 1. Introduction 9 assets and, in some cases, predict directions of changes. Examples are given of increase in tax rates on asset sales and variations in expected rates of return on assets. • • • Chapter 2 Notation and Definitions In this chapter, we provide most of the notation and definitions used throughout this thesis. Further definitions, especially those original to this piece of work, will be introduced as required. Recall from Chapter 1 the problem formulation of the SCMF: Let G — (N, E) be a finite directed graph with a set of nodes N = {1,2, • • •, n} and a set of arcs E = {ei, e2, • • •, em} (possibly with parallel arcs). Define the (node-arc) incidence matrix A = (Aij) ; = i , - , n of G by A^ = 1 if node i is the head of arc ej (that is, ej = (£, i) for some £ G N), A,j = — 1 if i is its tail (ej = (i,£) for some £ G N) and A,j = 0 otherwise. A demand vector (for G) is a real valued vector d G 3ftn for which YZ=i «^ = 0. For a given real-valued row-vector a G 3ftm and a real number ao G 3ft we define the additional constraint ax = ao for x G 3ftm. With each arc e,- G E we associate a flow Xi G 3ft, and a cost bj(xj) is incurred when the flow in arc ej is Xj, where bj(-) is a -f-oo or real-valued function on 3ft. The cost of a flow x = (XJ) G 3ftm is the sum of the cost functions on all the arcs of the graph. The SCMF can be written as P(a,a0): Min i = i s.t. Ax = d . ax = Qo-A flow x = (XJ) G 3ftm is said to be feasible (with respect to a demand d) if Ax = d. The set of constrained flows is denoted by F(a , a 0 , d) = {x G 3ftm : x > 0, Ax = d,ax = a0}. The graph G = (N, E) together with the constraint ax = ao will be referred to as a constrained graph and denoted by (Ny E, a). A real-valued vector x G 3ftm is called a circulation (of G) 10 Chapter 2. Notation and Definitions 11 if Ax = 0, and a constrained circulation if it further verifies ax = 0. An arc e< is said to be neutral if a, = 0 and active if c*j ^ 0. We denote by C(a) = {x 6 5Rm : Ax = 0, ax = 0} space the linear subspace of circulations constrained by the vector a. The support of a given vector x G S m , denoted Supp(x), is the subset of indices i G {1,2,... ,m} for which i,- ^ 0. Given a linear subspace K of 9Jm, an elementary vector [Ro67] of K is a vector x € K whose support is minimal among the supports of nonzero vectors of K. An elementary support is the support of an elementary vector. An elementary circulation is a constrained circulation whose support is an elementary support, or equivalently an elementary vector of the constrained circulation space C(a). Any vector of K can be expressed as a conformal sum (two vectors u and v are conformal if U{Vi > 0 for all i) of elementary vectors of K [Ro67, pp. 108-109, Harmonious Superposition Theorem]. A simple path p in G is an ordered set of arcs in G for which there exists a set of nodes of G such that every node is shared by a unique pair of successive arcs with respect to the order. If in addition there is a node shared by only the first and the last arc in the ordered set obtained from p, then p is a simple cycle. A vector c = (c,) € {0,1,— l}m is called an oriented cycle if it is a circulation and Supp(c) is a simple cycle on G. If c is an oriented cycle, —c is the reversed oriented cycle of c. If Cj ^ 0, then c is said to contain arc e;-. If Cj = 1 (resp., —1) then e,- is a forward (resp., backward) arc of c. An oriented cycle c is said to be neutral (with respect to the constraint ax = a0) if ac — 0 and active if ac ^ 0. By extension a subgraph of G is active (resp., neutral) if it contains (resp., does not contain) active cycles. Moreover, an arc is a positive (resp., negative) arc if and only if every cycle c that contains it as a forward arc verifies ac > 0 (resp., < 0). A vector p E {0,1, —l}m is called an oriented path from node i to node j in G if by adding to E the arc e = (j, i) if it does not exist, the vector p + e possibly in the newly Chapter 2. Notation and Definitions 12 created graph, is an oriented cycle. Forward (resp., backward) arcs of p are forward (resp., backward) arcs of p + e. A graph G = (TV, E) is said to be connec ted if and only if there exists at least one simple path between any two nodes of G, and fc-connected for k > 2 if and only if there exists at least k internally node-disjoint paths between any two nodes of G. In particular a graph is 2—connected or b i connec t ed if and only if every pair of distinct arcs is contained ih a simple cycle [Wh32, p. 347] and by extension we say that a graph with only one arc is biconnected. A vector z 6 {0,1,—l}m is a cu t of G if and only if G can be partitioned into two connected subgraphs G\ = (Ni, E\) and G2 = (N2, E2), with Ni U N2 = N and Ni f\N2 = 0, so that Zj = 1 (resp., —1) if ej = (ii, i2) (resp., (i2, h)) with ii £ Ni and i2 £ N2, and Zj = 0 otherwise. It is a well known result that cuts and simple oriented cycles are orthogonal (see e.g. [Ro84, pp. 115-117]). A subgraph GT = {N, T) of G is a s p a n n i n g forest of G if it contains all the nodes of G but no cycles, and a s p a n n i n g t ree if, in addition, GT is connected. If a spanning tree GT is directed so that one of its nodes, say 1, is not the head of any arc and the unique oriented path p(i) from node 1 to node i in GT only has forward arcs then GT is called a d i r e c t e d s p a n n i n g t ree and node 1 its r oo t . The nodes of p(i) are then the ancestors of i and i is their descendant . D(i) denotes the set of descendants of node i and we may assume without loss of generality that i > j whenever i is a descendant of j. If all the arcs in E\T are oriented from a node to one of its ancestors, then G is called a p a l m g raph , T its u n d e r l y i n g t ree , and the arcs in E\T are the r e t u r n arcs while the arcs in T are the t ree arcs . It was shown by [Ta72] that by using depth-first search any connected undirected graph can be converted into a palm graph by redirecting its arcs in a suitable manner and renumbering the nodes appropriately. This can be done in linear time, see for example [Ta72,AHU74]. In a similar fashion any connected directed constrained graph can be converted into a c ons t r a i ned p a l m g r a p h if by redirecting an arc we mean reversing its orientation and multiplying the corresponding a, by —1. We will denote by /( i ) , i / 1, the Chapter 2. Notation and Definitions 13 father of node t, that is, the unique node such that ( / ( t ) , t ) € T , and p(i, j) = p(j) — p(i) is the unique path on T from i to j. We will further associate with each node i a label of = ap(i). Let GT = (N, T) be a spanning forest in G, and tj an arc in E\T'. Then there exists a unique oriented cycle in G orienting ej as a forward arc and whose remaining arcs belong to T. This unique .cycle will be denoted by c(ej,Gr)- One can further verify that if G is a palm graph and ej = (i,k) then c(ej,Gr) = p(k, i) + ej = p(i) — p(k) + ej and thus ac(ej, T) = ap(i) — ap(k) + atj — aj — a* + otj. If c(ej, GT) is an active oriented cycle with respect to a, then GrUfej} = (N, Tl){ej}) is called an a—one—forest (on G). In general, a subgraph S of G is an a-one-forest if and only if it can be constructed in the above manner. We show in Lemma 2 that if a is not a linear combination of rows of A, then there exists at least one a-one-forest. In the discussions of computational complexity, we will use the term problem to desig-nate all possible instances of a given question. A decision problem is one whose answer is either "Yes" or "no", an evaluation problem is that of finding the optimal value of an optimization problem, but not necessarily the corresponding optimal decision variables. We will assume that the data is rational and denote by s the size of an instance, that is, the number of bits of information required to encode the given instance. Typically, if the data is integer (this is a valid assumption, for rational data can, without loss of generality, be appropriately scaled), the space required to encode G = (N, E, a) together with the demand vector d is n m s = 0(mlog2n + £ l o g 2 ( | 4 | + 1) + £ log2(\aj\ + 1))'. t=i j=i. • • • Part II Singly-Constrained Network Flow Problems 14 Chapter 3 Transformation to an Unconstrained Network Flow Problem Chapter Abstract A linear time algorithm that reduces the solution of a monotropic network flow problem with an additional linear equality constraint to the solution of lower dimensional subproblems is presented. Of the subproblems, at most one is a singly-constrained monotropic network flow problem while the others are unconstrained. If none of the subproblems is constrained, the algorithm provides a linear-time transformation of constrained to unconstrained monotropic network flow problems. Extensions to nonlinear and inequality constraints are given. • • • 3.1 Preliminary remarks In this chapter, we study the Nonparametric Singly-Constrained Monotropic Network Flow Problem, the S C M F . This problem can be written as m P(a,a0): Min Ylbi(xi) s.t. Ax = d • OCX = Qo. A problem similar to the above, but without the additional constraint, will be referred to as an Unconstrained Monotropic Network Flow Problem, or simply as an uncon-strained problem. Notice that if x1 and x2 are feasible, possibly optimal, for P(a, ao), then the difference x1 — x 2 belongs to the circulation space C(a) = {i£ 3?m : Ax = 0, ax = 0}. This remark motivates the development of the representation of C(a) in section 3.2. 15 Chapter 3. Transformation to an Unconstrained Network Flow Problem 16 3.2 Tucker Representation and Elementary Vectors of C(a) In this section we study some characteristics of the subspace C(a) which will then be used in the development of the decomposition algorithm To that end we will assume without loss of generality that all leaf arcs through which no circulation passes were discarded from the outset (this can be done in 0(n) operations). Indeed such arcs are of little interest as far as the optimization problem is concerned, for any flow that is feasible for P(a, ao) has a fixed value on them. Let F E 3? r X ? be a matrix with r rows and q columns and consider the linear subspace of 3^ defined by K(F) = {x € 3^ : Fx = 0}. We will assume without loss of generality that F = (FB,FN), where FB is nonsingular, is of full row rank, so that (FB)~1F = (I,F) and F — (fij), i = 1, • • • , r , j = r + 1, • • •, q. We refer to (J, F) as a Tucker representation of K(F) [Tuc63,Ro84]. The variables x i , . . . , x r are called the basic variables while the variables x r called the nonbasic variables for this particular Tucker represen-tation. Clearly, for any given value x r + i , . . . , xq of the nonbasic variables, the basic variables x j , . . . , x r of a vector x € K(F) will be uniquely determined by the system of equalities = E'=r+i fijXj for i = 1,2,..., r. The set B of column vectors of F corresponding to the basic variables is called the basis for the Tucker representation of K(F). The next four results provide a characterization of these bases. Note that we may assume in the following that the side constraint ax = ao is not redundant, that is, that a £ K(A) • L E M M A 1 [Ro84, p. 456]. Let F € 3? r x« then a subset B of columns of F is a basis for some Tucker representation of K(F) if and only if it is a basis (in the usual sense of linear algebra) for the subspace spanned by the columns of F, that is for B(F) d= {y e £ r : 3 x € ft« with Fx = y}. Chapter 3. Transformation to an Unconstrained Network Flow Problem 17 L E M M A 2 Let G = (N, E, a) be a constrained graph and A its node-arc incidence ma-trix. If a £ K(A) then all the a-one-forests of G exist and are the bases for the Tucker representation ofC(a). P R O O F . First, since a ^ K(A), then G contains at least one active cycle. Such an active cycle may be completed into an a-one-forest by adding appropriate arcs. Now, let GT = {N, T) be a spanning forest in G and e* an arc in E\T so that T U {e^ } is an a-one-forest. We will assume without loss of generality that T = {ei, e2, • • •, e„_i} and that k = n. Now, since T is a basis for the system of n linear equations Ax = 0, see for example [Ro84], there exists a series of linear operations which, when applied to the rows of the matrix Aa, fl.A'\ obtained by replacing the last row of A by a, will result with a matrix A'a = I 0 : a J where / is an (n — 1) x (n — 1) identity matrix, A' = (a,j) where a,j = — c(ej, GT){, with c(ej, (7T),-denoting the ith component of c(ej, GT) and ctj = ctj — YX=i <*iaij-Note that a, = ctj + YAZI Qi c(ej,Gr)i = ac(ej,Gr) for all j = n , . . . , m and, since GT U {en} is an a-one-forest, d n ^ 0. Now by adding to each row i of A'Q row n divided by an and multiplied by — a, n one obtains the matrix A"a = (I: Aa) where / is an n x n identity matrix, and Aa = (a,j) with a' a,j = a 0 - -~-ain t' = l , . . . , n - l , j = n + 1,..., m (3.1) anj = — j = n + l , . . . , m . -Now A'}, is a Tucker representation for C(a) whose corresponding basis is the a-one-forest. • The origins of Lemma 3 to follow can be traced back to [GKKR78] in which a similar result is used, although not explicitly stated or proved. We include a proof for completeness. L E M M A 3 If <* £ K{A), then all bases for the Tucker representation of C(a) are a-one-forests containing an active cycle. Chapter 3. Transformation to an Unconstrained Network Flow Problem 18 P R O O F . We first show that any basis contains no more than one cycle. Assume, on the contrary that there exists a basis B C E for the Tucker representation of C(a) which contains two different simple cycles, say C 1 and C2 (which differ by more than their orientation). Further let c1 (resp., c2) be an oriented cycle corresponding to C 1 (resp., C 2 ) . If c1 is a neutral cycle, then A A — Ac 1 0 a c = ac 1 0 is a linear combination of the rows of Aa that are in B and whose coefficients are the entries of c1, and thus not all equal to zero. Therefore B is not a basis for the linear subspace B(E,a)d^ {t/G & n + 1 : 3x G 3im with y = Aax) and by Lemma 1 not a basis for the Tucker representation of C(a). Clearly the same holds if c2 is a neutral cycle. Let us assume now that both cycles are active. Then similarly A [{ac2)cl - (ac^c2} = (ac 2)Ac 1 — (acl)Ac2 0 a (ac 2)ac x — (ac 1)ac 2 0 is a linear combination of rows of Aa that are in B and whose coefficients are the corre-sponding entries of (ac 2)c 1 — (ac 1)c 2, and thus not all equal to zero. A contradiction arises as in the previous case. This proves that any basis contains no neutral cycle and no more than one active cycle. In Lemma 2 we showed the existence of a basis with cardinality equal to n. (This is always possible since we assume the existence of an a-one-forest). Hence all bases have cardinality equal to n and no more than one cycle, and therefore can be written as B = GT U {ej} where GT = (N,T) is a spanning forest with ej € E\T, and B contains a unique cycle C(CJ,GT) which is active. • Combining Lemmas 2 and 3 one obtains Chapter 3. Transformation to an Unconstrained Network Flow Problem 19 THEOREM 4 The bases for the Tucker representation of the subspace C(a) are the a-one-forests. • In order to characterize the elementary vectors of the subspace C(a) which play a major role in our algorithm we will describe the General Basis Theorem given by Rockafellar, and its specialization to our content. For further details the reader is referred to [Ro84, p. 457]. To that end, let 6 be a basis for some Tucker representation of C(a) and let a;j, e,- € B, ej 6 E\B, be the coefficients in that representation. The General Basis Theorem states that for -each ej £ E\B there exists a unique elementary vector ft whose support contains ej positively (that is, fj = 1) and otherwise only elements of B. The corresponding elementary vectors ft form an algebraic basis for C(a) and are determined by -akj k E B 1 k = j 0 otherwise. The subset of C(a) given by {/J : j £ E\B} is called the fundamental basis associated with B. Furthermore, any elementary vector is part of at least one such fundamental basis. Hence we may, by the following construction, obtain all of them. Let B — GT U {en} be any a-one-forest, and recall from Lemma 2 that (d,j) are the entries of the Tucker representation of C(a) corresponding to the basis B and that (a,j) are the entries of A' (recall that A' = (a;j) and a,j = — c(ej, GT)«)- Now, we can use (3.1) and the expression of fl to write ft = - X) akjek + ej = ~ $3 °*ic* ~ <*njGn + ej = - £ akjei, + ej+ £ ^r-aknek - ?r-en (3.2) = c ( e j , G T ) - ? i c ( e n , G r ) . a n Chapter 3. Transformation to an Unconstrained Network Flow Problem 20 Therefore, / J is either a neutral oriented cycle (if ctj = 0), or a weighted sum of two active oriented cycles, in which the weights are determined, up to a multiplicative factor, by the equation a/-7 = 0. Observe further that any elementary vector thus constructed will fall into one of the following categories. (i) / = c and c is a simple neutral cycle satisfying ctj = 0 in (3.2) for some basis B. (ii) / is of the form / = c1 - (ox7ac2)c2 (3.3) with ac 1 ^ 0 and ac 2 ^ 0. In this situation several cases may occur (ii-a) c1 and c? are two disjoint active cycles (ii-b) c1 and c2 are two simple active cycles intersecting on a single node or on a path. (ii-c) c1 and c2 are two simple active cycles whose intersection includes more than either a single node or a path. One can see that such a situation would create more than three cycles in Supp(f) — not a minimal support — and therefore / could not be derived in the fashion described in the General Basis Theorem. Thus this situation does not lead to an elementary vector of C(or). Furthermore, any vector / belonging to either of the categories (i), (ii-a) or (ii-b) can be constructed in a fashion described above. Thus we have the following theorem. T H E O R E M 5 The family of vectors H(a) for which either (i), (ii-a) or (ii-b) holds is the family of elementary vectors of C(a). • * 3.3 Dependency and Graph Decomposition We start this section by defining a dependence relation between arcs in a constrained graph which will lead to a decomposition of the constrained monotropic network flow problem into subproblems of lower dimensions. Chapter 3. Transformation to an Unconstrained Network Flow Problem 21 Let G = (N, E, a) be a constrained graph. We say that two arcs e,- and tj in G are dependen t if and only if there exists an elementary vector / = (/*) £ H{<x) for which fifj 7^ 0. It can be seen that the dependence relation is an equivalence relation. Indeed, the set of elementary vectors of the circulation space forms a matroid [Ro67]. Therefore, given three arcs e,-, ej and ejt, if there exists two elementary vectors f1 and / * that respectively contain e,- and ej, and ej and e*, then there exists an elementary vector / 3 that contains e, and ejfc. A constrained graph G = (A7, E, a) is said to be dependen t if and only if every pair of arcs in E is dependent. A dependen t c o m p o n e n t of G is a maximal dependent subgraph of G or, equivalently, a subgraph of G whose set of arcs is an equivalence class for the dependence relation. We now look into the problem of decomposing a constrained graph G = (N, E, a) into dependent components. To that end, recall that a graph G = (N, E) is b i connec t ed if and only G is connected and either E is a singleton or for any pair of arcs in E there exists a simple cycle containing both arcs. A b i connec t ed c o m p o n e n t of a graph is a maximal biconnected subgraph, and Whitney [Wh32] showed that a graph can be decomposed into biconnected components in a unique fashion. Two biconnected components have at most one node in common (see e.g. [Tut66, pp. 90-92]), and the decomposition of a graph into biconnected components can be done in linear time as described, for example, in [Pa71], [Ta72] and [HT73]. We show how the decomposition procedure into biconnected components can be used to decompose a constrained graph into dependent components. We begin by decomposing G into, say, £ biconnected components GT = (Nr, Er,ar), r = 1, • • • , £ where ar is naturally obtained by keeping in a the entries corresponding to arcs in ET. Then for each biconnected component we test whether GT contains at least one active cycle. We will assume without loss of generality that for some 1 < p0 < £, G\,--- ,GPo each contain at least one active cycle, and that G>„+i, • • • ,Gi contain no active cycle. THEOREM 6 Let G\, • • •, GPQ,GPo+i, • • •, Gt be defined as above, and define the graph G* = (N*,E*) = Gx U G2... U G P 0 . If p0 > 2 then G*, GPo+1, • • •, Gt are the dependent Chapter 3. Transformation to an Unconstrained Network Flow Problem 22 components of G. If po = 1 there exists a partition of Gi into Q > 1 subgraphs Gq = (N*,E*,cfl), q = l,...,Q, Ei =U?=i^ ?, EqnE"' = 0 whenever q ^ q' and |7Y« n 7Y»'| = 2 for q ^ q', such that Gi,..., Gq^G^x — G2, • • •, Gt are the dependent components of G. Moreover if po = 1 and Q > 2 the dependent components of G\ are biconnected subgraphs that form a r i m (a term which is defined later) and none of them contain any active cycle. The proof of Theorem 6 requires the following four Lemmas. L E M M A 7 Let G =• (N,E,a) be a constrained biconnected graph. If there exists an active cycle in G, then for each arc ej in G there exists an active cycle containing e,. P R O O F . Let c° be an active cycle in G and e, an arc in E. If e, is in c° the proof is complete, otherwise let ej be any arc in c°. Since G is biconnected there exists a simple cycle, say c1, that contains both e,- and e;. If ac 1 ^ 0 then c1 is the required active cycle containing e, and the proof is complete. Otherwise, let the oriented path p which contains e, as a forward arc be the part of c 1 whose first and last nodes, namely ni and n2, belong to c°, but which has no other nodes in c°. Let the oriented path p' (resp., p") be the part of c° that lies between nx and n2 and contains (resp., does not contain) ej, oriented from n 2 to n\. Consider the two cycles c 2 = p + p' and c 3 = p + p", both oriented so that c2 = cf = 1. Clearly c 2 — c 3 = p' — p" = ± c ° , therefore ac2 — ac3 = ±ac° ^ 0, which implies ac 2 ^ ac3. Now, since both c2 and c 3 contain e,- and either ac2 ^ 0 or ac3 ^ 0 the proof follows. • L E M M A 8 Let G = (iV, E, a) be a biconnected constrained graph, and suppose that G can be written as the union of two constrained graphs Gi = (N1, JE^a 1) and G2 = (N 2,E2,a2) where E l 0 E2 = 0, E l U E2 = E. Moreover suppose that G\ is dependent and contains at least one active cycle. Then G\ and G2 are dependent. Chapter 3. Transformation to an Unconstrained Network Flow Problem 23 PROOF. We start by proving that for any given arc e, in G2 there exists an arc in G\ such that this arc and e; are dependent. The remainder of the proof follows from the fact that G\ is dependent and the transitivity of the dependence relation. In order to do this we will exhibit an elementary vector with nonzero entries both on e,- and on some arc in G\. Let c° be any active cycle of G\ and ej be any arc in c°. Since G is biconnected there exists a cycle, say c 1, such that c}c] ^ 0. If c 1 is a neutral cycle, that is, ac 1 = 0, then c1 is an elementary vector of H(a), e,- and ej are dependent, completing the proof. Let us assume on the contrary that c 1 is an active cycle and define the simple cycles c 2 and c 3 in a similar manner as it was done in the proof of Lemma 7. If ac2 = 0 (resp., ac 3 = 0) then c2 (resp., c3) is an elementary vector that contains e, and at least one arc in Gi, and the proof follows. Otherwise both ac 2 ^ 0 and ac3 ^ 0, and since c 2 and c 3 intersect on the simple path p (defined in the proof of Lemma 7) then / = c2 — (ac2 / ac3)^ is an elementary vector of H(a) that contains all the arcs of c°. Moreover, since / , = c2 — (ac2 / ac3)c3 = 1 — ac2/ac3 ^ 0 for we showed in Lemma 7 that ac2 ^ ac 3 , / is the required elementary vector and the proof is completed. • L E M M A 9 Suppose that a biconnected constrained graph G = (N, E, a) has several dependent components Gq = (Nq,Eq,a9),q = 1 , . . . , Q with Q > 2. Then no depen-dent component contains any active cycle, and \A(q)\ = 2 for any q = 1,...,Q where A(q) = N"n\Jm^Nm. PROOF. To show the first part of the Lemma, suppose that for some 1 < q < Q, Gq contains an active cycle. By applying Lemma 8 to the case where G\ is Gq and G2 is Um#? Gm one obtains that G\ is not independent of the rest of G, yielding a contradiction. To show the second part assume that the result does not hold and that, for example, |A(1)| > 3 (Clearly |A(1)| < 1 is impossible for, in a biconnected graph with more than one arc, all node-cuts have at least two elements). Since G is biconnected there exists a simple cycle that contains arcs both in Gi and in G = Um i^ G m . Moreover since A(l) is the node-cut between Gi and G, any such cycle contains at least two nodes in A(l ) . Chapter 3. Transformation to an Unconstrained Network Flow Problem 24 Let c be such a cycle and assume without loss of generality that the part of c in G is a simple path p that contains no other node of Gi than its end nodes, say ni and n2. Indeed if this does not hold let ej be any arc of G\ which is in p, n x (resp., n 2) the first node of A(l) (possibly an extremity of ej) encountered on p starting from ej forward (resp., backward) with respect to the orientation of c, and replace c by the portion of it that lies between ni and ri2 in G together with any path joining n\ to n 2 in G\ (such a path exists for G\ is connected). Since |A(1)| > 3 there exists a third node common to G\ and G, say n 3 , and since G is biconnected there exists a simple cycle, say c°, that uses two given arcs adjacent to n3, one in G\ and the other in G. Orient c° so its first arc after n 3 is in G, denote by n 4 the first node of A(l) encountered on c° starting from n 3 and by,p' the part of c° which lies in G between n 3 and n 4 . We first look at the case where n 4 ^ n l 5 n 2 and show that we can assume without loss of generality that p and p' have at most one node in common. Indeed if they do not, let n 5 (resp., n 6) be the first (resp., last) node of p' encountered on p when starting from n x (if necessary exchange the names of n 3 and n 4 so that n 5 is encountered on p' before when starting from n 3), then replace p (resp., p') by the part of p that joins n x to ns (resp., n2 to n 6) together with the part of p' that joins n 3 to n 5 (resp., n 4 to rie) and exchange n2 and n 3 . Define now two arc-disjoint paths p" and p'" in G\ that join respectively ni to n2 and n 3 to n 4 (To prove the existence of p" and p'" add to G i two arcs joining respectively ni to n 3 and n 2 to n 4 . Since Gi is still biconnected there exists a simple cycle of G\ that contains the two arcs, and removing these two arcs from the cycle results in p" and p"'). Further define the cycle c1 (resp., c2) obtained by joining p and p" (resp., p' and p'"). Both c1 and c2 are active for they have arcs in G\ and in G, and they meet in at most one node, thus c 1 — (etc1 / ctc2)^ is an elementary vector with arcs in G\ and in G, yielding a contradiction. We now look at the alternative case where one of ni or n 2 , say ni, is equal to n 4 . First, we show that we can assume without loss of generality that p and p' meet in at most a single node or a simple path. In order to see this, suppose on the contrary that this situation does Chapter 3. Transformation to an Unconstrained Network Flow Problem 25 not arise. Let n 5 be the first node of p encountered on j/ starting from n 3 (thus n5 ^ n{) and replace in p1 the portion between ns and r\\ by the corresponding portion in p, so that the two paths p and pf now possess the above property. Then define two arc-disjoint paths p" and p'" in Gi that join respectively ni to n2 and ni to 713 (the proof of their existence is similar to the proof of the existence of p" and p'" in the previous case, by introducing an arc between n2 and 713), and the cycles c 1 and c? as above. For similar reasons c1 and c? are active, and now meet in at most a single node or a simple path, thus c1 — (ac1 /ac^c 2 is an elementary vector, yielding a similar contradiction. • Lemma 10 to follow is based on the construction we present now. For a biconnected constrained graph G = (N, E, a) that is comprised of several dependent components, say Gq = (Nq,Eq,aq) for q = 1,..., Q > 2, we define the cycle graph G+ induced by G as follows. We will call bolts the nodes of N that are common to at least two dependent components of G and denote by N+ the set of bolts. Recall from Lemma 9 that each Gq has exactly 2 nodes in common with the other dependent components. For q = 1,..., Q we define the arc e+ = (i,j) where i and j are the two nodes common to Nq and Uq'^q Nq> as described in Lemma 9, and associate with it a scalar a+ = apq where pq is any oriented path in Gq from i to j. Moreover, if E+ = {e+ : q = 1,..., Q} and a + = (otg)q=i,...,Q, then the induced cycle graph is the constrained graph G+ — (N+, E+, a+). We will refer to G as a rim and to its biconnected components Gq, q = 1,..., Q as the rim components. L E M M A 10 Suppose that G = (N, E, a) is a biconnected constrained graph that is com-prised of several dependent components and let G+ = (N+,E+, a + ) be the cycle graph induced by G. Then a + is independent of the choice of the paths (p')?=i,...,<j and G+ is a simple active cycle. PROOF. To see that a+ does not depend on the choice of pq suppose that there exist two oriented paths in Gq, say, p and p' between the two nodes i, j G Nq fl N+ such that ap ^ ap'. Clearly p — pf is a circulation on Gq, and therefore a sum of simple cycles [Be73, Chapter 3. Transformation to an Unconstrained Network Flow Problem 26 pp. 90-91]. Since a(p — pf) ^ 0, then for at least one of those cycles, say c we have ac ^ 0, contradicting the fact that Gq contains no active cycles as was shown in Lemma 9. Clearly G+ cannot contain any simple neutral cycle, for otherwise such a cycle would correspond to a simple neutral cycle of G, that is, an elementary vector with arcs in several of the Gq,q = 1,...,Q, contradicting the fact that the latter are independent. Let us assume now that G+ contains at least two distinct active cycles, say c + 1 and c + 2 . Then the vector x = (ac + 2 )c + 1 — (ac + 1 ) c + 2 is a constrained circulation on G + since it verifies Ax = 0 and ax = 0, and therefore x is a sum of elementary vectors of G + . Let / + be any one of those elementary vectors. Since G + does not contain neutral cycles / + is the weighted sum of two active cycles in G+ that meet in at most a simple path or a single node, and the same holds for the vector / of G obtained by replacing every arc e+, q = 1,..., Q, in G + by pq. Therefore / is an elementary vector of G with non-zero components in several dependent components, leading to a contradiction. • COROLLARY 11 If a graph G = (N,E,a) is a rim, then any active cycle in G goes through all the bolts of G and through all of its rim components. PROOF. The main consequence of Lemma 10 is a result on the topology of rims. Such graphs are closed "chains" of biconnected subgraphs, each having a single node, a bolt, in common with each one of its two neighbours. Since none of these rim components contains an active cycle, any active cycle has to go through at least two rim components and thus, from the "closed chain" topology of the rim, through all rim components and all the bolts. • • PROOF OF THEOREM 6. Each subgraph GPo+u • • •, Gt is clearly dependent since each is a biconnected component with only neutral cycles, which are also elementary vectors. We first consider the case where po > 2 and show that, for such values of po, G* is dependent. To that end let e, and ej be two arcs in E*, for which the following two situations may arise. (i) e,- and ej belong to the same biconnected component, say G i , of G*. Then, there exists a simple cycle c'J containing both e, and ej whose arcs are all in G\. If c'1-7 is a neutral Chapter 3. Transformation to an Unconstrained Network Flow Problem 27 cycle, that is, ac , , J = 0, then c , , J is an elementary vector and hence e,- and e7- are dependent. Otherwise ac*'-7 ^ 0, and since po>2 there exists an active cycle, say c, in some Gm with 2 < m < p 0 such that / = c1*' — (ac'^/ac)c is an elementary vector of G with /,•/, ^ 0. (it) e,-and tj belong to two different biconnected components of G. By Lemma 7 we can find two active cycles c' and c? one in each biconnected component with c\ = Cj = 1 that intersect in at most one node. Thus / = c' — (ac^/acP)^ is an elementary vector of G for which /,/ ,- ^ 0, and the two arcs are dependent. We have therefore shown that G* is dependent. We next show that, when po > 2, G*, Gpo+i, • • • , Gt are pairwise independent. Clearly no simple cycle of G contains arcs that belong to more than one of the above subgraphs. Thus, if say G' and G" £ {G*, GPo+i, • • •, Gt) are dependent, there must exist an elementary vector / satisfying f f j ^ 0 for some ej £ G' and tj £ G". Moreover, / is a weighted sum of two active cycles, one contained in G' and the other in G". This is impossible since G* is the only component containing active cycles. We now look at the case where po = 1 and face the decomposition of G* = G\ into dependent components. From Lemma 9, G\ either is dependent or can be decomposed into several dependent components, each being a connected subgraph that does not contain any active cycles. Lemma 10, when applied to G\ in the case it contains several dependent components, completes the proof of Theorem 6 by providing the required rim structure of Gi. • The decomposition of a graph into its dependent components described in Theorem 6 will now be demonstrated in the following example. E X A M P L E 1 Figures S.l-b and S.l-c illustrate the decomposition procedure applied to the graph G given in Figure 3.1-a (the circled numbers on the arcs designate the nonzero entries of a). As shown in Figure 3.1-b, G has five biconnected components of which Gi,G2 and G3 contain active cycles and G 4 and G$ contain only neutral cycles. • Our last task in this section is to determine whether a biconnected constrained graph (or subgraph) that contains active cycles is a rim, that is, whether Q > 2. Recall that Chapter 3. Transformation to an Unconstrained Network Flow Problem 28 c: Aggregation into 3 dependent components Figure 3.1: D e c o m p o s i t i o n of the g r aph G Chapter 3. Transformation to an Unconstrained Network Flow Problem 29 a biconnected constrained graph G = (N, E, a) is a rim if and only if it contains at least one active cycle and can be partitioned into Q > 2 constrained biconnected subgraphs Gt = (iV*, El, a'), I — 1, • • • , Q such that no subgraph contains an active cycle and, if Q = 2, A ^ n i V 2 = {ii,*2}, whereas if Q > 3, N lnN i+1 = {it} for t = 1,... , Q - 1 , 7V«niV 1 = {iQ}, JV'niV* = 0 for i f c>£+l. It is important to notice that the fact that a constrained graph is a rim does not depend only on its topology but rather on both the structure of the graph and the nature of the constraint vector o. Example 2 to follow will illustrate this fact. E X A M P L E 2 In Figures 3.2-a to 3.2-c we present a graph with 5 nodes and 10 arcs. The shaded areas delimit the rim components when the graph is a rim, in which case the bolts are denoted by i i , i 2 , etc... The reader will notice that, depending on a, the graph may be a rim with various sets of bolts and components (Figures 3.2-a and 3.2-b) or not be a rim at all (Figure 3.2-c). Indeed, it is easy to show that, for the values of a given in Figures 3.2-a and 3.2-b, G is a rim. On the other hand to verify that the constrained graph G shown in Figure 3.2-c is not a rim notice that, if it were one, the only possible bolts would be the nodes n\ and n 2 , for the cycle e\ — e 2 is active. Therefore, if G were a rim, it would have two components, one of which would contain one of the arcs either e\ or e 2 and the rest of the graph. However, both subgraphs G\{ei} and G\{e 2} contain active cycles and thus do not qualify as rim components, proving that G is not a rim. • In the following Theorem we present a characterization of the bolts of a rim. THEOREM 12 Let G = (N, E, a) be a rim and i some node in N. Then i is a bolt of G if and only if the graph G\{i) obtained by deleting from G node i and all the arcs adjacent to it does not contain any active cycle. Chapter 3. Transformation to an Unconstrained Network Flow Problem a: A rim graph with 4 components b: A rim graph with 3 components c: A graph which is not a rim Figure 3.2: R i m s and G r a p h s Chapter 3. Transformation to an Unconstrained Network Flow Problem 31 P R O O F . Observe first that G\{i) does not contain any active cycle when i is a bolt, for any active cycle goes through all the bolts as was shown in Corollary 11. We now show that if G\{i} does not contain any active cycle then t is a bolt of G. To that end assume on the contrary that all active cycles use node i but that t is not a bolt, that is, it belongs to exactly one component of G, say Gi (recall from the proof of Corollary 11 that nodes may only belong to either one or two rim components). Let c be any active cycle of G, and write ± c as pi + pi + • • • + pq where pt is an oriented path in the rim component Gt from it-i to it (with io = iq). If Gi\{t} contained an oriented path from iq to ti, say p'x, then Pi + Pi H + PQ would be an active cycle of G\{i}, as shown in Lemma 10, that does not use node i contradicting the hypothesis. If on the other hand Gi\{i} does not contain any such path then {i} is a cut-node of G\, which is a biconnected subgraph, again yielding a contradiction and completing the proof. • We assume whenever necessary that G is a constrained palm graph with underlying tree T and partition the set of return arcs E\T into two sets R and S as follows. If c(e,-,T) is an active cycle then it is called an R—cycle and e,- an R—arc (e, E R) while if c(e,-, T) is a neutral cycle it is called an S—cycle and e, an S—arc (e< € S). Clearly the subgraph H of G whose set of arcs is T Li S does not contain any active cycles. The biconnected components Hi, • • •, Hh of H will be called the branches of G. We further let v0 be the largest ancestor of all R-arc tails, that is, v0 — max{l : / £ p(i) (i,k) 6 R) and w0 the largest R-arc head, that is, w0 = max{k : (i, k) € R}. The above definitions are demonstrated in. Figure 3.4. In Lemma 13 we introduce a property of vo and wo that connects these nodes with the R-cycles of G. L E M M A 13 Let G = (N, E, a) be a biconnected constrained palm graph, and VQ and WQ be defined as above. IfwQ < v0, the intersection of all R-cycles is the path p(w0,vo), whereas if vQ < WQ this intersection is empty. Chapter 3. Transformation to an Unconstrained Network Flow Problem 32 P R O O F . For any R-cycle c(ej, T) , with ej = (i, k) £ R, v0 is an ancestor of t and w0 > k. Thus, if wo < v0, then k < wo < VQ < i, p(wo, vo) is a part of c(ej, T), and hence is common to all R-cycles. Moreover, from the definitions of VQ and WQ, no strict ancestor of wo is common to all R-cycles, nor does any strict descendant of VQ. Therefore, the intersection of all R-cycles contains only p(too,t>o), and the first part of the Lemma follows. In order to prove the second part, assume vo < u>o. From the definition of wo there exists an R-arc Cj = (», WQ) € R where i is a descendant of wo, that is, w0 belongs to p(i). Moreover, from the definition of VQ, vo also belongs to p(i), and thus v0 < w0 implies that u 0 is a strict ancestor of wo. Now, there exists another R-arc, say, ej» = (£', k) € R, such that p(vo, i') and p(u0, wo) have only VQ in common, for otherwise the immediate descendant of VQ on p(vo, WQ) would be an ancestor of all R-arc tails strictly greater than VQ, contradicting the definition of v0. We show that c(ej/, T) has no node in common with c(ej, T) . Indeed, if k < VQ we can write c(ej/,T) = p(k,i') + ej- = p(k,v0) + p(v0,i') + Cji. Now, the nodes of p(k, VQ) are all ancestors of VQ and thus, since VQ < wo, p(k,v0) contains no descendant of wo and from the choice of ej# neither does p(vo,i'), whereas c(ej,T) uses only descendants of w0. The same conclusion holds if k > vo, since from the choice of ej/, p(k, i') contains no descendant of WQ. Thus the intersection of all R-cycles is empty and the proof is complete. • We now present four results that connect the palm graph and the rim structures that will in turn provide a basis for our rim detection algorithm. In Lemma 10 we showed that if G is a rim then for any active cycle c, |ac| is a constant. We will now show in Lemma 14 that if in addition G is a palm-graph then ac(ej, T) does not depend on the choice of ej in R. L E M M A 14 Let G = (N,E,a) be a biconnected constrained palm-graph . If G is a rim then ac(ej,T) does not depend on the choice of ej in R. P R O O F . Suppose that the Lemma does not hold and that for some e\,e-i 6 R we have ac(ei,T) ^ ac(e2,T). Since from Lemma 10 we know that |ac(ei,T)| = |ac(e2,T)| then Chapter 3. Transformation to an Unconstrained Network Flow Problem 33 ac(ei, T) = —ac(e2, T). By Lemma 13, the intersection of c(ei, T) and c(e2, T) is a path, say p(w,v), with UJ < u>0 < v0 < v and combining with Corollary 11 we obtain that p{wo,v0) contains all the bolts of G, and thus WQ < VQ. Therefore c = c(ci, T) — c(e2, T) is an oriented cycle of G, which is active for ac = ac(ei,T) — ac(e2,T) = 2ac(ei,T) ^ 0, and thus c also contains all the bolts of G. Now, since v and w are the sole nodes common to c, c(ei,T) and c(e2, T) by Corollary 11 they are the only two bolts of G and hence v = VQ and w = WQ. From the topological structure of rims exposed in Corollary 11, in a rim with two bolts and two components the part of an active cycle that lies between two bolts belongs entirely to one of the two components. Thus, if p(w0,vo) lies in, say, G\ then c(ei,T) — p(u>o,t>o) and c(e 2,T) — p(wo, vo) lie in G 2 , and therefore so does c. We have obtained an active cycle c inside a rim component, and thus a contradiction to Lemma 9. • In the following we will denote by aT the unique value of ac(ej,T), ej G R, whenever G is a rim. Lemma 15 to follow gives a characterization of the bolts of a constrained palm graph that is a rim. L E M M A 15 Let G be a biconnected constrained palm graph with underlying tree T and set of S-arcs S. If G is a rim then its set of bolts is equal to the set of cutnodes of H that lie on p(wo, VQ), together with VQ (resp., WQ) if it is the tail (resp., head) of all R-arcs. PROOF. First recall that H is the subgraph of G whose set of arcs is T U S and that a rim contains active cycles, thus R ^ 0. We start by showing the first inclusion, namely, that the set of bolts of G is included in the above set. To .that end we show that if a node to 6 TV is a bolt of G it is either a cutnode of H that lies on p(w0,v0) or vo (resp., wo) if it is the tail (resp., head) of all R-arcs. Let us first assume that i0 = v0 (resp., wo) but that io is neither the tail (resp., head) of all R-arcs nor a cutnode of H. Clearly, io belongs to some branch of G, say Hi, and given any R-arc ej whose tail (resp., head) is not i 0 (we made the hypothesis that such an arc exists) the R-cycle c(ej,T) goes through to (since i0 is a bolt, and by Corollary 11 all active cycles do), and thus through He. Let ix and i 2 be Chapter 3. Transformation to an Unconstrained Network Flow Problem 34 respectively the first and last node of c(ej, T) that belong to the branch Hi and p(i\, i2) the portion of c(ej,T) that lies in Hi. Notice that c(ej,T) does not lie entirely inside Hi, and thus enters and leaves Hi either through cutnodes of H or, if ej is incident to some node in Hi, through an extremity of ej for these are the only nodes common to Hi and the rest of H L) {ej} (recall that c(ej,T) is composed of ej together with arcs of H). Therefore, since io is neither a cutnode of H nor the tail or head of ej, by the choice of ej, then io, *i and i2 are distinct nodes of Hi. Now, since Hi is biconnected there exists a path in Hi, say p, from ii to 12 that does not go through io- Moreover, from the fact that Hi does not contain any"active cycles we can show, as in the proof of Lemma 10, that ap = ap(ii,i2) and p, being inside Hi, does not intersect with c(ej,T) — p(ii,^2) which lies entirely outside of Hi. Thus, replacing p(i x , i 2 ) in c(ej, T) by p results in another active cycle c(ej,T) — p(ii, i 2 ) + p of G that does not contain io, contradicting the fact that io is a bolt. The proof for the case where io & {VQ, W0) is a bolt but not a cutnode of H on p(vo, Wo) is identical except that we can take for ej any R-arc. In order to prove the reverse inclusion we first show that the cutnodes of H that are on p(w0, VQ) are bolts of G, and from Theorem 12 it suffices to show that all active cycles of G go through them all. The family of cycles {c(e,-, T), e,; G S U R] forms an algebraic basis of the unconstrained circulation space of G (for S\JR = E\T, see e.g. [Ro84, p. 117] and [Ki47] for the introduction of these cycles and the original proof) and any cycle on G can be written as c = X T e >6Sufl ! / j c ( e i ) ^ 1 ) - Now, let Hi be a branch of G that contains at least-one cutnode of H on p(w0, v0), say, i x . If we regard cycles as flows, then clearly no flow corresponding to an S-cycle leaves Hi through t'i (or, for that matter, through any other node) for S-cycles lie either entirely inside or outside Hi. However the flow corresponding to any R-cycle c(ej,T) leaving Hi through i\ is equal to 1 if the arc ( / ( i i ) , i i ) £ Hi and to —1 otherwise, for c(ej,T) contains the path p(u?o,uo) which enters or leaves Hi at ii (p(u>0,t;o) contains all the bolts of G, and hence i x ) . Thus, the flow corresponding to c leaving Hi through i i is equal to iHejeKJ/j- Now, since the S-cycles are neutral and ac(ej,T) = aT for all R-cycles, the fact that c is active implies ac = T.^syjac{&hT) + T,c,zRyj<xc(ej,T) = a r £ e > e f l 2 / ; ^ 0. Chapter 3. Transformation to an Unconstrained Network Flow Problem 35 From Lemma 10, \ac\ = |a r | , £eyefl Vj = tna* *si * n e fl°w corresponding to c leaving Hi through ii is nonzero. Therefore i\ is a node of c and the proof is complete. Similarly, if vQ (resp., u>0) is the tail (resp., head) of all R-arcs then obviously deleting VQ (resp., wo) yields a graph with no active cycle and, by Theorem 12, vo (resp., tu0) is a bolt. • Before giving in Theorem 16 a characterization of palm-graphs that are rims, we introduce a degenerate class of rims which will be referred to as one—rims. We call a constrained graph G = (N, E, a) a one-rim if and only if it is biconnected, dependent (and therefore not a rim), and has a unique node i\ € N, called by extension a bolt, with the following property. There exists a partition of the arcs incident to i'i into two subsets such that splitting i\ into two copies of itself, say i'x and i", assigning the arcs of each of these subsets to i[ and to i", respectively, and introducing the expansion arc l\ = (i'i,i'{) (with a€l = 0) results in a rim to be referred to as the expanded one—rim (see figure 3.3). One may think of a one-rim as a rim with one component, or as a rim with two components, one of which is degenerate. The appropriate partition of the arcs incident to i x will be determined in Algorithm I. Figure 3.3: A one-rim (left) and its expanded version (right) To motivate the attention given to one-rims, notice that the set of feasible flows on the original arcs of the expanded one-rim is equal to that of the one-rim, as long as the demands Chapter 3. Transformation to an Unconstrained Network Flow Problem 36 assigned to i[ and i" add up to that of i\. Moreover, since the graph obtained by splitting the unique bolt of a one-rim in the fashion described above is a subgraph of its expanded version, and is dependent, it is a rim component of the expanded version, the other component being the singleton {e"i}. THEOREM 16 biconnected constrained palm graph G = (N,E,a) is a rim (resp., a one-rim) if and only if R ^ 0, {ac(e,-,T), e,- £ R) is a singleton, w0 < v0 and p(wQ,v0) contains at least two (resp., exactly one) node(s), each of which is either (i) a cutnode of H, (ii) the tail of all R-arcs or (iii) the head of all R-arcs. PROOF. First, let us prove the theorem for rims. We have seen in Lemmas 14 and 15 that these conditions are necessary, and prove now that they are also sufficient. The part of G that lies (in the order given to N) between two consecutive nodes that verify (i), (ii) or (iii) is a biconnected subgraph that contains no active cycle. Indeed, no R-arc is incident to any node of this subgraph, except possibly for the first, say and the last, say iq, of these nodes, and thus it is composed of a single branch that possesses the properties required to be a rim component. Furthermore the complement, in G, of the union of the above branches, say G\, has by construction exactly two nodes in common with arcs not in G\, namely i i and ig. In order to show that G\ is a rim component we first show that it contains only neutral cycles. Indeed, the vector z = J2aeRei * s a c u * °f G i , for all paths from iq to i\ in Gi contain a forward R-arc. Any cycle c of Gi can be written, as in Lemma 15, c = Z)eieSuH c» c( e«j^1)> a n < l since cuts and cycles are orthogonal 0 = c*z = £ e i € f l C , - , thus ac = aTJ2eieRci = 0 a n ( ^ c i s neutral (recall that ar is the unique value of ac(ej,T), ej 6 R). We now claim that G\ is biconnected, and rule out the trivial case where G\ is equal to R and is a singleton (a subgraph composed of a single arc is biconnected). Assume on the contrary that G\ is not biconnected then, since G is biconnected and G\ has only i\ and iq in common with the rest of G, G\ is connected. Moreover, the biconnected components of G\ then form a chain between i i and iq (for G is biconnected whereas a biconnected component Chapter 3. Transformation to an Unconstrained Network Flow Problem 37 of G\ with only one node in common with the rest of G\ or with the set {i\, iq) would also be a biconnected component of G). Thus any active cycle of G goes through all the cutnodes of Gi for they include a path from i\ to iq in Gi, and since no,biconnected component of G\ contains active cycles then G is a rim whose set of bolts includes the cutnodes of G\, contradicting Theorem 15 and completing our proof for rims. Now, in order to s^how that the result is valid for one-rims, it suffices to apply the above to the expanded version of a one-rim (recall that these are rims with two components), and interpret it in terms of the original one-rims (by condensing the expansion arc, thus restoring the "original graph). • We define in the following a coloring of the nodes and branches of G that, as will be seen, is easily implemented in a depth-first search algorithm, and allows us to determine both the rim components and bolts of G. We color in red all the descendants of vo (including VQ) that belong to some R-cycle and in blue all the ancestors of WQ (including wo) that belong to some R-cycle. Then, color in red (resp., blue) all the branches of G that contain an arc in T whose extremities are both red (resp., blue) and color in white the remaining nodes and branches. It is clear from Theorem 16 that if G is a rim then WQ < VQ, thus no descendant of vo is an ancestor of w0, and a unique color is assigned to each node. The coloring of the graph G given in Figure 3.4 is demonstrated in Figure 3.5. The usefulness of the coloring of G is justified by the following theorem. THEOREM 17 If G is a rim then the R-arcs and the non-white branches of G form one of its rim components, the others being the white branches. PROOF. We start by showing that all the white branches are rim components of G. To that end, first notice that a rim component that lies between two consecutive bolts, say u and v, u < v, and which contains the arc (/(u),u), is the unique white branch that contains (/( u)i u) ( s e e Figures 3.4 and 3.5). Indeed this white branch is biconnected, contains no active cycles, and since u and v are consecutive bolts on p(w0,vo) it contains u. Also recall Figure 3.4: A palm graph with its branches Figure 3.5: The coloring of the palm graph G Chapter 3. Transformation to an Unconstrained Network Flow Problem 40 that the branches of G are dependent subgraphs of G (since they are biconnected and contain no active cycles, every pair of arcs in a given branch belongs to some neutral cycle of that branch, that is, to an elementary vector of H(a), and thus is dependent) and since rim components are maximal dependent subgraphs of G, branches either are included in rim components or do not intersect with them. Now, the nodes of the rim component mentioned above are not descendants of VQ (resp., ancestors of WQ) except possibly for VQ (resp., wo) itself, and therefore it does not contain any arc whose extremities are both red (resp., blue) nor, from the above remark, any arc that belongs to a red (resp., blue) branch. Therefore, that rim component is composed of only white branches and, being biconnected, does not contain more than one such branch, proving our claim. Consequently the part of G that lies between the first and last bolt, in the order given to N, and that contains the father of the latter, is a "chain" of branches, each of which has one bolt (a cutnode of H) in common with the next (see Fig 3.5). We show next that the remaining part of the graph, namely the last rim component Gi introduced in Theorem 16, is composed entirely of the non-white branches and R-arcs. Let us assume on the contrary that G\ contains at least one arc of a white branch, say, Ho From the remark made in the first part of the proof, we obtain that Hi C G i . Notice further that if a branch Hk is red (resp., blue) then there exists a path on T that goes from vo (resp., WQ) to an arc in Hk whose extremities are both red (resp., blue). Therefore we may assume without loss of generality that Hi is a leaf branch of G, that is, a branch that has only one node in common with the rest of H. However, such a leaf branch needs to have a return arc from one of its nodes, other than the cut-node of H, to some other node of G\Hi, and that return arc is necessarily red (for, since Hi is a leaf of H, no* arc of H\Hi is incident to other nodes of Hi than the unique cutnode of H that connects Hi to the rest of H). Therefore Hi contains at least one arc that belongs to some R-cycle, and thus two red or two blue nodes, yielding a contradiction and completing the proof. • Note that a constrained graph can be transformed into a palm graph in many ways, depending for example on the choice of the root. However if G is a rim its set of bolts is Chapter 3. Transformation to an Unconstrained Network Flow Problem 41 unique as shown in Theorem 12, and as a consequence of Corollary 11 so is the partition of G into rim components. Therefore the sets of bolts and of rim components, as obtained in Theorems 16 and 17, are independent of the palm graph chosen. We now present Algorithm I that, given a biconnected constrained graph G = (N, E, a), will determine whether G contains active cycles and, if so, whether G is either a rim or a one-rim. In the latter case, it will either provide its bolts and the rim components or, for a one-rim, its unique bolt and its expanded version. In addition, it will be useful at a later point to have a feasible flow for the unconstrained version of G. Such a flow, denoted by x, can"be obtained by sending, for each node t 6 N, a flow of <2,- along the path p(i), so that the flow on each tree arc is equal to the sum of the demands of the descendants of its head (it is a well known result that x is the basic feasible solution, in the usual sense of linear programming, associated with the tree T). A L G O R I T H M I Using any linear-time algorithm based on depth-first search (see e.g. [Ta72j, and [HT73]) determine the branches of G (that is, the biconnected components of H) by working on H and ignoring in G the R-arcs (see "Return arc partitioning" below) as they are encountered. Simultaneously, in addition to the operations related to the detection of the branches, perform the following: A r c redirecting. Whenever an arc e,- = (u, v) is visited as a tree arc and v < u (resp., as a return arc and u < v) redirect e,-, that is, replace it by (u, u) and replace a,- by —a,-. Node Labelling. Set o f = 0, then, whenever a node v is visited for the first time set a7 = <xj(v) + oti where e» = (f(v),v). Recall that o% — ap(y). Computation of x. Start by setting = d, for all tree arcs (/(»'), i), i 6 N. Then, whenever the search backtracks from a descendant j of i to i , add X(,j) to 3(/(.),t). Return arc partitioning. If the arc e,- = (u,u) is visited as a return arc and a £ + ct,i — ctf = 0 then put e,- in 5, otherwise put it in R and color u in red, v in blue. If during the search o £ + a,- — a* (= o/c(e,-, T)) takes on more than one non-zero value end Chapter 3. Transformation to an Unconstrained Network Flow Problem 42 the search and state that G is not a rim. (Notice that when G does not contain active cycles the algorithm will return R = 0 and thus will detect such graphs). Detection of t>o and WQ. When the search visits an R-arc, say (v, w), for the first time, it colors its tail v, in red, its head w in blue, and continues its exploration from v. At a later point when all the descendants of v have been visited the search backtracks from v and indicates to its ancestors that v is red by coloring them in pink. If during the search a node, say u, is colored in pink twice when backtracking from two of its sons then we conclude that u> vQ and we color u in red (notice that it is not indispensable to also color in red all the pink nodes between u and its red ancestors). The last node to be colored in red is v0. The first blue node encountered during the backtracking, and thus during the whole search, is WQ, and all subsequent tree nodes encountered are colored in blue until the last R-arc head is reached. Clearly If v 0 < WQ we conclude that G is not a rim. Detection of the bolts. In order to keep a record of the cutnodes of H or heads or tails of all R-arcs encountered when backtracking from VQ, the algorithm keeps a stack of such nodes visited since and including the most recent red node, emptying it completely whenever a new red node is encountered (keeping only the new red node), and stopping the stacking process after the first blue node, namely WQ, is encountered. If by doing so we obtain an empty stack, then G is neither a rim nor a one-rim, whereas if we obtain a unique (resp., two or more) nodes then G is a one-rim (resp., a rim) and the stack contains its bolt(s). R i m components (if G is a rim). The Biconnectivity Algorithm we apply to H, as described by [Ta72], keeps a stack of arcs corresponding to each branch, emptying it as cutnodes are encountered. Similarly we keep a stack of rim component starting at the first bolt encountered during the backtracking process and ending with the last bolt, yielding successively GQ, • • •, G2, while G\ is equal to the remainder of the graph. One—rim split, (if G is a one—rim) replace the bolt i'i of G by the arc e% = i"), assigning to i[ the tree arcs and S-arcs joining ii to descendants of it, together with R-arcs whose tails are i i , and the remaining arcs to i". The proof of the validity of Algorithm I lies in Theorems 16 and 17. Chapter 3. Transformation to an Unconstrained Network Flow Problem 43 Complexity of Algorithm I All the operations described above can be performed in a single depth-first search, and the time and memory they require at each step of the search is independent of the size of the graph. Moreover, the space required to maintain the lists corresponding to R, S, ac(ej,T),ej G R, the coloring, and the stack of candidate bolts, is at most 0(m + n). Therefore, since the depth-first search alone takes O(m-J-n) (including the operations related to the biconnected components of H, see e.g. [Ta72,HT73]), Algorithm I runs in linear time. 3.4- Decomposition Into Independent Monotropic Network Flow Problems In this section we develop a decomposition theory to partition the Singly-Constrained Monotropic Network Flow Problem into subproblems where the total number of variables over the subproblems equals the number of variables of the original problem. Of those subproblems at most one is a SCMF, whereas all the others are unconstrained monotropic network flow problems. Our linear time procedure thereby establishes whether P(a, ao) can be transformed into an unconstrained monotropic network flow problem and if so carries out the transformation. We will assume without loss of generality that the underlying graph G has been mod-ified in the fashion described by Granot and Veinott [GV85] that is, that the biconnected components of G have been disconnected by creating multiple copies of the nodes common to more than one component (cutnodes of G) and that the demand at the original nodes has been allocated to their copies in the appropriate way. This modification clearly does not affect the values of the ajs for there exists a one-to-one correspondence between flows in the original graph and flows in the modified graph that maintains the same flow on each arc. Now, since the biconnected components G i , • • •, Gt of G do not have nodes in common, there exists a numbering of E and N for which the constraint matrix Aa of problem P(a, a0) can be written as Chapter 3. Transformation to an Unconstrained Network Flow Problem 44 A1 A2 i i i \ \ i i * A' a 1 a 2 a1 where A1 (resp., A2,..., A1) is the incidence matrix corresponding to Gi (resp., G2,..., Gt) and a 1 (resp., a 2 , . . . , a*) the parts of a corresponding to the arcs in G\ (resp., G2,..., Gt). Following the notations used in Theorem 6 assume without loss of generality that the bicon-nected components Gi, • • •, GPQ of G contain active cycles, whereas the remaining biconnected components GPo+i,... ,Gt do not. Since GPo+i, • • •, Gt do not contain any active cycle then apo+i (resp., a P o + 2 , • • • , a*) is a linear combination of rows of APo+1 (resp., A P 0 + 2 , • • •, A1) and thus by an appropriate modification of a and a 0 we can assume, without loss of generality, that a P o + 1 = • • • = a1 = 0. Clearly if po = 0, that is, if no biconnected component of G contains active cycles, then P(ct, ao) is feasible if and only if ao is also equal to zero, in which case the constraint may be dropped altogether. If we rearrange the rows of Aa so that the a row follows the last row of Ap° then clearly Aa will have the block-diagonal form. We will denote the north west block containing the rows of A1,...,APo together with the a row as [^]. It is a well known result that any optimization problem with column-additive objective function whose constraint matrix is block-diagonal can be decomposed into independent subproblems, each corresponding to the variables and linear constraints associated with a block of the matrix. We have therefore so far obtained a decomposition of P(a, a0) into / — po + 1 subproblems, only one of which (corresponding to the north-west block) is a SCMF, the other I — po being unconstrained Chapter 3. Transformation to an Unconstrained Network Flow Problem 45 network flow problems. We will show that in some situations we can further transform [—] to a block-diagonal structure, in which case the problem P(a, oo) is transformable to an unconstrained network flow problem altogether. To that end, we return to the study of rims, that is, of biconnected constrained graphs whose number Q of dependent components is at least two (in the sequel we assume without loss of generality that one-rims were replaced by their expanded version as described in section 3.3. Recall that the set of constrained flows on a one-rim is identical to the set of flows on the corresponding rim component of the associated expanded one-rim). We will show in Theorem 18, to follow, how the rim structure is related to the decomposition of the SCMF. We first require the following construction. CONSTRUCTION 1 Let G = (N,E,ct) be a rim palm graph with rim components GQ = (Nq,Eq,aq), q = 1,... ,Q > 2 and GQ+I = G\. Denote by iq the bolt that is common to Nq and Nq+1 (see Figure 3.6-a). Consider now the expanded rim G — (N,E,a) obtained from G by splitting each bolt iq into two copies i'q and i", in such a way that all the arcs of Eq (resp., Eq+1) incident to iq in G are now incident to i'q (resp., i"q) in G, and by adding to E the arcs eq = (i'q, i'q), q = 1, • • •, Q, with an associated parameter = 0, the rest of G being unchanged (see Figure 3.6-b). G is also a palm graph, and we may define on itp(i), D(i), c(ej,T) for i £ N, ej £ E in a similar way as their counterparts p(i), D(i), c(e 7,T), i € N, ej £ E in G. It will be useful to notice that p(i) = p(i) + £; e r;(,») eq Vi £ N, ap(i'q) = dtp(iq) = ap(iq) = cxj^ for all q = 1, • • • , Q and ap(i) = aj for all other nodes. Moreover c{ej,T) — c(ej,T) for tj £ S and c(ej,T) = c(ej,T) + _£ , = I , . . . ,Q eq for ej £ R. Recall that aw is the unique value of ac(ej,T), ej £ R, and define on G a demand vector d as follows h = £ d, + ^ ( a o - E ^ f ) iez>(t,) a t / i forq = l,---,Q, di» = diq - J,, (3.4) d,- = d,- for all other nodes.O Transformation to an Unconstrained Network Flow Problem 46 c: The decomposed rim Figure 3.6: Rim Decomposition and Expansion Chapter 3. Transformation to an Unconstrained Network Flow Problem 47 THEOREM 18 Suppose that a biconnected constrained palm graph G = (N, E, a) has several dependent components, say Gq = (Nq, Eq, a9), q = 1,---,Q > 2. Then the set of constrained flows on G is the Cartesian product of the sets of unconstrained flows on each dependent component when the demands at the nodes shared by two successive dependent components are given by (3.4)-* PROOF. First, in the notation of Theorem 6, po = I = Q > 2, and thus from Theorem 6 G is a rim. Clearly there is an identical one-to-one correspondence between constrained flows on G and the respective entries of constrained flows on G, as long as each demand d{q is shared by i'q and i'q' in such a way that + J,» = d{q. We start by temporarily apportioning the demand at the bolts between their respective copies by setting d^ = 0 and d{» = diq for q = \,---,Q, di = d< for all other nodes. Then, notice that the flow x° = J2i?i dip(i), obtained by sending for each node i 6 N, i ^ 1, a flow of J,- from node 1 to i, is a feasible unconstrained flow (it is easy to see that it meets the demand requirements, that is, Ax° = d, where A is the incidence matrix of G). Since this flow may not meet the additional constraint ax = a0, we pick any R-arc £ R and adjust the value of the left-hand-side of the additional constraint by sending the appropriate flow along the active cycle c(efc,T), defining the constrained flow i 1 = £ d,P(i) + -^(ao - E * « f ) £ ( « * . T). Indeed, the particular solution x 1 also meets the demand requirements for, since c(ejt,T) is a cycle, Ac(ek, T) = 0, and Ax 1 = Ax° + l/ar (a0 - E,#i <fc*f )Ac(ejt,T) = Ax° = d, as well as the additional constraint, for ax1 = a E ^ W + T ( a ° - E ^ n « c ( e i c , T ) = E ha* + (a 0 - J2 di<*J) = «o Chapter 3. Transformation to an Unconstrained Network Flow Problem 48 (using the fact that, from the choice of d, 6x(ejb,T) = ac(ejt,T) = a r). Now, any constrained flow x can be expressed as the sum of a particular feasible con-strained flow, say x 1, and of some constrained circulation, say, x 2. As in the proof of Lemma 15, x 2 can be written x 2 = J2cjesuRyjc(ejiT) where ax 2 = 0 implies that Y^ejeRVj — 0, and thus the general expression of any constrained flow on G is given by x = x 1 + x 2 = E*P(0 + - 7(«o - E ^ f ) 5(e* . r ) + £ %c(Ci,r). (3.5) t / l Q e^esuR Further, notice that the entry of p(i) on some arc eq is equal to 1 if p(i) uses the arc e,, that is, if i is a descendant of iq' in G, and to 0 otherwise, whereas the entry of any R-cycle (resp., S-cycle) on that same arc is equal to 1 (resp., 0). Therefore xiq = x^ + x2^ = X)te.D(,») di+l/ocT (ctQ—J2i?i diQJ) for all 9 = 1, • • •, Q and is independent of the constrained flow x. Noticing that, from the choice of <f,v and <i,», the first term J2ieD(i%) di is equal to Di€D(t,) di, the way i'g and share diq can then be adjusted in order to restrict the flow on the arcs eq, q = 1, • • •, Q to zero by adding x g, to d^ and subtracting it from d^, resulting in the adjusted version of G where d<; = 2Z <*.• +-7(00 - 5 3 <*•<*?") for q = 1, •••,(?, di» = di, ~ di>q-Indeed, since only the demand at the endpoints of e,, q = 1, • • •, Q are changed and these changes add up to zero for each one of those arcs, the new* flows on the adjusted version of G are obtained from the old ones by sending along e, = (iq,iq) a flow equal to the change of resulting in xiq = 0 for all q = 1, • • •, Q. Now, deleting the arcs e,, q = 1, • • •, Q that carry no flow will disconnect the graph into connected components that are the dependent components of the original graph (see the disconnected version of G in figure 3.6-c) and from the way x was constructed in (3.5) the constraint need not be expressed explicitly. The Chapter 3. Transformation to an Unconstrained Network Flow Problem 49 set of flows on the unconstrained disconnected version of G is thus equal to the set of flows on the original version of G, and thus to that of G, and the proof follows. • Notice that the modified demand vector given by (3.4) can easily be computed as part of Algorithm I, and thus in linear time. Indeed, both 2^i€D(i) «^ a n < ^ ^ ieD(j) diCtf can be obtained recursively for all nodes j as the depth-first search backtracks to j, the term ^2i?i dioif being equal to £i€c(i) hatf — diaj = £t gD( i ) ^«af (recall that, by definition, aj = 0), and aT is also obtained in Algorithm I. The above decomposition is demonstrated on a rim G with Q = 3. E X A M P L E 3 Consider the palm graph G with 7 nodes and 12 arcs given in Figure 3.7-a with the additional constraint x\2 — xjt + 2 i 2 3 — 2x37 + 3X.JI + 3xsi = 28 and the demands di = di = d*> = d7 = 0, and d2 = 4, <f3 = I, de = —5 For this palm graph, T = {(1,2), (2,3), (3,4), (4,5), (5,6), (3, 7)}, R = {(4,1), (5,1)}, S = {(7,1), (7,2), (6,3), (6,4)}, 1 = WQ < vo = 4. The path P(WQ,VQ) contains node 1 which is the head of all R-arcs and node 3 which is a cutnode of H. ac(ej,T), ej £ R takes on the unique value aT = ac((4,1),T) = ac((5,1),T) = 6. Thus, from Theorem 16, G is a rim whose two components Gi and G2 have for respective node-sets Ni — {3,4,5,6} and N2 = {1,2,3,7}, its bolts being the nodes ii = 3 and i2 — 1. Figure 3.7-b illustrates the expanded rim, G in which the bolt i\ (resp., i2) is split into nodes i'x = 3' and i" = 3" (resp., i'2 = 1' and i'2' = I"). Given that aj = 0, aj = 1 aj = ct% = aj = aj = 3, aj = 1, then from (3.4) we obtain . €D (3 ) a ' t# l = dyi — d$ — <f3/ = —1 and di>2 = d~v = E di + -r( a o - E ^ « a ^ ) = 6 ieD(i) a t#i <fj« = din = d\ — dy — —6. The disconnected unconstrained subgraphs are shown in Figure 3.7-c. • c: The two equivalent subgraphs Figure 3.7: R i m E x p a n s i o n Chapter 3. Transformation to an Unconstrained Network Flow Problem 51 We now return to the original problem P(a, a0) and use the results obtained above to present Algorithm II which decomposes a SCMF defined on the constrained graph G = (N, E, a) into independent subproblems on the dependent components of G. After a fea-sibility check (Step 1) Algorithm II isolates the biconnected components of the underlying graph (Step 2) and disconnects them in the manner described by Granot and Veinott [GV85]. Each of the components is then tested for the presence of active cycles and for the rim and one-rim structures (Step 3). Independent unconstrained subproblems are defined on those components that do not contain any active cycle. If all the biconnected components con-tain no active cycles Algorithm II terminates at Step 4 with an equivalent unconstrained monotropic network flow problem. If several biconnected components contain active cycles or if the unique biconnected component that contains active cycles is not a rim, the algorithm gives the decomposition of the original problem into subproblems, one of which remains a SCMF (Step 5). If, however, a single biconnected component contains active cycles and is either a rim or a one-rim, Algorithm II provides a decomposition of the original problem P(a, cto) into unconstrained subproblems (step 6). A L G O R I T H M II Step 1. Check if the unconstrained network flow problem obtained from P(a, ao) by removing the constraint ax = ao is feasible, that is, if the linear system Ax = d is feasible (the total demand on each connected component of G should be zero). If not, P(a, ao) is infeasible, and terminate. Step 2. Decompose G into say £ biconnected components G> = (Nr, Er, aT) r = 1, • • • , £, * and disconnect those that have nodes in common by apportioning the demand at the common nodes between the copies thereof in the fashion described in [GV85]. Step 3. Apply Algorithm I to each biconnected component G> in order to determine if they contain active cycles, and assume without loss of generality that G>, 1 < r < po, contain(s) at least one active cycle. If only one of them does, say Gi, (that is, if p0 = 1), use Algorithm I to determine if it is a rim or a one-rim (in the latter case, replace it Chapter 3. Transformation to an Unconstrained Network Flow Problem 52 by its expanded version, a rim, and set the cost associated with the expansion arc to zero). Now, if Gi is a rim expand and disconnect it as described in Theorem 18 and compute the modified demand according to (3.4). Step 4. For each one of the biconnected components of G that do not contain active cycles create the unconstrained subproblem Pk : Min £ bj(Xj) s.t. Akxk = dk k = po + l , . . . , e where xk = (x,)e,e^ and dk = (d,),-^, for k — po + 1,... ,£. If, further, none of the biconnected components of G contain active cycles that is, if po = 0, and if ocYlr=i,-,tx( r) — ao (where x(r) is the feasible unconstrained flow for the subgraph <S>, computed as "x" in Algorithm I) then P(a, ao) is feasible and equivalent to Pk, k = 1, • • • ,£ and thus is transformable to an unconstrained network flow problem. If, However, po = 0 and aJ2r=i,-,tx( r) i1 Qo then P(a,a0) is infeasible. Step 5. If G\ is the unique biconnected component of G that contains active cycles (po = 1) but is neither a rim nor a one-rim, or if several biconnected components of G contain active cycles (po 2) (recall from Theorem 6 that in those two cases G* is a dependent component of G) create the subproblem P > , a 0 ) : Min £ bj(Xj) s.t. A*x* == d* ax* — ao where x* = (x,) e. €£;. and d* = (d,)i€£;.. P{a, Q0) is equivalent to P*(a, a0), together with Pk, k = po + 1, • • • and thus not transformable to an unconstrained problem. Step 6. If a single biconnected component of G contains active cycles, that is, po = 1 and G* = G\, and if this biconnected component is a rim (recall that if it was originally a Chapter 3. Transformation to an Unconstrained Network Flow Problem 53 one-rim, it has been replaced by a rim in Step 3), then for each one of the disconnected rim components of G\ build the unconstrained subproblem Pq : Min £ bjixj) s.t. A'xW = $ti q = l, 9 where x^ = (x,)ei€.E,, and d^q\q = 1,••-,(?, is the part of the modified demand vector J obtained in (3.4) corresponding to Nq. The original problem P(a,ao) is then " equivalent to the Q + £ — 1 independent unconstrained problems P*, k = 2 , . . . a n d Pq, q = 1,..., Q, and thus transformable to an unconstrained problem. Note that the problems Pq corresponding to the components of the rim G* that are singletons (i.e., contain only one arc), if any such rim components exist, are trivial one-variable problems of the form Min{6j(x^) : x^ = cPf^} where ej is the unique arc of Gq (in particular, this is the case of the component {ei} of the expanded version of a one-rim). As a result P(a, ao) really decomposes into only Q -f £ — 1 — Z nontrivial independent unconstrained network flow problems, where Z is the number of rim components of G* that are singletons. Proof of the Validity of Algorithm II The preliminary decomposition into subproblems corresponding to G*, C P o + i , • • • , Gt is a direct result of the block-diagonal nature of Aa described at the beginning of this section. For the case po = 0, it is further necessary to check that the problem P(a, ao)-is feasible (step 4). Notice that this is true if and only if any given feasible unconstrained flow, say x° , meets the constraint. Indeed, recall that for any feasible unconstrained flow x, a x — a x ° = a(x—x°) = 0 for x — x° is a circulation, and thus a linear combination of simple cycles which are all neutral (pQ = 0). We choose for x° the flow X)r=i,. ;tx(r)> where x(r), r = l,---£, is a feasible unconstrained flow on the biconnected component G> of G (obtained in Algorithm I), justifying Step 4. The remainder of the proof lies in Theorems 6 and 18. • Chapter 3. Transformation to an Unconstrained Network Flow Problem 54 Complexity of Algorithm II Step 1 requires the decomposition into connected components, which takes 0(m), Step 2 takes 0(m + n) [Pa71,Ta72,HT73], Step 3 takes 0(\Er\ + \Nr\) on each biconnected component GT for a total of 0(rn + n) and Steps 4, 5 and 6 also take linear time, thus Algorithm II runs in 0(m -f n). It is interesting to note that in the event where P(ct, a0) is transformable to an uncon-strained network flow problem its constraint matrix Aa is not necessarily totally unimodular. The following example shows a constrained network flow problem that is transformable to an unconstrained one but whose matrix is not totally unimodular. E X A M P L E 4 Consider the graph G with two nodes and two arcs given in Figure 3.8 together with the additional constraint x\ — x2 = 1. G is clearly a rim whose two components have respectively {e\} and {e2} as their arc sets, and the bolts of G are i\ and i2. Thus any problem P(a, ao) on G is transformable to an unconstrained network flow problem. However, the constraint matrix of such a problem has [ " l 1 ! * ] as a submatrix, whose determinant is equal to 2, and thus the constraint matrix is not totally unimodular. • Figure 3.8: The r im G We now argue that the decomposition presented above is exhaustive in the sense that none of the subproblems obtained can be further decomposed. By "decomposing a prob-lem", we mean expressing, independently of the cost function, its set of optimal solutions as a cartesian product of optimal solution sets of subproblems obtained by partitioning the un-derlying graph. First, the subproblems on the biconnected components that do not contain any active cycles, as well as those on the components of a rim, if such a situation occurs, Chapter 3. Transformation to an Unconstrained Network Flow Problem 55 are unconstrained network flow problems on biconnected graphs and therefore cannot be decomposed (see, for example, [GV85]). We now claim that the constrained subproblem on a dependent subgraph, if any, cannot be decomposed either. In order to see this, suppose on the contrary that, regardless of the cost-function vector (6 j (z j ) ) e > € £; . , the subproblem P*(a, QQ) on the constrained dependent subgraph G* can be decomposed into two indepen-dent subproblems, say, Pt' and P2", over two subsets E{ and E2 of the set of arcs E*. Since G* is dependent there exists an elementary vector, say / , of the circulation space over G* that has nonzero components on at least one arc of each of the sets E^ and.E2. Consider now the problem P*(a, a 0) obtained by setting bj(xj) equal to zero if Xj = fj or if ej G E^, and to + 0 0 otherwise. One of its optimal solutions is x = / , and if the subproblem is indeed decomposable then the projection x1 = f1 obtained by setting to zero all the components of / that correspond to arcs in E2 should form a feasible solution for P{. Moreover, the zero vector on E\ is clearly optimal for P2', and since the solution set of P*(a, a 0) is the Cartesian product of those of P{ and P2 it contains f1 which is therefore feasible for P"{ct, ao). Thus P can be written as a sum of conformal elementary vectors of the circulation subspace of G* whose supports are all included in that of / x , which is strictly contained in that of / (for / has nonzero components on at least one arc of E2), contradicting the fact that / is an elementary vector, and proving our claim. A similar proof holds if P*(a, a 0) decomposes into more than two subproblems, and this trivial extension is omitted. The foremost consequence of the above is that if the original SCMF is transformable to an unconstrained problem, in the sense that its solution set is the cartesian product of the solution sets of unconstrained network flow subproblems on subgraphs of its underlying graph, then Algorithm II will de-tect it and provide the transformed problem. Conversely, if Algorithm II does not yield such a decomposition, that is, one of the subproblems it yields is a constrained problem, then we may conclude that the original problem does not admit such a transformation. Chapter 3. Transformation to an Unconstrained Network Flow Problem 56 3.5 Extensions and Remarks Cost Function We start this section with a remark concerning the cost-function of the problem P(ct, OCQ). Indeed, the hypothesis that the objective—function be arc-additive can be relaxed in that, given the block-diagonal structure of Aa corresponding to the dependent components of G, it suffices that it be "dependent component-additive". That is, it is 9 sufficient that the objective function can be expressed as a sum of functions whose respective arguments are the sets of variables corresponding to each dependent components of G (the proof is trivial and therefore omitted). Nonlinear and Inequality Constraints In order to see how our procedure can handle nonlinear and inequality constraints we require the following theorem. T H E O R E M 19 For a biconnected constrained graph G = (N,E,ct) the following are equivalent. (a) The additional constraint is equivalent by a linear transformation to the difference of sum of variables associated with arcs directed into a single node ii and a sum of variables associated with arcs directed away from that same node (that is, a sub-sum of the node balance equation for that node) (b) There exists a way of splitting one node ii £ N and introducing an arc, say ex, between its two copies, such that the additional constraint is equivalent by a linear transformation to xix = 8, where 6 depends on a and the demand vector d. (c) G is either a one-rim or a rim and i\ is a bolt. * P R O O F . The fact that (a) and (b) are equivalent is straightforward and only involves combining the node-balance equations for t'i and its two copies with the constraint. More-over, it is a direct consequence of theorem 18 that (c) implies (b). In order to show that (b) implies (c), consider the expanded graph G obtained in (b) by splitting i\ into, say, i[ and i" and let et = (i\, i"). For the constraint x S l = 6 on G, G considered as a subgraph of G that Chapter 3. Transformation to an Unconstrained Network Flow Problem 57 contains no arcs with otj ^ 0, and thus no active cycles. Therefore, G is either a one-rim (if the expanded graph without the expansion arc, G\{e"i} is biconnected) or a rim (if G\{e"i} has several biconnected components. Since G is biconnected, these form a "chain" between i[ and i"), ii is a bolt, and the proof is complete. • A direct consequence of the above is that, for a rim or a one-rim G , the flow on the expansion arc e"i in the expanded graph G defined in Theorem 19 is a linear function of the quantity ax, say, x g l = /3ctx + 7. Therefore any additional constraint of the form ty(ax) = 0, where ^ is any real-valued function, can be incorporated into the cost-function by expanding one of the bolts and setting the cost of the flow on the arc e~\ to zero whenever ^((xS l — 7) / /?) = 0, and to +00 otherwise, resulting in an unconstrained network flow problem on G. Notice that the above family of constraints includes inequality constraints, for ax < 0 (resp., > 0) is equivalent to \P(ax) = 0, where ^(z) = 0 if z < 0 (resp., > 0) and vj(z) = 4-00 otherwise. Spec i a l T y p e s o f C o n s t r a i n t s In [K177], it is shown that the singly-constrained linear network flow problem is equivalent to an unconstrained problem on an expanded graph if the constraint is a sum of flows associated with arcs all directed into or all directed away from a single node. As a consequence of Theorem 19 and the above remark on inequality constraints, the procedure presented here covers all such cases, and carries the transformation a step further by disconnecting the rim components when the additional constraint is of the equality type. M u l t i p l e C o n s t r a i n t s If the original problem includes several additional constraints, our procedure can be applied successively to each of them. It is then necessary that the SCMF obtained by keeping only the first constraint be equivalent to an unconstrained problem, which in turn, together with the second constraint, is also equivalent to an unconstrained problem and so on. It is important to remark that the order in which the constraints are Chapter 3. Transformation to an Unconstrained Network Flow Problem chosen may influence the outcome of the decomposition. We are now studying the constraint case. Chapter 4 Ripples, Complements and Substitutes Chapter Abstract We extend the qualitative theory of sensitivity analysis for Minimum-Cost Flow Problems presented by Granot and Veinott [GV85] to Minimum-Cost Flow Problems with one addi-tional linear constraint. The departure from the unconstrained network structure is shown to have a profound effect on computational issues. Two natural extensions of the less-dependent-on" partial ordering of the arcs are presented. One is decidable in linear time while the other yields more information but is NP-complete in general. The Ripple The-orem gives upper bounds on the absolute value of optimal-flow variations as a function of variations in the problem parameter. The Theory of Substitutes and Complements presents necessary and sufficient conditions for optimal-flow changes to consistently have the same (or the opposite) sign in two given arcs. The complexity of determining Substitutes and Complements is shown to be NP-complete in general. However, for all intractable problems, families of cases arise from easily recognizable graph structures and can be computed in lin-ear time. The Monotonicity Theory links the changes in the value of the parameters to the change in the optimal arc-flows, and bounds on the rates of changes are discussed. • • • * 4.1 Introduction In this chapter, we turn to the parametric version of the Singly-Constrained Monotropic Network Flow Problem (SCMF) discussed in chapter 3 in order to study sensitivity analysis for such problems. We are interested in the response of optimal solutions and optimal values 59 Chapter 4. Ripples, Complements and Substitutes 60 to modifications in costs (for instance alternative pricing, varying taxes, profit margin) or in upper/lower bounds (recall that these are incorporated in the objective function). These variations will, in our context, be viewed as changes in cost-function-parameters. To that end, we associate with each arc tj € E a parameter tj in a lattice Tj (for background on lattices and lattice programming, see e.g. [CD73,Vefo.]), and a cost bj(xj,tj) which incurs when the flow and parameter of arc ej are respectively ij and tj, and &,(-, •) is a + 0 0 or real-valued function on 3ft. The m-vector t = (tj)ej^E is called the parameter vector and lies in the lattice product T = x^ e-E^'- The cost of a flow x = (ij) 6 3ftm is the sum of the cost functions on all the arcs of the graph. The problem to be discussed in this chapter is that of finding a flow with minimum total cost that meets the constraint, for a given parameter vector. Explicitly, the Parametric Singly—Constrained Monotropic Network Flow Problem ( P S C M F ) , also referred to as the Constrained Problem, can be written as m p(cx,a0,ty. Mm E M 1 ; ' * ; ) 3 = 1 s.t. Ax = d ctx — ao. We will denote by X(t) the set of optimal flows of P(a,a0,t). A problem similar to the above, but without the additional constraint, will be referred to as the Parametric U n -constrained Monotropic Network Flow Problem, or simply as the Unconstrained Problem. The usual non-negativity and upper/lower bound constraint(s), if any, are natu-rally incorporated into the cost-function by setting bj(xj,tj) to + 0 0 for all forbidden values oixj. Qualitative sensitivity analysis and the study of substitutes and complements (terms defined in section 4.3) for the unconstrained case was the objective of [GV85]. Here, however, the additional linear constraint partially destroys the attractive features and some of the results obtained for pure network flow problems. The cost function is, for most results, required to be convex in the arc-flow, and may reflect real costs, upper and/or lower bounds. The sensitivity analysis is performed by modifying the parameter associated with one or Chapter 4. Ripples, Complements and Substitutes 61 several given arcs. Any variation of the cost structure can be represented in this fashion. Our results are concerned with the "reactions" of the optimal flows to such changes. For applications, such parameter variations may for example reflect changes in upper and/or lower bounds, additive or multiplicative increases in cost, pricing alternatives, technological advances, discounts, or even simulate the deletion/addition of an arc. In the case of multiple optima, our results are valid for at least one of the possible optimal flows. The chapter is organized as follows. Section 4.2 focuses on bounds on the magnitude of change of the optimal flow in two given arcs, the main results being given in the Rip-ple Theorem (Theorem 21). To that end, we define two partial orders on the set of arcs, the l e s s-dependen t-on relation and the quan t i t a t i v e l y- l e s s-dependen t-on relation, as well as a coefficient Mjk which is associated with each pair of arcs (ej, e*). Computational issues associated with the partial orders and the coefficients Mjk are discussed. In section 4.3 we introduce the notions of complements and substitutes pairs of arcs and present a result on the direction of changes in the optimal arc-flow for such pairs of arcs in Lemma 25. Com-putational complexity is again addressed. The Monotonicity Theory presented in section 4.4 relates and compares the rate of change in the optimal flow of a given arc to that of another arc's parameter when the two arcs are either complements or substitutes, a result stated in the Monotone Optimal-Flow Selection Theorem (Theorem 31). The Smoothing Theorem (Theorem 33) provides an upper bound on the maximum arc-flow change over the network in terms of £ i~norm of the corresponding parameter variation. Finally, Theorem 34 shows the subadditivity property of the minimum cost. 4.2 T h e R i p p l e T h e o r e m F o r C o n s t r a i n e d G r a p h s . We study in this section the effect of a change in the parameter of a given arc, in a constrained network, on the flow throughout the network. We show that the magnitude of the change in any arc depends on how "dependent" (a term to be defined later) the arc is with the arc whose parameter is being changed. First observe that, as a direct result of the problem decomposition presented in Chapter 3, changes in a parameter associated with an Chapter 4. Ripples, Complements and Substitutes 62 arc in a given dependent component will not affect the optimal flows in arcs belonging to other dependent components. More precisely, if x is an optimal flow for P(a, cto,t), and if t and t' differ only in their j t h entry, then there exists an optimal solution x' to P(a,aQ,t') such that i j = x\ for any arc ej that belongs to a dependent component that does not contain ej (equivalently, whenever e,- and ej are independent). In the following, the effects of changes within a given dependent component will be studied. Recall from Section 3.3 that the dependent components of a constrained graph as obtained from its biconnected components can be classified as follows. Type (I) Each neutral biconnected component is a dependent component. Type (II) If the number of active biconnected components is at least 2, then the subgraph of G composed of all of the active biconnected components forms one dependent com-ponent. Type (III) If a unique biconnected component is active and is neither a rim nor a one-rim, then it is also a dependent component in itself. T y p e (IV) If a unique biconnected component is active and is a rim (resp., a one-rim) then each of its (resp., its unique) rim component(s) is a dependent component. Moreover, the components of G thus obtained have no nodes in common. Now, if the dependent component in question is of type (I) or type (IV), then the as-sociated subproblem is unconstrained, and therefore one can apply the qualitative theory developed by Granot and Veinott [GV85] for Unconstrained^Monotropic Network Flow Prob-lems. We will thus assume in the following that G has a single dependent component which is either of type (II) or type (IH), that is, where G is composed of either several or of a unique active biconnected component(s). In order to study and compare effects of changes in one arc's parameter over other arcs, we now introduce two partial-orders on the set of arcs E. Chapter 4. Ripples, Complements and Substitutes 63 4.2.1 Less-Dependent-On Relation Let G = (N, E, a) be a constrained dependent graph of type (II) or (III) and let e,-, ej, e* be arcs in E. We say that e,- is less dependent on ej than is and write e,- <j e* if and only if where H(a) is the set of elementary vectors of the circulation space defined in Theorem 5 and Hj(a) is the set of elementary vectors / which contain a given arc ej. If e; <j tk and One should observe here that the characterization of the equally-biconnected-to equiva-lence relation ==, given in Granot and Veinott [GV85, Theorem 4] for unconstrained problems is no longer valid for constrained networks. There, e, <j tk — e,- is less-biconnected-to ej than ejt is — if and only if every simple cycle which contains e,- and ej also contains e*. They state that in a graph G with no additional constraints two arcs e,- and e* are equally biconnected to a third arc ej if and only if e, = ejt or deleting e,- and leaves G disconnected. Example 5 below shows that this characterization is not valid in the constrained case. Theorem 20 to * follow provides an operational characterization of the less-dependent-on relation. E X A M P L E 5 Consider the graph G with 8 arcs and 6 nodes given in Figure 4-9, with cti = 1/2, Q 6 = 1, a , - = 0 for all i ^ 1,6. Clearly e3 =\ ee, for the only elementary vectors that contain both and ti (resp., e& and e2) are, up to a multiplicative factor, f = 2(ci + e 2 + e3) - (e 4 + e 5 + e6) = (2,2,2,-1,-1,-1,0,0) and g = 2(d + e 2 + e 3 ) -for all / e H(a), fifj ^ 0 fk ? 0 (for all / € Hj(a), / , 0 / * ^ 0). Chapter 4. Ripples, Complements and Substitutes 64 (e6 + 67 + eg) = (2,2,2,0,0, —1, —1, —1), which also contain e 6 (resp., e$) and thus e 3 <\ e& (resp., e 3 > 2 t$). However, deleting e 3 and e$ leaves a connected graph. • Figure 4.9: Equally dependent pairs of arcs need not disconnect the graph T H E O R E M 20 Let G = (N,E,a) be a constrained dependent graph and let e,, ej and ek be arcs in E. Then e,- ek if and only if deleting ek leaves e, and ej independent. P R O O F . The proof is a straightforward application of the definition of the Less-dependent-on relation, and is added for completeness. Define G' as the constrained graph obtained by deleting ek and H'(a) to be the set of elementary vectors of the constrained circulation space of G'. It follows trivially from the definition of elementary vectors that H'(a) = {/E H(a) : fk = 0}. Now, e,- <f ek if and only if V / € i T ( a ) , fifj^O => fk?0 or equivalently VfEH(a), / t = 0 => fifj = 0 which is the same as Chapter 4. Ripples, Complements and Substitutes 65 V / € / T ( a ) , / , / , = ( ) completing the proof. • Note that Theorem 20 provides a linear time algorithm to verify whether three arcs e,-, ej and ek satisfy e,- <j ek, for it suffices to decompose G\{ejt} into dependent components in 0(m -f n) as described in Chapter 3, and check whether or not e,- and ej are in the same dependent component. We now apply Theorem 20 to obtain a classification of the cases where e,- <j ek holds. In order to do so, we will start with all the possible configurations of a non-dependent graph G\{ek} and investigate the possible ways of adding an arc ek = (ni,n 2) that will result in a dependent graph. For e, <j ek to hold, it then suffices that the arcs e, and ej belong to two different dependent components of G\{ek}. The classes of non-dependent graphs that will become dependent when an extra arc ek is added in an appropriate fashion are described below. We start with the case where G\{ek] is biconnected, and therefore is a rim (e,- and ej belong to two different rim components). • If one (resp., two) of the rim components of G\{ek}, say G' (resp., G', G"), contains (resp., contain) both ni and n 2 , then G is dependent if and only if ek does not close a neutral cycle in G' (resp., in G' or in G"). For otherwise G would be a rim and G ' U { e J f e } (resp., G'\J{ek) or G"\J{ek}), one of its rim components, contradicting the fact that G is dependent (notice that, since G' is neutral, one of the cycles that ek closes in G' is neutral (resp., active) if and only if so are all the cycles that ek closes in G') (see Figure 4.10-(i)) . • If none of the rim component of G\{ek} contains both ni and n 2 , then let c be any active cycle of G\{ek} that contains ni and n 2 , and write c = pi — p?, where px and pi are two arc-disjoint oriented paths from n 2 to n\. Notice that ac = api — ap2 ^ 0, and since G\{ek) is a rim, the set {ap\,ap2} does not depend on the choice of the active cycle c. Now, since Gr\{ejt} contains active cycles, so does G, and thus G is dependent if and only if it is not a rim, that is, if both cycles ek + pt and ek + p 2 are active or, equivalently, if a* £ {api^ap^} (see Figure 4.10—(ii)). Figure 4.10: Construction of the dependent graph G when G\{ek] is a rim We now turn to the case where G\{ek] has several biconnected components, say G\, • • •, Gi, and since G\{ek) is not dependent, then at least one of these, say G i , is neutral (e,- and ej belong to different biconnected components, and at most one of them to an active one). In the following we will use the fact that if an arc ek is added to a neutral (sub-)graph G', then G ' U ( e J f e } is either neutral or one of its biconnected components, which contains e^ , is a rim for all the active cycles go through ek. Therefore, if G' is neutral, G'\J{ek} is active if and only if all the cycles that contain ek are active. • Let us first assume that one of the biconnected components of G\{ek) contains both ni and n 2 . Clearly, it has to be a neutral one, say G\, and the cycles created have to be active, for otherwise G\ would be a neutral biconnected subgraph of G, that is, a dependent component, and G would not be dependent. (From the above remark, Gi U{e*} is then a rim with bolts ni and n 2 and rim components G\ and {e^}.). Moreover G 2 , • • • , G/ need to be active and thus G\ is the unique neutral biconnected component of G\{ek} (see Figure 4.1 l-(i)). Chapter 4. Ripples, Complements and Substitutes 67 Figure 4.11: Construction of the dependent graph G when G\{ek) is not bicon-nected Chapter 4. Ripples, Complements and Substitutes 68 • In the following we assume that none of the biconnected components of G\{ek} contain both ni and n 2 . Recall that we assumed G to be of type (II) or of type (in). If G is of type (II), then all the arcs that lie in neutral biconnected components of G\{ek} belong to some active cycle in G, and therefore to some cycle that contains ek, so that all the neutral biconnected components of <j\{e*} are part of a single biconnected component of G. Thus several, but not all, of the biconnected components of G\{ek}, including all the neutral ones, form a chain, and n\ (resp., n 2) belongs exclusively to the first (resp., last) of these subgraphs (see Figure 4.11—(ii)). If on the contrary G if of type (III), the above remark holds but we require that all the biconnected components of G\{ek] be part of the chain and at least one of them be active, for otherwise G would be a rim (see Figure 4.11-(iii)). 4.2.2 Q u a n t i t a t i v e L e s s - D e p e n d e n t - O n R e l a t i o n For any three arcs e,, ej and ek in E we say that e, is (resp., s t r i c t l y ) q u a n t i t a t i v e l y less d ependen t on ej t h a n ek is and write e, <* ek (resp., e, <] ek) if and only if for all / <E H(a), / , / , ^ 0 => | / , | < | /* | (resp., | / , | < |/fc|) or, equivalently, if |/,-| < |A| (resp., |/,-| < |M) for all / G Hj(a). If ei <' ek and ek <' e, we say that e, and ek are q—equally d e p e n d e n t on ej and write e,- =' tk. Clearly, e, =' ek if and only if for all / £ Hj(a), = One can easily see that the quantitative dependence relation is again a partial-order and hence =' is an equivalence relation. The corresponding sets of q-equ iva lence classes S] induced by it are partially ordered by <'. We will denote by S](k) the unique element of £ ' that contains arc ek. Notice that in the unconstrained case H(a) reduces to the set of simple cycles, and thus both the less-dependent-on and the quantitatively-less-dependent-on relations are equiv-alent to Granot and Veinott's [GV85] less-biconnected-to relation (where <j ek if and Chapter 4. Ripples, Complements and Substitutes 69 only if any simple cycle that contains and ej also contains e*). In that sense they both constitute genuine extensions of the Granot and Veinott notion. However, it will be shown in example 6 to follow that in the constrained case they are no longer equivalent. Clearly, for e,-,ej and e* 6 E, if ti <* e* (resp., e,- e*) then also e,- <j e* (resp., e,- =j ek). This implies that £ ' ( i ) C £j(i) for all e,- 6 E, but the reverse inclusion is generally not true, as can be seen from the following counter example. E X A M P L E 6 Consider the graph given in Figure 4-12 with the additional constraint Figure 4.12: does not imply =' For any circulation x £ C(a), Xi = 2x? by the constraint and x2 = x 3 by the configuration of the graph. Therefore for any elementary vector f £ H(a), fi = 2f2 and f2 = /3. Hence, ei = 2 e 3 but e\ 7^2 e 3 - E One should also notice that in contrast with the unconstrained case where the greatest element in the partial order <j always contains arc ej, in the constrained case one can encounter examples for which there exists an arc such that ej <' e^ . In particular, this may happen if the constraint is of the form Xj + ctkXk = ao and |ajt| < 1. 4.2.3 The Ripple Theorem We are ready now to present the Ripple Theorem that will give some characterization of the change in the optimal solution to a Singly-constrained Monotropic Network Flow Problem resulting from a change in the parameter of one arc. Chapter 4. Ripples, Complements and Substitutes 70 T H E O R E M 21 The Ripple Theorem. Let G = (N, E, a) be a dependent constrained graph of type (II) (i.e., several active biconnected components) or type (IH) (a unique active biconnected component which is neither a rim nor a one-rim) and suppose that t and t' differ only in one component ej 6 E, bk(-,tk) is convex for each ek € E\£j(j), x is an element of X(t) and X(t') is nonempty. Then there exists x' £ X(t') such that (R . l ) x' — x is a sum of conformal elementary circulations, each of whose support contains arc tj. (R.2) D - R i p p l e Property: For any two arcs e, and ek in E, if e,- <j ek then Wi-XilKMkilx't-Xk] (4.6) where. Mki = max{|/,/M : / e Hk(a)}. (4.7) (R.3) Q—Ripple Property: \x'k — xk\ does not increase the less quantitatively dependent ek is on ej. P R O O F . Part (R.l) follows by using Rockafellar's Harmonious Superposition Theorem described in Chapter 2 and the convexity of the cost functions as was done by Granot and Veinott in [GV85]. The proof is included for completeness. Suppose x' is an element of X(t'). Then x' — x is a sum of conformal elementary circulations. Let y be the sum of the conformal elementary circulations whose support contains ej and z the sum of the remaining elementary circulations. Then y and z are conformal and zk = 0 for all k G £f{j) since, by definition, any elementary support that does not contain ej does not contain e* either whenever ek =j ej. Therefore, by the convexity hypotheses, b(x + y, t') + b(x + z, t') < b(x, t') + b(x\ t') (4.8) where b(x,t) = YXLi bi(xi, ti). Moreover, since the parameter change involves ej only and ZJ = 0, b(x + z,t') - b(x,t') = b{x + z,t)- 6(x,t). (4.9) Chapter 4. Ripples, Complements and Substitutes 71 Combining (4.8) and (4.9) one obtains b(x + y,0 + b(x + z,t)< b(x,t) + 6(x',t'). Hence, x + y G X(t') and x + z E X(t), because x' G X(t') and x 6 X(t). Therefore, x + y is optimal for t' and (R.1) holds. In the remainder of the proof, we will assume that (R.l) holds. In order to show (R.2) assume that e,-,e* G E and that <^ e*. From (R.l) we can write x' — x = E z < , / ° where za > 0 for all a (4.10) / a conformal and, from the conformality of the sum, \x't-xt\= E *«!/»< I for all*. (4.11) conformal Moreover, <j ek implies that fai = 0 for all elementary vector /„ G Hj(a)\Hk(a) and, by the definition of Mki, \fai \ < Mki\fak \ for all fa G Hk(a). Thus, conformal conformal conformal -E / o 6 H > ( a ) n H k ( Q ) conformal < E * . M « I / . J = E ^ M « i / e j = M « | x i - * * l Z a 6 l f j ( « ) n H t ( « ) faZHj(a) conformal conformal completing the proof of (R.2). To prove (R.3) we need to show that for any two arcs e,-, ek G E such that e,- <' ek we have |x- - x,| < |x'fc - xk\. By hypothesis, | / a i| < | / a J for all fa G Hj(a), thus (4.11) yields l * i E E * . l / . J = l * * - x * l (4-12) / a € H j ( a ) faeHj(a) conformal conformal Chapter 4. Ripples, Complements and Substitutes 72 completing the proof of (R.3). • Notice that under the assumptions of the Ripple Theorem, the following special cases are trivial consequences. • If x'k = Xk then x\ = x,-. • Since e,- <j ej for all i, then |zj — x,| < Mji\x'j — Xj\ for all i. • Constant changes in q—equivalence classes. In the unconstrained case, Granot and Veinott showed that, under the assumptions of the Ripple Theorem, the magnitude of the change in optimal arc-flow remains constant over all arcs in a given equivalence class for the less-biconnected-to relation. This property remains valid for the quantitatively-less-dependent-on relation, since if e,- =' ejt, then by definition | / a - | = | / a J for all fa G Hj(a), and thus by (4.11), |x- — x,| = \x'k — Xk\. However this is no longer the case for the less-dependent-on relation as demonstrated in example 7 below. E X A M P L E 7 Non—constant variations in d—equivalence classes. Consider the graph with 7 arcs and 5 nodes given in Figure 4-13, with the added constraint 2x4 + X5 = 3. Let the demand be given by d{ = 0 Vi and the costs by bi(x1,t1) = (x1-t1)2, 6 9(x 7 ,i r) = | x 7 - l | , bj{xj,tj) = 0 V j ^ l , 7 . Figure 4.13: Tight bounds in the Ripple Theorem The assumptions of Theorem 21 are satisfied, and if we further let, for example, t = (0,0, • • • , 0) and t' = (1,0, • • • , 0) then it is easy to verify that X(t) = {x} and X{?) = {x'} Chapter 4. Ripples, Complements and Substitutes 73 where x = (0,0,0,1,1,0,1) and x' = (1,-2,1,2,-1,-2,1). Indeed, zero is a lower bound on the objective value for any value of the parameter, and one can check that both these solutions achieve an objective value of zero, and are unique in that respect. Moreover, e4 and e$ are in the same d-equivalence class £ j ( 5 ) . Indeed, the sole elementary vector / = (ei + e4 -f e3) — 2(e2 + e6 + es) = (1, —2,1,1, —2, —2,0) that contains e± and e4 (resp., ande5) also contains es (resp., e 4 J, and thus e4 =f es. However, \x'4—z4| = 1^2 = \x's—xs\. • Before discussing in subsection 4.2.4 the computational complexity involved in determin-ing the bounds M , * introduced in the Ripple Theorem, we will illustrate in Example 8 that those bounds are indeed the sharpest bounds possible, in the sense that inequality (4.6) in Theorem 21 may be tight. E X A M P L E 8 Tight bounds in the Ripple Theorem. Consider again the graph given in Figure 4-13. The elementary vectors that contain both e\ and e2 are f= (ej + e 4 + e3) - 2(e2 + e 6 + e5) =(1, -2 ,1 ,1 , -2 , -2 ,0) 9= (ei + e 2 + e6 - e7 + e3) =(1,1,1,0,0,1,-1) and thus M12 = max{|2/l|, |1/1|} = 2. Now, if we let t = (0,0,---,0) and f = (l,0,---,0) the unique optimal flows for t and t' are respectively x = (0,0,0,1,1,0,1) and x' = (1,-2,1,2,-1,-2,1) (see Example 7). Thus \x'2 — x2\ = Mi2\x[ — xi\ and the bound given in equation 4-6 is tight. • « 4.2.4 Computing the Bounds in the Ripple Theorem In this subsection we discuss the complexity of computing the coefficients Mjk introduced in the Ripple Theorem. This computation in general turns out to be NP-Hard as shown in Theorem 22. However, we provide in the latter part of this subsection special cases in which a polynomial time algorithm can be derived. Chapter 4. Ripples, Complements and Substitutes 74 T H E O R E M 22 The problem [M] of computing the coefficient Mjk=max{\fk/fj\:feHj(a)} for any given pair of arcs (ej, ek) of a constrained graph G = (N, E, a), is NP-Hard. P R O O F . Assume that there exists an algorithm AI[M] which, given a constrained graph G = (N, E, a) and fwo arcs e3, ek £ E, evaluates the coefficient Mjk, and runs in at most P[M\{S) elementary operations, where P^r](s) is some function of s (recall that s is a measure of the size of the input, see Chapter 2). We show in the following that Al^ can be used to solve an NP-Hard problem, namely the M a x i m u m Weight Oriented Simple Cycle [ M W O S C ] (see [GJ79, p. 213]) [MWOSC] max{\ac\ : c simple cycle of G}. Consider the following construction. For a given graph G = (N, E), an m-vector (Q,),=I M whose entries will be called weights, define the constrained graph G* = (N',E',a*) by N* = NU{n + l,n + 2} E" — E U {e m + 1 = (n + l , n + 2 ) ,e m + 2 = (n + 2,n + 1)} and a' = { cti if i < m —1 if i = m + 1 0 if i - m + 2 and let ek be any given arc in G (See Figure 4.14). Now, since no simple cycle goes through both ek and e m + i , any elementary vector containing those two arcs has to be a weighted sum of two active disjoint cycles, that is, / = ( c m + i + e m + 2 ) + fkc (4.13) where c is an active cycle of G for which ck = 1 and fk is determined by (3.3), resulting in Chapter 4. Ripples, Complements and Substitutes 75 m+2 Figure 4.14: The extended graph G* fk = -a'(em+i + em + 2)/or"c = l/a*c = 1/ac. (4.14) Therefore, for the constrained graph G*, we can write M k m + 1 = mox{\fm+1/fk\: f e H;(a*)} = max{\l/fk\ : ( c m + 1 + e m + 2 + fkc) € ^(a*)} = mai{|acj : ck = 1, c simple cycle of G) where Hl(a') is the set of elementary vectors of the circulation space of G* that contain ek. Thus AI[M] will, when applied to G' and a particular pair of arcs (ej t ,e m +i), determine the oriented cycle of maximum weight that contains arc ek. By repeating the above for k = 1, • • •, m and then selecting the largest of the m optimal values, one solves the [MWOSC] in 0(MP[M](s)). Since the [MWOSC] is NP-Hard, so is [M], completing the proof. • In the following we present five examples where the value of Mjk can easily be computed. For convenience we will assume without loss of generality that all elementary vectors / encountered with fj ^ 0 have fj = 1. Arcs in Rims. In the first part we consider the case where G has several biconnected components, and the biconnected component(s) that contains the arcs ej and ek is a rim (are rims). At this point, it is interesting to notice that a biconnected subgraph, say G\, Chapter 4. Ripples, Complements and Substitutes 76 with a unique arc e,- that verifies a, ^ 0, is a rim whose bolts are the end-nodes of e,- and whose rim components are {e,} and Gi\{ej}. Such subgraphs naturally fall in the category described here. • If at least one of the biconnected components of G, say G\, is a rim, then for every ej, ejt G Gi, the elementary vectors that contain both ej and ek are either simple neutral cycles'of Gi or active cycles of G\ paired with active cycles not in G\. All such elementary vectors verify | / j | = \fk\, and thus Mjk = 1. • If at least two of the biconnected components of G, say G\ and G2, are rims, then for every ej G G\ and ek G G2, any elementary vector that contains both ej and ek is of the form f = c1 + fkc2 where c1 and c2 are respectively active cycles of G\ and G2, c* = c\ = 1 and fk = —acxjct(? as in (3.3). Therefore \fk/fj\ = | ( —ac 1 /ac2)/l\ = {ac1 /ac2\ is independent of the choice of c1 and c2, and Mjk is equal to that ratio. The s u p p o r t o f a on some b i c o n n e c t e d c o m p o n e n t o f G is a p a i r o f arcs . Suppose now that a,- = 0 for all arcs e,-, e, ^ ej, ek and e,- belongs to the same biconnected compo-nent (s) of G as ej or ek. Since the above treats the case where the two ares lie in different biconnected components of G, we may assume that ej and ek lie in the same biconnected component of G. • Let us first assume that G is biconnected but is not a rim (type (in)). Then, any ele-mentary vector which contains both arcs is either a simple neutral cycle (this situation may only occur if \ctj\ = \ak\) or a pair of active cycles, say / = c l — (ac^/ac2)^, and we may assume without loss of generality that cj = c\ = 1 and c\ = cj' = 0. In either case, \fk/fj\ = \aj/ak\, and thus Mjk = \ctj/ak\. Chapter 4. Ripples, Complements and Substitutes 77 • We now suppose that G has several active biconnected components, and that ej and ek belong to one of them, say G\. Along with the elementary vectors described above, we need to consider any active cycle of G\ that contains ej and ek, together with another active cycle in another biconnected component. For such an elementary vector / , \fk/fj\ = 1, and thus Mjk = max{l, \ctj/ak\}. • Notice that in the above two cases, the assumption on the entries of or may be relaxed by only requiring that, among the arcs that lie in the biconnected component Gi of G . that contains ej and ek, only those that are contained in every simple cycle that also contains ej and those that are contained in every simple cycle that contains e*1 may have nonzero entries in a (see Figure 4.15). Indeed, as far as the study of cycles goes, we may replace ctj (resp., ak) by ac, where c is any cycle that verifies Cj = 1 (resp., Cfc = 1), and replace by zero all the other aj's, ej € G\, i ^ j, k. Only bold arcs have nonzero alpha's Figure 4.15: Only bold arcs verify aj ^ 0 JIn a graph G, the set of arcs contained in every simple cycle that contains a given arc ej is the equiv-alence class for the =,• relation denned in [GV85] which contains ej. Alternatively, such an arc, say c,-, is characterized by the fact that {ej} is a biconnected component of G\{ej}, and thus can be detected in linear time. Chapter 4. Ripples, Complements and Substitutes 78 4.2.5 Complexity Issues Attached to the Qualitative Less-dependent-on Rela-tion In this subsection we present a general statement about the complexity of the problem of determining whether e,- <' holds for three given arcs e,-, ej and ek. The computation turns out to be NP-complete for the general case, and we provide again special cases where the answer is tractable. We are thankful to Richard Anstee for suggesting improvements to an earlier version of the proof of Theorem 23. T H E O R E M 23 The problem [QLD] of deciding whether three given arcs e,-, ej and ejt in a constrained network G = (N,E,a) are such that e,- <' ejt is NP-complete. P R O O F . Assume that there exists an algorithm AI^QLD) which, given a constrained graph G = (N,E,a) and a triplet of arcs ei,ej,ek £ E, determines whether e,- <' e*. We claim that AI[QLD] c a tt be used to solve the decision version of the Maximum Weight Oriented Path [ M W O P - D ] defined as follows. Given a vector of weights (wi) £ 3?m, two nodes say n x and n 2 , and a real number A > 0, do all oriented path p from n\ to n 2 verify wp < A ? The [MWOP-D] known to be is NP-complete (see [GJ79, p. 213]). Now, add to G the arc eo = ("2, ni), define the vector a by -2' 2 * - A and consider again the graph G" constructed in the proof of Theorem 22. Apply AI\QLD] to the statement "eo < m + 2 e m + i " . By definition, this statement holds if and only if, for any elementary vector / of G* which contains both e0 and e r n + 2 , | / 0 | < | / m + i | - From (4.13) and (4.14), this is equivalent to |l/a*c| < 1 for any active cycle c of G* that contains e0, that is, \ac\ > 1 for all active cycles of G that contain e0. This is trivially equivalent to \ac\ > 1 Chapter 4. Ripples, Complements and Substitutes 79 for all cycles c of G with Co = 1. Since such a cycle is of the form c = en + p, where p is an oriented path from n x to n 2 , we can write that AI^QLD] will return a YES if and only if for all oriented paths p from ni to n 2 . Now, since |tuc| < 2*, (tup — 2") > 1 and thus wp < X for all path p from rti to n 2 , solving the [MWOP-D]. Since the reduction from one problem to the other is clearly linear, the proof follows. • Recall from Subsection 4.2.1 that e, <' ek =>• e, <^ e*, and thus the list of configurations for which e,- <j ek does not hold (see Subsection 4.2.1) also applies here. We now provide some cases in which one can easily decide whether e, <' ek does hold. In order to do so, we prove the following lemma. L E M M A 24 Let G = (N,E,ct) be o constrained graph and ej,ek, two arcs in G. Then every active cycle of G which contains ej also contains ek if and only if the biconnected component of G\{ek) that contains ej is neutral. PROOF. First, every active cycle of G which contains ej also contains ek if and only if ej does not belong to any active cycle in G\{ek) or, equivalently, if ej does not belong to any active cycles in the biconnected component of G\{ejfc} in which it lies. The result follows from Lemma 7 in Chapter 3 which states that a biconnected graph with at least two arcs is active if and only if every arc belongs to an active cycle. • • 1» G has at least two biconnected components, one of which, say Gu 1S a r i m - Then for any e,-,et G G\ and ej which does not belong to the rim component of Gi that contains e,, any elementary vector that contains both a and ej is of the form given in (3.3) where c1 is an active cycle of G\ that contains e,- and c 2 is some active cycle of G \ G i (if tj € G\ then c1 contains ej, otherwise c2 does). Conversely, any active Chapter 4. Ripples, Complements and Substitutes 80 cycle c1 in G\ which contains tj can be completed into an elementary vector that contains e,- as well. Clearly, such an elementary vector contains tk if and only if c1 does, and thus e, <j tk if and only if every active cycle of G\ which contains ti also contains e*. From Lemma 24, this holds if and only if the biconnected component of G\{ek} that contains tj is neutral. The possible configurations are given in Figure 4.16 where tj may .belong to G\ (t) or to G\G\ (it). Since it follows from the above that [/,-1 = \c)\ = |/jt| = \c\\ = 1, then e,- <' ek holds whenever e,- <j ek does. Other Biconnected Figure 4.16: e,- <j tk •2» G has exactly two biconnected components which are both rims, say Gi and G2- Then for every e, G G\, tj,ek 6 G2, any elementary vector that contains both e,- and e7 is of the form given in (3.3), where c1 and c2 are respectively active cycles of Gi and Chapter 4. Ripples, Complements and Substitutes 81 (j2- Therefore e,- <j ek if and only if every active cycle of G2 which contains ej also contains e*. The two possible configurations are given by Lemma 24 (see the subgraph Gi in Figure 4.16, (i), (ii) ). For e, <' e* to hold, we require the additional condition that I/, I < |/jt| whenever fj ^ 0, which from the above is equivalent to lac2! — Icrc1 j. 4.3 Complements and Substitutes in Constrained Network Flows In this section we define the concepts of complements and substitutes for constrained networks. These notions are crucial to the development of the Monotonicity Theory in section 4.4. The definition of substitutes and complements as given in [GV85] only involved the topology of the graph. Indeed, for the unconstrained network flow problem, two arcs are complements (resp., substitutes) if and only if every simple cycle in the network orients them in the same (resp., in opposite) direction(s). Here, the side constraint ax = a0 comes into play through the elementary vectors, as will be seen in the definition below. Some preliminary results on comparative flow changes between two arcs that are substitutes or complements are given here. However, Theorem 31 in section 4.4 will show the central role played by substitutes and complements in predicting flow changes in a given arc resulting from changes in the parameter, and thus in the cost function, of another arc. We further show here that the problem of determining whether two given arcs are substitutes, complements, or neither is, in general, NP-complete. We then point out particular classes of instances of that problem where a fast solution (where polynomial time algorithms such as Decomposition into Biconnected Components or Rim Recognition suffice) is provided. Two arcs e, and ej in a constrained graph G = (N, E, a) are said to be complements (resp., substitutes) if and only if for all elementary vectors/ 6 H(a), fifj > 0 (resp., < 0). (4-15) (Recall that H(ct) is the set of all elementary vectors of the constrained circulation space.) Chapter 4. Ripples, Complements and Substitutes 82 E X A M P L E 9 In the graph given in Figure 4-17 one can see that e\ ande2 are complements, for the elementary vectors that contain them both are f1 = (ci + e2 + e3) - l/3(e 6 + e5 - e4) P = (el + e2 + e3) + l/2(c 7 + c 1 0 + c8) P = (d + e2 + e3) + l/4(e 7 + e 1 0 + c u + e9) / 4 = (ea + e2 + e3) + l /2 ( -e 8 + e9 + e u ) / 5 = (ci + e2 + e3) + l/2(e 7 + e 1 2 + e9) f6 = ( e i + e2 + e3) + l/2(e 1 0 + e u - e12) 5 i i — 2x7 — 2xn •+• 3x5 = 2 Figure 4.17: Subs t i t u t e s a n d c o m p l e m e n t s i n a c o n s t r a i n e d g r a p h and one can check that f[f\ > 0 for i = 1, • • •, 6. Similarly (ei, e7) and (ei, e n ) , for instance, are other pairs of complements whereas (t\, es) is a pair of substitutes. • In order to further motivate the interest in arcs that are complements and substitutes notice that, under the assumptions of the Ripple Theorem, if, in addition, the arc tj whose parameter is being changed and another arc e,- are complements (resp., substitutes), then (x'i - x,)(x; - X j ) > 0 (resp., < 0). This is a straightforward consequence of (4.10) and the fact that, by the definition of com-plements (resp., substitutes), faifaj > 0 (resp., < 0) for all fa G Hj(a). Stronger results will be presented in Theorem 31 of section 4.4 and in Lemma 25 to follow. It is also interesting to notice that, although it was shown in Subsection 4.2.3, that optimal arc-flow changes Chapter 4. Ripples, Complements and Substitutes 83 are not constant across d-equivalence classes, one can predict the comparative direction of changes as shown below. L E M M A 25 Variations in pairs of complements and substitutes. Let G = (N,E,a) be a dependent constrained graph and suppose that t and V differ only in one component ej E E,Jbi(-,U) is convex for each e\ E E\Sf(j)', x is an element of X(t) and X(t') is nonempty. Then there exists x' E X(t') such that for any e* E £f(j) we have Complementarity Property: (x\ —Xi)(x'k —Xk) > 0 (resp., < 0) (4.16) whenever d and are complements (resp., substitutes). PROOF. If (x\ — Xj)(x^ — Xfc) = 0 the proof is complete. Otherwise, notice that Hj(a) fl Hi(a) = Hj(ct) D Hk(a) whenever ej =j e^ , and we will denote this set by Hijk- For the optimal flow x' E X(t') defined in Theorem 21 by (4.10) we obtain (x'i - Xi)(x'k - xk) = ( £ 2afai)( E z°f°*) conformal conformal = ( £ *./«.•)( £ Zafa„) conformal conformal where all the terms in both sums are nonzero and za > 0 for all /„ E H^k- By conformality, all the terms in the first sum are of the same sign, and so are the terms in the second sum. Now, since e,- and ej are complements (resp., substitutes), these signs are the same (resp., opposite) and the proof follows. • • In view of the above two results it is natural to ask whether the property for a pair of arcs to be complements or substitutes is transitive. This is in general not true, as was shown by Granot and Veinott [GV85] for the unconstrained case, and thus for the constrained case as well2. Still, in the unconstrained case, every pair of arcs in an equivalence class of the 2 Counter examples for the unconstrained case are given in [GV85]. For an example specific to constrained networks, refer to Figure 4.17 where (e7, ei) and (ci, en) are pairs of complements, but e7 and en are neither complements nor substitutes, for the elementary vectors f1 = 4(ei + e2 + + (e7 + eio + en + eg) and / 2 = (e7 + e i 2 — en + es) orient them respectively in the same and in opposite directions. Chapter 4. Ripples, Complements and Substitutes 84 less-biconnected-to relation defined therein is either complement or substitutes. This result does not hold either for constrained networks, for instance in Figure 4.17 ej en, e7 =\ en but er and en are neither complements nor substitutes. (Indeed, the elementary vectors / = (ei + e2 4- e3) + l/4(e 7 + ei 0 + en + e9) and g = (er + e 1 2 — en + eg) orient them in opposite directions.) The following result, however, shows that under certain assumptions, some form of transitivity holds, in particular when the arcs involved belong to the same d-equivalence class. L E M M A 26 Conditional transitivity of Complements and Substitutes. Let e,, ej and ek be three arcs in a constrained dependent graph G = (N, E,a), and suppose that fij e,- and ej are complements, [ii] e,- and ek are complements (resp., substitutes), and [iii] ek <j e,3. Then ej and ek are complements (resp., substitutes)*. P R O O F . Let / 6 H(a), and suppose that fjfk ^ 0. By [iii] f{ ^ 0, and thus by [i] and [ii] / ,/ ,• > 0 and /,•/* > 0 (resp., < 0). Therefore sign(fjfk) = sign(f?fjfk) = sign(fifj)sign(fifk) = 1 (resp., —1) (Where the real-valued sign function is naturally de-fined by sign(z) = 1 if z > 0, — 1 if z < 0, and sign(0) = 0), completing the proof. • T H E O R E M 27 The Complexity of Determining Substitutes and Complements. The problem of determining whether a given pair of arcs of a constrained graph G = (iV, E, a) are substitutes, complements or neither is NP-complete. P R O O F . We show here that the simpler decision problem of determining whether or not two given arcs are "neither substitutes nor complements", denoted by [DN], is N P -complete. Assume now that there exists an algorithm, say AI^DN], which when applied to the constrained graph G = (N,E,a) and a pair of arcs (e,-, e*) answers the above question in, say, 0(P[r)N](s)) elementary operations. Now, given a constrained graph G = (N,E,a) 3In particular, [iii] holds if e, and are in the same d-equivalence class for 4If ti and ej are substitutes, then trivially a similar result holds, in which the conclusions are reversed. Chapter 4. Ripples, Complements and Substitutes 85 and a particular arc ek G E, construct the graph G* as in the proof of Theorem 22 (See Figure 4.14), and apply A1[ON] to the pair of arcs e*, e m + i . Now, from the definition of substitutes and complements, the answer to [DN] is YES if and only if there exists a pair of elementary vectors, say /+ and / " of H(ct) such that fm+i = fm+i = 1, /fc" > 0 and fa < 0. From equations (4.13) and (4.14) one obtains that / + = (em+i + e m + 2 ) + ( l / ac + ) c + and / " = ( e m + i -f e m + 2 ) + (l/ac~)c~ where c + and c~ are active cycles of G with cj = ck = 1. Moreover, f t = ( l / a c + ) c £ > 0, fu = (l/ac")c^ < 0 ==> ac+ > 0 and ac~ < 0. Thus AI[DN] will, in 0(P[DN]($)) elementary operations, determine whether the above two cycles exist simultaneously. We now show that AI[DN] can be used to solve the recognition problem associated with the Maximum Weight Oriented Simple Cycle Problem [MWOSC] in time polynomial in P[DN]{3)-In order to do so, first notice that the set {ac : c is a cycle in G, c*. = 1} has a smallest element, say Ai, and a largest element, say A 2 , and a rough upper bound on their magnitudes is given by |Ajt| < 2" for k = 1,2. Moreover, if A1[DN] is applied to the graph obtained by replacing in G* the quantity or* by (a* — A) for some A £ 3J, then the answer will be YES if and only if there exists two cycles c + and c~ in G such that ac+ > A and ac~ < A, that is, if and only if Ai < A < A 2 . Since an initial element of the interval (Ai, A 2) can be obtained in linear time by finding any cycle that contains (complete by any simple path joining its head to its tail using depth-first search), it is possible to uge binary search over the interval [—2*, 2*] in order to determine both Ai and A 2 , and thus X(k) = max{ac : c cycle in G,ck = ± 1 } = max{|Ai|, |A2|}. The time required to do so is 0(log22aP[DN]{S)) =0(SP[DN](S)) (see [GJ79,PS82] for the running time of binary search). By repeating the above procedure for k = l , . . . , m , one obtains max{A(fc) : k = l , . . . ,m} = max{ac : c cycle in G} in 0(msP[rjN](s)) elementary operations, proving our claim. Since [MWOSC] is NP-complete, so is [DN], and the proof is complete. • Chapter 4. Ripples, Complements and Substitutes 86 There are, however, some cases in which one can determine whether two arcs in a con-strained graph G = (N, E, a) are substitutes or complements with little computation. More-over, the question of whether a given instance of the above problem is one of these special cases can be answered in linear time by well known graph algorithms. The following three examples illustrate this fact. a) "Parallel" ar*cs. Suppose that the set of nodes N / <f> can be partitioned into two subsets say Ni and N2 with TV = Ni U N2 and NiD N2 = <j> and that there exists a unique pair of arcs say (e,-, ej) joining Ni and N2 with e; = (a,-,o;) and ej = (a,-,6j) (resp., (bj, a.j)) with a,, a, 6 N\ and bj G N2 as is illustrated in Figure 4.18.a. In this case clearly for any circulation x in G we have X{ = — Xj (resp., x, = Xj) regardless of the fact that the network may have some constraints. Therefore, the same will hold for the elementary vectors of the circulation space C(a). Thus, for all / G H(a), /,• = — fj (resp., f = fj), and the arcs e, and ej are substitutes (resp., complements). b) "Series" arcs. A simple extension of the above result is the case where the set of nodes can be partitioned into say k subsets so that TV = Ni U N2 • • • U Nk with TV* H TVm = <j> for I y£ m G {1,..., k) and where there exists a unique arc e/ between some node in Nt and another in A ^ + i for all £ = 1,..., — 1, a unique arc ek between some node in Nk and another in iVi, and no other arc joins any node in TV, with any node in Nj, i ^ j = 1,..., k. This situation is illustrated on Figure 4.18.b. We can then condense the subsets Ni,... ,Nk each into a single "supernode" and obtain a simple cycle (see Figure 4.18.c). By the same argument as above two arcs of the subset {ei,..., ek) are complements if they are oriented bythis cycle in the same way, and substitutes if they are oriented by it in an opposite way. For any elementary vector of the circulation space / G H(a), we clearly have, = | / 2 | = . . . = \ fk\ and therefore the arcs t\,..., ek are all in the same equivalence class for both the dependence and the quantitative dependence relations. c) Arcs with common degree-two nodes. Suppose now that the arcs and tj are Chapter 4. Ripples, Complements and Substitutes 87 in series, i.e., have a node in common, say a E N, and no other arc is incident to a. We can apply a) to this case by considering the subsets iVi = {a} and iV2 = iV1\{o} and assert that ei and ej are either substitutes or complements. This is illustrated in Figure 4.18 (d-e). W) (e) Figure 4.18: Substitutes and complements For the following cases we require some additional definitions. An arc e,- in a rim G is a positive (resp., negative) rim arc if and only if every positive rim cycle c verifies Ci > 0 (resp., < 0). Lemma 28 to follow provides a characterization of such arcs using the * construction we describe now. Let G be a rim, e, an arc in one of the rim components of G, say G', and c any positive rim cycle. Define the unconstrained graph T(G') = G'{J{eo} where eo joins the two bolts of G', say ni and n 2 , and is oriented from n\ to n 2 if so is the part of c that lies outside of G' (see Figure 4.19). Note that T(G') does not depend on the choice of c. e. Figure 4.19: The r im G (left) and the constructed graph T(G')(right) L E M M A 28 Characterization of positive r im arcs. Let G = (N, E, a) be a rim, G' one of its rim components, and e,- an arc in G'. Then e,- is a positive rim arc if and only if ei and eo are complements (resp., substitutes) in T(G') in the sense defined by Granot and Veinott in [GV85]5. P R O O F . First recall that any positive (resp., negative) rim cycle c in G goes through all the bolts and through all the rim components, and thus corresponds to a cycle of T(G') which contains e0 as a forward (resp., backward) arc, the correspondence being obtained by replacing the part of c which lies outside of G' by e0 (resp., —e0). Therefore, every positive rim cycle verifies Ci > 0 (resp., Cj < 0) if and only if so does any active cycle in T(G') which verifies = 1. Moreover, if is a negative rim cycle then — is a positive rim cycle, the above applies, and the proof follows. • The first consequence of Lemma 28 is that one can verify in linear time whether a given arc is a positive rim arc, a negative rim arc, or neither. This observation is now used in the following to identify rim arcs which are substitutes or complements. d) Arcs in a r im. Suppose that G is of type (II) and that one of its biconnected components, say G\, is a rim. Then any elementary vector with arcs in Gi is either a neutral cycle of G\ or a pair of active cycles, one in G\ and the other in G\GX. Therefore 5That is, if any oriented cycle in T(G') orients ei and eo in the same (resp., in opposite) direction. Chapter 4. Ripples, Complements and Substitutes 89 any two arcs et- and ej in G\ are complements (resp., substitutes) if and only if any cycle c of G\ verifies C j C j > 0 (resp., < 0), that is, if the two arcs are complements (resp., substitutes) in the sense defined by Granot and Veinott for unconstrained graphs. This can be done in linear time [GV85]. Using similar arguments to those used in the proof of Lemma 28, one can show that two arcs in the same rim component G' of G\ are substitutes (resp., complements) if and only if they are substitutes (resp., complements) in T(G'1). Moreover, if the two arcs lie in different rim components of G\, say G' and G", then any cycle that contains them both is active, and therefore they are complements (resp., substitutes) if and only if they are both positive or both negative rim arcs (resp., one is a positive and the other a negative rim arc). In particular, it is a simple consequence of the topology of rims that two arcs which belong to different rim components and each are incident to a bolt (not necessarily the same bolt) are conformal. e) Arcs in two rims. Suppose that G is of type (II), that two of its biconnected components, say Gi and G2, are rims and that e,- € G\ whereas ej £ G2. Then any elementary vector that contains both e,- and ej is of the form / = c1 — (ac1 /ac2)c2 where c1 and c2 are respectively positive rim cycles of Gi and G2. Therefore, e,- and tj are complements (resp., substitutes) if and only if they are both positive or both negative rim arcs (resp., one is a positive and the other a negative rim arc), and the above remark on arcs incident to bolts also holds. It is important to notice at that point that in contrast with the unconstrained situation [GV85] where it is sufficient for two arcs to be incident ffo the same node in order to be substitutes or complements, here we also require the common node to be of degree 2 (unless the arcs belong to rims, as shown above). The following example illustrates the fact that the degree requirement is indeed necessary. Chapter 4. Ripples, Complements and Substitutes 90 E X A M P L E 10 Consider the constrained graph G = (N, E, a) given in Figure 4-20 with the additional constraint 2x i + 3 x 2 — 10^6 = 2. Then /* = (ei + e 4 - e 3 ) + 2/5( e i + e 2 + e6) = (7/5 ,2/5 ,-1 ,1 ,0 ,2/5 ) f= (c x + e 4 - e3) - 2/3(e2 + e 3 + e5) = ( 1 , - 2 / 3 , - 5 / 3 , 1 , - 2 / 3 , 0 ) are both elementary vectors. Now f\f\ > 0, / 2 / 2 < 0 and thus ei and e 2 are neither substitutes nor complements although they share a node. • Figure 4.20: Arcs with common nodes need not be substitutes or complements We now turn to the study of comparative flow changes for substitutes and complements. 4.4 The Monotonicity Theory The main result of this section provides conditions under which the optimal flow in one arc is monotone in the parameter associated with another arc. We further establish bounds on the rate of change of the flow. Namely, we show how the rate of change of the flow is bounded by a function of the rate of change of the parameter vector t. We start by stating the extensions of two lemmas from Granot and Veinott [GV85] which are needed in the proof of our main result, the Monotone Optimal-Selection Theorem for constrained networks. Consider again the constrained graph G = (TV, E, a) and the problem Chapter 4. Ripples, Complements and Substitutes 91 P(ct, cto,t) : Min b(x,t) s.t. Ax = d ax = ao. L E M M A 29 Ascending Optimal-Arc-Flow Multifunction. In a dependent con-strained graph G =^N,E,a), ifT° is a chain whose elements differ only in one component j G E-, and bj is subadditive6, then the jih projection of X(t), irjX(t), is ascending in t on rpQ P R O O F . Our proof is almost identical to the proof of Lemma 11 in [GV85] and is included for completeness. For t G T°, ti fixed for all i ^ j, the minimum cost Bj[xj,tj] over all constrained flows x feasible for P(a,ao,t) with given flow Xj in arc tj can be expressed as Bj[xj,tj] = bj(ij,tj) -f B'J[XJ], where the second term is the minimum cost of flows in arcs other than ej. Since Bj[-,-] is subadditive in the variables (ij,tj) on 3? x itjTQ and the infimum of B on T° is finite, the result follows from the Monotone-Optimal-Selection Theorem of Lattice Programming [To78,Ve65]. • Now, if b(-,t) is strictly convex, then X(t) = {x(t)} is a singleton and one can interpret the conclusion of Lemma 29 as stating that Xj(t) is nondecreasing in tj. In order to prove the monotonicity result for the case where not all arc costs are strictly convex we define for a parameter e G [0, l ] m the following perturbed problem P(a,a0,t,e): Min 6(x, t,e) s.t. Ax — d ax = ao. Where b(x, t,e)= Hxu ^ ei) and 6,(x,-, U,e.) = 6,(x,-, i.) + e,-c"*''. (4.17) 6 R e c a l l that a function / on a lattice T is s u b a d d i t i v e i f for any two parameters t a n d t', f(t A t') + f(t V t') < f(t) + f(t'), where t A t' a n d t V t' are respectively the m e e t (coordmatewise m i n i m u m ) and j o i n (coordinatewise m a x i m u m ) of t a n d t' — T h i s property is also referred to in the literature as s u b m o d u l a r i t y . Chapter 4. Ripples, Complements and Substitutes 92 Let X(t,e) be the set of optimal solutions of the above perturbed problem, and note that since o(x,r,0) = b(x,t), then X(t,0) = X(t). Furthermore if / is a function from 3?" into itself, we say that f(x) has an iterated limit g as x —* y in 3?n, written Ilimx^yf(x) = g if HmXn^Vn ... lim^y, limXl^yi f(x) = g. for some order of taking limits (if different orders yield different limits, then the function may have more than one iterated limit). L E M M A 30 Iterated Optimal Constrained Flow. In a dependent constrained graph G = (N,E,a), if t ET, bj(-,tj) is convex and lower semicontinuous7 for each ej G E, and X(t) is nonempty and bounded, there is a unique x(t,e) £ X(t,e) for eache ^ > 0 (i.e., e,- > 0 for all i) and IlimciQx{t,e) exists and is in X(t). P R O O F . The proof is again similar to that of Granot and Veinott [GV85, Lemma 12] except that it uses Theorem 21 (the Ripple Theorem), and is included for completeness. We will show that X(t,e) ^ 0 and that the graph of the multifunction X(t,-) is compact on [0,l]m for any given t. Since P(a, ao,t) is feasible let x° G X(t), then b(x°,t) is finite and so is L = b(x°,t, 1). Moreover, since b(x,t,e) is nondecreasing in £, the level set 2L(t,£) = {x : Ax = d, ax = Q 0 , b(x,t,e) < L} is nonempty, and 2L(t,e) C X(<,0) for all 0 <e < 1. Now, since 6(-,t) is lower semicontinuous and X(t) is nonempty and bounded, then X(t) = X(t,0) is nonempty and compact. Thus, since the level sets of a lower semicontinuous convex function are all compact if one of them is nonempty and compact [Ro70], X_(t,0) is also nonempty and compact. By the above inclusion so is 2L{t,e), and thus so is X(t,e). Moreover, since bj(-,tj) is convex and continuous on the interval on which it is finite, &(•, t, •) is finite and continuous on the compact 7Recall that a real-valued convex function / on 3fm is l o w e r s e m i c o n t i n u o u s if and only if all its level sets {x : f(x) < a), a G 3t, are closed. Chapter 4. Ripples, Complements and Substitutes 93 set XJt, 0) x [0, l ] m , and it follows from an extension of [Be63] that for t fixed the graph of the multifunction of e t - » X(t, e)8 C X_(t, 0) is compact on [0, l ] m . Now, since b(x,t,e) is strictly convex on X_(t, 0) for e ^ 0, the perturbed problem has a unique solution, say X(t,e) = {x(f,e)} for each e. By the Ripple Theorem and treating e as the parameter we have • \xi(t,e')-Xi(t,e)\ < Maizes') - xj(t,e)\ (4.18) for all arcs ej and ej and 0 <C £ < e' < 1 differing only in the j t h component. Moreover, since b(-,t, •) is subadditive then, by Lemma 29, Xj(t,z') — Xj(t,e) > 0, and (4.18) yields |x,(t,e') - xj(r, £)| < ^ . (x^r ,^ ) - ^(r^)). (4.19) We now show that Ilimeiox(t,e) exists and is in X(t,§) = X(t). To this end let be the vector obtained by replacing in e components 1 through i by zero. We claim that limeiio x(t, e) exists and is in X(t, e^). Indeed by the above remark Xi(t, e) is nondecreasing in £i, so that l im e i jo:ri(£,£) exists and is finite by the compactness of the graph of X(t,-). Now, by (4.19) and the compactness of the graph of X(t,-), \\meii0x(t,£) exists and is finite for each i > 2, so x(t,e^) d= \imCliox(t,e) exists and is in X(t,e^), proving our claim. By induction, given x^,^'"1)) G X ( £ , e ( ' - 1 ) ) and the fact that (4.19) also holds if e is replaced by e^, define x(t,e^) *= lime,[0 x(t, e^1-1)). By a similar argument as above one can show that this limit exists and is in X(t,e^). Lastly, (4.19) also holds if e = 0, thus x(t, 0) = x(t,gt"*)) € X(t,£<m)) = X(t, 0) = X(t) and the proof is complete. • Given an ordering of the arcs, the function t i-> x(t,0)is called an Iterated Optimal-Constrained-Flow Selection. Clearly, the selection may depend on the ordering of the arcs, and thus on the order of taking limits, as it does on the type of perturbation applied to the cost function — the perturbation proposed in (4.17) is clearly not the only way to make the costs strictly convex. 8That is, the multifunction X(t, •) of t where t is kept constant Chapter 4. Ripples, Complements and Substitutes 94 T H E O R E M 31 M o n o t o n e O p t i m a l - F l o w Se l e c t i on . In a dependent constrained graph G = (N,E,ct) suppose that bj(-,tj) is convex and lower semicontinuous for each tj £ Tj, bj(-, •) is subadditive for ej £ E, and X(t) is nonempty and bounded for each t £ T. Then there exists an iterated optimal-constrained-flow selection t t-r x(t) with the Ripple Property and for which Xj(t) is nondecreasing (resp., nonincreasing) in tk whenever ej and ek are complements (resp., substitutes). P R O O F . The proof is similar to the proof of Theorem 10 in [GV85]. First consider the case where the cost function b(x, t) is strictly convex in x, and recall that in such a situation X(t) = {x(t)} is a singleton, and x(t,0) — x(t). Now, suppose that t' is obtained from t by increasing to t'k. By Lemma 29 we obtain that Xk(t') — xk(t) > 0, and since ej and ej are complements (resp., substitutes) then, by Lemma 25, Xj(t') — Xj(t) > 0 (resp., < 0), completing the proof. We now look at the case where the arc-costs may not all be strictly convex. Then the perturbed costs b(x,t,e) are strictly convex, and thus from Lemma 30 there exists a unique solution x(t,e) that is optimal for the perturbed problem for each t £ T and e >^ 0. Now clearly from the above the result holds for x(t.,e), t £ T. By taking the limit, the result will still hold for x(t) = x(t,0) — Ilimei0x(t,e) which by Lemma 30 will have the desired properties, and the proof is complete9. • 4.4.1 T h e S m o o t h i n g T h e o r e m The monotone optimal-flow selection theorem shows that changes in arc flows are mono-tone in parameter changes in certain other arcs. The Smoothing Theorem to follow presents qualitative results regarding the rate of change of the flow's compared with changes in the parameters. Following the lines of Granot and Veinott [GV85], we start with two preliminary definitions. The d u a l g* of a function g of two variables from 3£2 onto 3? U {+00} is given by the function g*(a,a') = g(a' — a,a'). The function g is said to be d o u b l y s u b a d d i t i v e if both g 9Notice that if the costs are strictly convex, then X{t) is the singleton (x(f)}, x(t) = x(t,0), and thus the notation is consistent. Chapter 4. Ripples, Complements and Substitutes 95 and g* are subadditive. For examples of doubly subadditive functions the reader is referred to [GV85, p. 489]. Two parameters t and t' of the parameter space T are said to be monotonically step-connected if there is a finite sequence t° = t, t1,..., tk = t' such that tr and f r + 1 differ at most in one component for all r and tr is coordinatewise monotone in r. In Lemma 32 we show that, under certain circumstances, a modification of an arc's parameter will not produce an optimal-flow change in this arc larger in magnitude than the variation of the parameter. L E M M A 32 In a dependent singly-constrained graph G = (N,E,a), if T° is a chain whose elements differ only in their jth entry, Tj € 3t, 6* is subadditive and bi(-,tj) is convex for all t € T° and all i ^ j, then the multifunction t i—• tj — TjX(t) is ascending on T°. P R O O F . For t € T°, let y5 = tj - Xj, then bj(xj,tj) = bf{yj,tj). Therefore Bj[xj,tj] = Bf[yj,tj] = bf(yj,tj) + B'j[tj - xf\ is subadditive on 3? x ITJT0 for bf is subadditive, and B'j[-\ is convex by the Projection Theorem for convex functions. Now, the infimum of B on T° is finite, and the proof follows from the Monotone-Optimal-Selection Theorem of Lattice Programming. • T H E O R E M 33 Smoothing Theorem. In a dependent constrained graph, suppose that Ti C 3ft, bi(-,t) is convex and lower semicontinuous for each t € Ti, that 6,- is doubly subadditive for all ei £ E, and that X(t) is nonempty and bounded for each t 6 T. Then there exists an iterated optimal-constrained-flow selection x(-) wjth the Ripple property and such that ii(t) and Mjit j — x,(<) (resp., —Mjitj — Xi(t)) are nondecreasing (resp., nonincreasing) in tj whenever ei and ej are complements (resp., substitutes). Moreover, || x(t') — x(t) ||oo< M || t' — t jji for all monotonically step-connected t and t' in T, where M = max{\fi/fj\ : e,-,ej € £ , / G # ; ( « ) } Chapter 4. Ripples, Complements and Substitutes 96 P R O O F . The proof is similar to that of Theorem 15 in Granot and Veinott [GV85] and is included for completeness. Suppose that two arcs e,- and e; are complements and that t *-* x(t) is an iterated optimal selection then, by Theorem 31, is nondecreasing in tj. Moreover, by Lemmas 31 and 32, tj — Xj(t) is nondecreasing in tj. Now, let t € T and let t' be obtained from t by augmenting its jth component. From the Ripple Theorem (Theorem 21) and Lemma 25, 0 < i,(0 - Xi(t) < Mji(xj(t') - xj(t)) => MjiXj(t) - *,•(<) < MjiXj{t') - *,•(*') and thus, by the choice of t and t', the quantity MjiXj(t) — x,(f) is also nondecreasing in tj. Consequently Mjitj-Xi(t) = M:i(tj-Xj(t)) + (MjiXj{t)-xi{t)) is the sum of two quantities which are nondecreasing in tj, and thus is nondecreasing in tj. Now, if e, and tj are substitutes instead of being complements, then by inverting the direction of e, and replacing x,(r) by — Xi(t) the arcs become complements, the above conclusions hold, and the proof of the first part of the Theorem follows. To show the second part suppose that t and t' differ in only one component, say j. Then, from the Ripple Theorem (Theorem 21) and the definition of M W O -Xi{t)\ <M3i\xj{t')-Xj{t)\ <M\xj(t')-X]{t)\ < M\t':; - tj\ by Theorem 29 (4.20) for all e,- € E. Next, consider the case where t and t' are monotonically step-connected. Then there exists a sequence t° = t, t1,..., tk = t' such that tl — t ' - 1 has only one non-zero component for each / and tl is coordinatewise monotone in /, and it follows from (4.20) that II x(0 - x(t) |U < E M O - x ^ H U < EMIIi'-t'-Ml^MHi'-Oli, *=1 Chapter 4. Ripples, Complements and Substitutes 97 completing the proof. • One should observe that in the particular case where e, and ej are complements (resp., substitutes) Mij = Max {fj/Mies?., - fj/f) : / € H(a), fifj * 0}. 4.4.2 Subadditivity of M in imum Cost in the Parameters In this section we present a result concerning the variations of the minimum cost b(t) = HjLi bj(xj(t), tj) where x(t) is any optimal flow for P(a, ct0, t). For any subset D of E, denote by XD the sub-vector of x whose entries are indexed by D, and let Y, Z be the partition of E for which x' <C xY and x'z > xz. T H E O R E M 34 Let C be a subset of E such that the arcs in C are all pairwise comple-ments, and assume that xeje£\cTj = {<£\c}, bj(-,tj) is convex for each ej 6 E\C', T is a sublattice, be is subadditive and &(•) > -co on T, then b(-) is subadditive on T. P R O O F . The proof is similar to that of Theorem 17 in Granot and Veinott [GV85] and is included for completeness. First notice that it suffices to show that, for any two feasible (not necessarily optimal) constrained flows x and x' and a pair of parameters (t,f), b(t A t') + b(t V t') < b(x, t) + 6(i', t'). If either of the last two terms is +co then the equality holds trivially, thus in the following we assume that all four terms are finite. Now, x' — x is a sum of conformal elementary circulations, and if y is the sum of the conformal elementary circulations whose support contains an arc in Y and z the sum of the remaining elementary circulations, then y and z are conformal, yY = x' — xY and zY = 0. We now claim that yz = 0, and thus that zz = x'z — xz. Indeed, suppose that j/j ^ 0 for some ey € Z, then one of the elementary vectors / that constitute y verifies /,/_,- ^ 0 for some e, € Y. Since the arcs in C are complements, ffj > 0, contradicting the fact that / is conformal with x' — x. Therefore, xc A x'c = xc + yc and xc V x'c = xc + zc- It now follows from our assumptions on the arc-costs that Chapter 4. Ripples, Complements and Substitutes 98 Ut A t') + b(t Vt') <b(x + y,t/\ t') + b(x + z,t V t') < b{x,t) + b(x',t'). • The above result can be extended to include substitutes by noticing that two arcs e, and ej are substitutes if and only if they are complements in the constrained graph obtained by reversing e,, replacing a, by — and 6,(1,, <,) by o;(—z,-,i,) (one then obtains a result similar to Theorem 19 in [GV85]). • • • Part III Applications 99 Chapter 5 A Constrained Inventory—Production Mode l Chapter Abstract We discuss in this chapter some inventory-production models which can be formulated as nonlinear parametric network flow problems with one additional linear constraint. Although NP-Complete in general, several sensitivity analysis questions can be answered in polynomial time for the class of graphs that arises from this formulation. Special cases where little or no computation is required are studied. We then recommend a method by which a decision maker could understand qualitatively how to respond to changes in the environment such as machine breakdown, strike or variations in inventory carrying costs, and do so without additional computation. • • • 5.1 Introduction Qualitative sensitivity analysis for inventory-production models with convex costs using the concepts of substitutes and complements were first studied by Veinott [Ve84] for the single commodity case, then by Ciurria [Ci89] and Ciurria, Granot and Veinott [CGV89a] for the multicommodity case. We discuss in this chapter some inventory-production models which can be formulated as nonlinear parametric network flow problems with one additional linear constraint. Several products are manufactured on parallel machines over an horizon of several time periods. The products may be sold or kept as inventory, in quantities which are related by an additional constraint. We will address different questions a manager may be faced with when responding to changes in the environment. These changes can often 100 Chapter 5. A Constrained Inventory-Production Model 101 be translated into parameter changes in the arc-cost functions. We would like to know the effect(s) of such changes on the decision variables. Where are these effects the strongest? The weakest? Are some variables unaffected? Less affected than others? Do the variables that are affected increase or decrease in value? In order to answer these and other questions, we apply the concepts and definitions from Chapter 4 to the specific constrained graph which underlies the inventory-production model. The chapter is organized as follows. In Section 5.2 we show how certain inventory mod-els can be stated as (singly-constrained) network flow problems and formulate the Singly-Constrained Multi-Period Multi-Product Inventory-Production Problem as a PSCMF. In Section 5.3 we then study this model in its general form, that is, without making any as-sumptions on the side constraint, and present some computational aspects of sensitivity analysis, as well as an illustrative example. In Sections 5.4 and 5.5 we present some special classes of constrained subgraphs for which the above computations are unnecessary and sen-sitivity analysis questions have immediate answers, at least for certain subsets of variables. Examples of such cases are provided. 5.2 The Multi-Product Multi-Period Model Using a model similar to that of Veinott [Ve84] for the Single-Product Unconstrained case, we formulate in this section the constrained single-item multi-period inventory-production model as a singly-constrained network flow problem. We will adopt the following notation. Chapter 5. A Constrained Inventory-Production Model 102 n Number of p e r i ods in the planning horizon. p Number of P r o d u c t s bought or produced. xj Amount of product / produced or ordered in period i (Negative values of xj signify d i sposa l o f goods ) , yj Amount of product / stored at the end of period j (Neg'ative values of yj signify back logged d e m a n d ) . d\~ M a r k e t d e m a n d to be satisfied by product / in period i. t\ Parameter associated with the variable xj. rj Parameter associated with the variable yj. 9i(xiiA) C o s t associated with a production level xj of product J in period i. h'j(ylj, rj) C o s t associated with an inventory/backlogging level yj- of product / at the end of period j. where / = 1, • • • ,p, i = 1, • • •, n and j — 1, • • •, n — 1. The constraints of the single-item multi-period inventory-production problem reflect the inventory balance at the end of each period. They can be stated as ^• + y ' - i - y ' = rf! » = i , - - - , n (5.21) with the convention that yl0 = y'n = 0 (If the situation calls for a positive inventory K' at the end of the planning horizon, then replace dln by dln + similarly, starting inventory is subtracted from d[ which may then be positive or negative.). Figure 5.21 illustrates the underlying graph in the case where p = 3 and n = 5. Each production arc joins the p r o d u c t i o n node 0 to a c o n s u m p t i o n node , whereas each inventory arc joins a node i to a node i + The graph G is composed of p copies of the single product graph (obtained for p = 1) called p r o d u c t subgraphs and denoted by G1, • • • , G P . Note that this formulation will allow for bounds on the variables xj and yj. In order to see this, define the s tep—funct ion fx by Chapter 5. A Constrained Inventory-Production Model 103 0 if z < 0 +oo if z > 0. If we add now the term p(x\ — t[) to, say, the cost of production of item / in period i, the model will not allow for a production of more than t[ units of that product in the ith period. Similarly, adding to the inventory cost in period i the term fi(—y\ — rj) will limit backlogging in period t to r- (if r / > 0). y,1 ~y,2 y,3 wy,4 , -, - \2 \ 2 x,1 x,2 x,3 cx,4 x,5 y,1 "y,2 "y,3 e y,4 e x , 1 X e x ; 2 e x , 3 ex,4 e x > 5 6" p J e J o" y,1 ey,2 y,3 e y,4 Figure 5.21: The basic Inventory-Production Network (p = 3 and n = 5) The Mul t i -Product Mul t i -Per iod Inventory-Production Problem is to find a schedule (x,y) = (x\,..., x£, y\,..., y^-\) which, given a parameter t = (t\,..., t*, T j 1 , . . . , r p_ x) in a lattice T, minimizes the sum of production and inven-tory costs. If in addition to the balance equation constraints (5.21) a side constraint which binds the production and inventory levels of some of the p products is added, the problem can be formulated as follows Chapter 5. A Constrained Inventory-Production Model 104 min EE*i(*i>*i) + EEM(vi.r/) i=i t=i / = i i = i s.t x'i + y'-i-y^d'i V i , / (5.22) P n p n—1 E E «W + E E J = l i = l /=11=1 The s ide cons t r a i n t £ f = 1 £ ? = i ce'^+Y^-i YZ=i P[y\ = ao may express a variety of economic or physical realities. Some examples of possible constraints with their interpretations are P n Fixed production budget E E Q « 1 ' ' = a ° a « > 0 Vi P n - l Fixed total inventory E E = a ° ; = i i = i p n - l Fixed total inventory cost E E P\y\ — ao P\ > 0 Vi. / = i t=i A complete analysis of the S i ng l e—Produc t U n c o n s t r a i n e d C a s e where / = 1 and the side constraint is absent was given by Veinott [Ve84] where it was shown that every pair of arcs are c o n f o r m a l , that is, either substitutes or complements. Indeed, in an unconstrained graph, two arcs are complements (resp., substitutes) if and only if any simple cycle orients them in the same (resp., opposite) direction(s) [GV85]. These results are summarized in Table 5.1 where, for simplicity, we denote the production (resp., inventory) arc for period i by x] (resp., y}). The reader will notice in Table 5.1 that: • All production arcs are subs t i tu t es for they are incident to the same node. • All inventory arcs are c o m p l e m e n t s . • A Production arc x] and an inventory arc j/j are c o m p l e m e n t s if i < j and subs t i tu tes otherwise. Chapter 5. A Constrained Inventory-Production Model 105 x\ x) x\ i< j k > j y} yl i < j k > j y) S C S C C S s c c c Table 5.1: Complements and Substitutes in the Unconstrained Single-Product Mode l C : Complements, S: Substitutes 5.3 Substitutes and Complements in The General Case In this section we study the Singly-Constrained Multi-Product Multi-Period Production-Inventory model in its general form, that is, without making any assumptions on the side constraint. Recall from Chapter 4 that the definitions of complements and substitutes, the Ripple coefficients, and the partial orders, all depend on the set of elementary vectors of the circulation space. As seen before, the following problems (i) Given a pair of arcs, determine whether they are substitutes, complements or neither. (ii) Given a pair of arcs, say ej and e*, determine the corresponding Ripple coefficient Mjk-(iii) Given three arcs e,-, ej and e/t, determine whether or not e, <] are NP-Hard. However, in cases where the number of elementary vectors is bounded by a polynomial in the number of arcs, a polynomial time algorithm may emerge. Here, due to the special structure of the graph underlying the production-inventory problem discussed here, we can enumerate the elementary vectors of the circulation space, and thus answer the above questions, in polynomial time. Recall from Section 3.2, equation(3.3), that the elementary vectors are simple neutral cycles or are of the form / = c1 - (acl/ac2)c2, where c1 and c 2 are simple active cycles that share at most either a single node or a simple path. For convenience we will denote by c!(j, k), where 1 < j < k < n the unique cycle composed of the arcs x'j, j/j, • • •, y1^ and x[ (backward) and define a% k) 13? ac'(;, k) = a} - ofk + £ fi. i=j Chapter 5. A Constrained Inventory-Production Model 106 Clearly, all simple cycles of G are of that form. The elementary vectors are either simple neutral cycles, that is, / = c'(j, k) where ct'(j, k) = 0, or are of the form / = c'(j, k) - (a'(j, k)/am(j', k'))cm(f, k') (5.23) with a'(j,fc) ^ 0, «m(j',k') ^ 0, 1 < j < k < n, 1 < j' < k' < n if I ^ m, and 1 < j < k < j' < k' < n if / = m (if k = j' and a'(j, fc) = a'(j', Jk'), then / = k') is a neutral cycle.). Also recall from Section 4.3 that two arcs ej and ej are complements (resp., substitutes) if and only if for all elementary vectors / , /,•/, > 0 (resp., < 0). The above leads to the following results. 5.3.1 Pairs of Arcs Corresponding to the Same Product In this subsection we deal with pairs of decision variables that correspond to a same product, say /. for the sake of convenience, we drop the product superscript / in the remainder of the subsection. L E M M A 35 Substitutes and Complements in the Same Product Subgraph. Suppose that two arcs in the same product subgraph are conformal (that is, either substitutes or complements). Then, they are complements (resp., substitutes) if and only if they are so in the one-product unconstrained model, as described in Table 5.1. PROOF. The proof follows from the fact that the set of projections of supports of elemen-tary vectors of the constrained graph on each product subgraph includes the set of simple cycles of that particular subgraph. • It remains to determine whether two arcs in the same product subgraph are conformal or not. For example, it follows from Lemma 35 that two inventory arcs, say j/j and j/j, may either not be conformal or be complements. Thus, they will be conformal unless we can find Chapter 5. A Constrained Inventory-Production Model 107 an elementary vector that orients them in opposite directions. Clearly, the elementary vector in question, if it exists, consists of two active cycles, say c1 and c2, which verify c*. = cj = 1 and (ac1)(ac2) > 0. Assuming without loss of generality that i < j, then c 1 = c(r,s) and c 2 = c(u, v) (where l < r < s < u < u < n ; the reader may verify that this is the only way to obtain elementary vectors) may be chosen so that s is as small as possible and u as large as possible. If ac 1 > 0 and etc2 > 0, then we denote the index of the last inventory arc of c1 by L®(i) = s — 1 and that of the first inventory arc of c 2 by 17®(j) = u, whereas if ac 1 < 0 and ac 2 < 0, then Le(i) = s — 1 and Ue(j) = u (for a numerical example, see Example 11). Similarly, let £®(i)» Le(i) (resp., U®(i), Ue(i)) be the left-most (resp., right-most) indices of the right (resp., left) production arcs of cycles c 1 (resp., c2) which verifies c\. = 1 (resp., c2. = 1) and ore1 > 0, ac 1 < 0 (resp., ac 2 > 0, ac 2 < 0 ). For j < k, notice that k-i QC(J, k) - ct(j, k) = H where 7< t= c*j + # — a i + 1 . We show now how to determine the values L®(i), Le(i), U9(i), Ue(i), L®(i), L6(i), U®(i)) and U6(i). To that end, we also define the quantities l®(i), le(i), u®(i) and u e ( t ) as follows. Chapter 5. A Constrained Inventory-Production Model 108 l®(i) maximizes £ 7* o v e r 1 ^ ^ *• Jt=J©(i) « / e(i) minimizes £ 7fc o v e r 1 ^ ^S(0 ^ *• fc=/e(.) m Z®(i) = min{+oo, m : £ 7* > 0, i < m < n — 1}. m L e ( i ) = min{+oo, m : £ 7fc < 0> » < m < n — 1}. u®(i) maximizes £ Ik over t < u®(i) < n — 1. Jt=.-«e(«") u e ( i ) minimizes £ 7* o v e r • ^ u&{i) < 1 — 1. *=« u®(i) f/®(z) = max{-oo,m : ^ 7^ > 0, 0 < m < z}. k=m f/e(z) = max{—00, m : ^ 7fc < 0, 0 < m < i}. k=m if i > 2 and L e ( i - 1) = 1 - 1 min{+oo, m : ^ ^ l " 1 7jt > 0, i < m <n] otherwise. i if i > 2 and - 1) = i - 1 min{+00, m : ^ "Jj1 -y^ < 0, i < m <n) otherwise. i if i < n — 1 and-{/®(i) = i max{—00, m : £!t=m 7/t < u> 1 < m < i} otherwise, i if i < n — 1 and Ue(i) = i max{—00, m : Yl'k'Jm 7* > 0> 1 < m < i} otherwise. With the convention that an empty sum is equal to zero. It is then possible to show the following. I®(0 = < Le(i) = Ue(i) = < Chapter 5. A Constrained Inventory-Production Model 109 T H E O R E M 36 Substitutes and Complements in a Product Subgraph. (i) Two inventory arcs j/,-, yj (i < j) are complements if and only if L®(») > U*(j) and Le(i) > Ue(j). (ii) Two production arcs z; and Xj (i < j) are substitutes unless at least one of the following holds (ii-a) Z ® ( t ) < Ue(j) o r Z © ( » ) < U®(j) (ii-b) Z ® ( t ) = Ue(j) = i0 and • i < i0 < j, or • z'o = i and 0 < —a(k,i) < ct(i,j) for some k < i, or • z'o = j and 0 < — a(j, k') < ct(i,j) for some k' > j. (ii-c) Le(i) = U®(j) = jo and • i < jo < j, or • jo = i and 0 < a(k, i) < —a(i,j) for some k < i, or • Jo = j and 0 < a(j, k') < —a(i,j) for some k' > j. (iii) A production arc x,- and an inventory arc yj (i < j) are complements unless at least one of the following holds. (iii-a) L®{i) < U®{j) or LQ(i) < Ue(j). (iii-b) Z ® ( » ) = U®{j) = to and • i0 7^ i, or • i0 = i and 0 < a(t, k') < —a(le(i — 1), t) for some k' > j. • (iii-c) ie(i) = Ue(j)=j0 and • jo h o r • j0 = t and 0 < — a(t, k') < a(/®(t — 1), i) for some k' > j. (iv) An inventory arc y,- and a production arc Xj (i < j) are substitutes unless at least one of the following holds (iv-a) I®(») + 1 < Ue{j) or !©(») + 1 < U*(j). Chapter 5. A Constrained Inventory-Production Model 110 (iv-b) L®(i) + 1 = U*{j) = i0 and • i0 T£ j, or • i0 — j and 0 < — a(j, k') < a(l®(j — 1), j) for some k' > j. (iv-c) + 1 = U®(j) = j0 and • Jo j, or • jo — 3 and 0 < a(j, h') < —a(le(j — l),j) for some k' > j. No other pairs of arcs may be substitutes or complements. P R O O F . First, it follows from the above definitions that U@(i) < i < L9(i) and Ue(i) < ii < Le(i). Moreover, one can check that all cycles c that contain a given in-ventory arc yi and verify ac > 0 (resp., < 0) also contain both yL<$(i) and yu®(i) (resp., j/£,e(i) and yue(i)). Similarly, all cycles that contain a given production a forward arc and verify ac > 0 (resp., < 0) lie entirely to the left of xi®^ (resp., X£e(,)) and to the right of zf?®(t) (resp., xrj&[i)). In order to prove (i), recall from Lemma 35 that two inventory arcs Vi-iVj (* < j) m a y only be complements, and will be so if and only if no elementary vector of the form (5.23) orients them in opposite directions. This will hold if and only if there does not exist a pair of active cycles c1 and c2 that contain respectively j/,- and yj and such that all inventory arcs of c1 lie strictly to the left of all inventory arcs of c2. From the above remark, such a pair will exist if and only if L9(i) < 17®(j) or L6(i) < Ue(j), completing the proof of (i). In order to show (ii), consider now two production arcs x,- and Xj (i < j), and attempt to exhibit an elementary vector / which verifies fXifXj > 0. For similar arguments as above, this is possible if L®(i) < Ue(j) or if Le(i) < U®(j), and impossible if L®(i) > Ue(j) and L e(i) > U®(j), verifying (ii-a). Suppose now that Z®(i) = UQ(j) = io, where t < i0 < j. If / exists, then it will be of the form / = c 1 — (ac1 /'ac?)c2 where the cycles c 1 and c2 share the arc x , 0 , c\. — cj. = 1, ac1 > 0 and ac2 < 0. It remains to verify that / . .-/ , , = [1 - (acVac2)^]^ - (ac'/ac2)] > 0. (5.24) Chapter 5. A Constrained Inventory-Production Model 111 One is lead to consider the following three cases. • If i < i0 < j, then c1 = c(i,i0), c2 = —c(i0,j), c2.. = cx. = 0, thus it follows from (5.24) fxtfxj = —(ac11 etc2) > 0, and i , and Xj are not conformal. • If i = io < j , then cl = — c(k,i) for some k < i, c2 = —c(i,j), (where a(k, i) < 0 and a(i,j) > 0) and t*. = - 1 , c\. = 0. Thus / „ . / , . = [1 + a(k,i)/a(ij)][-a(k,i)/a(i,j)} has the sign a(k, i) + a(i,j) and thus may be positive if 0 < — a(k, i) < a(i,j) for some k < i (from the definition of L®(i), io = i > 2). • If i < io = j, then c1 = c(i,j) and c2 = c(j,k') for some fc' > j (where a(i,j) > 0 and a(j,k') < 0). Therefore c2. = 0, c\. - - 1 , and f x , f X j = [-1 - ct(i,j)/a(j,k')] has the sign of ct(i, j) -f a(j, k') and thus may be positive if 0 < —ct(j, k') < a(i,j) for some k' > j (from the definition of Ue(j), io = J < n — 1). A similar argument holds if Le(i) = U®(j), where a is replaced by —a. To show (iii), observe that since a production arc xt- and an inventory arc yj (i < j) may only be complements, we attempt to find an elementary vector / for which f X i f y j < 0, which will be possible if l®(i) < U®(j) or if Le(i) < Ue(j), and impossible if L®(i) > U®(j) and Le(i) > Ue(j). Suppose now that L®(i) = U®(j) = io, where i < i0 < j. If / exists, then / = c1 — (ac1 jac2)^ where c1 and c2 share the arc x,0, c\. = (?y. = 1, ac1 > 0 and ac2 > 0. It remains to verify that / . * / , , = [1 " (ac7ac2)c2X - (acVac2)] < 0. (5.25) • If i < i0 < j , then c1 = c(i,i0), c2 = c(i0,k') where k' > j, c1. = c2. = 0, thus fxtfyj = —(ac1/ac2) > 0, and X{ and yj are not conformal. • If i = i0 < j, then c1 = — c(k,i) and c 2 = c(i,k') for some k < i and Jk' > j , (where a(fc,i) < 0 and a(i,k') > 0). Therefore c2. = 1 and = 0 and f x i f y , = [1 + cr(fc, i)/a(i,k')][a(k,i)/a(i,k')} has the sign of ~(a(i,k') + a(k,i)) and Chapter 5. A Constrained Inventory-Production Model 112 thus may be negative if 0 < a(i, fe') < —a(fe, i) for some k < i and k' > j or, equiva-lently (from the definition of Z® ( i ) , i 0 = i > 2), if 0 < a(i, k') < -a(le(i - l),i) for some k' > j. A similar argument holds if Le(i) — U@(j). The proof of (iv) follows from similar considerations. Since an inventory arc y,- and a production arc Xj (it< j) may only be substitutes, we attempt to find an elementary vector / for which / y i / x > > 0, which is possible if Z®(i) + 1 < Ue(j) (recall that the head of arc L®(i) is the node L®(i) + 1) or if L e ( i ) + 1 < U®(j), and impossible if L®(i) > Ue(j) and Le(i) > U®(j). Suppose now that L9(i) +1 = U6(j) = io, where i + 1 < i0 < j. If / exists, then / = c1 — (ac1 jac2)c2 where c1 and c2 share the arc x,0, c1. = c2j = 1, ac1 > 0 and ac2 < 0. It remains to verify that = (I - ( a c V a c X K - (ac'/ac2)} > 0. (5.26) • If i + 1 < io < j, then c1 = c(k,i0) where k < i, c2 = — c(io,j), c\ = c\. = 0, thus fxifyj — —(etc11 ac2) > 0, and y, and Xj are not conformal. • If i + 1 < i0 = j, then c1 = c(k,j) and c2 = c(j,k') for some < i and fe' > j , (where a(fe,j) > 0 and a(j, fe') < 0). Therefore = —1 and c2. = 0 and = — 1 — Q(k->j)/a(jynas ^ e s i g n a ( ^ » i ) + a0)fe') a n d thus may be pos-itive if 0 < — a(j, fe') < a(fe,j) for some k < i and fe' > j or, equivalently, if 0 < -a(j, fe') < a(l®(j - \),j) for some k' > j. * A similar argument holds if Le(i) + 1 = U®(j). Finally, the last statement is a direct consequence of Lemma 35. • 5.3.2 Pairs of Arcs Corresponding to Two Different P roducts In the following theorem, we provide necessary and sufficient conditions for a given pair of arcs to be substitutes or complements when they correspond to variables in two product Chapter 5. A Constrained Inventory-Production Model 113 subgraphs. First, recall that an arc is a positive (resp., negative) arc if and only if every cycle c that contains it as a forward arc verifies ac > 0 (resp., < 0). In our case, • A production arc xj is a positive (resp., negative) arc if and only if al(i,j) < 0 (resp., > 0) and al{j, k) > 0 (resp., < 0) for all 1 < i < j < k < n. • An inventory anc yj is a positive (resp., negative) arc if and only if a'(i, k) > 0 (resp., < 0) for all 1 < i < j < k < n. T H E O R E M 37 Substitutes and Complements Across Two Product Subgraphs. Two arcs from two different product subgraphs are complements (resp., substitutes) if and only if one is a positive arc and the other a negative arc (resp., both are positive arcs or both are negative arcs). Moreover, a production arc xj is a positive (resp., negative) arc if and only if L6(i) — +oo and UQ(i) — - co (resp., L®(i) = +oo and U®(i) = -co), whereas an inventory arc y\ is a positive (resp., negative) arc if and only if LQ(i) = +co and Ue(i) = - co (resp., L®(i) = -foo and U@(i) = — oo). P R O O F . First suppose that some arc e, is neither a positive nor a negative arc, that is, there exists two active cycles c1 and c 2 that contain it as a forward arc and such that ac1 > 0 and ac2 < 0. Now, given any other arc e, in some other product subgraph and any active cycle c that contains that arc as a forward arc (assume without loss of generality that ac > 0), one may consider the elementary vectors f1 = c1 — (acl/ac)c and f2 = c 2 — (ac2/ac)c. Therefore there exist two elementary vectors which verify / / fj < 0 and ffff > 0 and e; and ej are neither substitutes nor complements. Moreover, from the definition of substitutes and complements (4.15) and (5.23), a positive and a negative (resp., two positive or two negative) arcs in different product subgraphs will be complements (resp., substitutes). The proof of the second part of the theorem follows directly from the definitions of Ze(i), Ue(i), l®{i), U®(i), L e(i), Ue(i), L®(i) and U®(i). • Chapter 5. A Constrained Inventory-Production Model 114 5.3.3 Computational Complexity-It follows from the above that in order to obtain all pairs of substitutes and complements it suffices to obtain the quantities /®(i), / e (i) , L®(i), Le(i), u®(i), "e(0> U*(i), Ue[i), Z®(i), X e ( i ) , £/®(i) and £7 e ( i ) . These may be calculated using the following recursion equations: le(i + l)=< u®(i - 1) = < ue(i-l) = < «®(0 if E U W 7 t > 0 i +1 otherwise *e(0 if £U,*(,!)7*<0 x + 1 otherwise i — 1 otherwise ' ue(0 if £ l ! i ° 7 f c < 0 i — 1 otherwise. Thus the quantities /®(i), / e ( i ) j ^ ® ( * ) i ^e(0i u®(0> " e ( l ) i * = 1,•• • ," — 1 can be obtained in O(n) for each one of the p product subgraphs. Moreover, if L®(i) > i+l (resp., Le(i) > t' + l) then L®(» +1) = L®(i) (resp., Le(i +1) = Le(i)), and if c7®(i) < i - 1 (resp., £7e(0 < i - 1) then U®(i — 1) = i7®(i) (resp., C/ e (i — 1) = Ue(i)). One may thus obtain all the pairs of arcs which are either substitutes or complements in at most 0(n2p) elementary operations. E X A M P L E 11 In this example, we illustrate the concepts of substitutes and comple-ments for a production-inventory problem where the number of periods is n = 6, and the « side constraint is of the form 2x\ + 3x\ + 5x\ + 7x{ + 1 \x\ + 13x\ - 9y{ + Uy\ + ly\ + 0y\ + I7y\ +2x2 + + 5 x 3 + 7 x 4 + llxl +13*2 - 9y? + uvl + ivi + + ny52 = a0. 1=3 i '=l ;=3 i = i Chapter 5. A Constrained Inventory-Production Model 115 Where for products I = 3, a', i = l , - - - ,6 , /?', t = l , - - - ,5 , and a 0 can 6e any real numbers. The above quantities for products 1 or 2 as well as pairs of arcs which are substitutes or complements are given in Table 5.2, resulting in the pairs of substitutes and complements given in Tables 5.3 and 5-4-i 1 2 3 4 5 6 H -10 12 5 - 4 15 l*(i) 1 2 2 2 2 P(i) 1 1 3 4 4 L*(i) 2 2 3 4 5 LQ(i) 1 -f oo + 0 0 4 +oo u®(i) 5 5 5 5 5 u6{i) 1 2 4 4 5 U®(i) 1 2 3 4 5 Ue(i) 1 —oo —oo 4 —oo L®(i) 3 2 4 6 5 +oo Le(i) 2 +oo 3 4 5 6 U9(i) 1 . 2 3 4 5 — CO' ue<i) 1 —oo 2 4 3 5 Table 5.2: Substitutes and Complements: Computations Positive arcs: x2, y 2, J/3, J/5 Negative arcs: x6 Now, A manager may be interested in the qualitative effect of variations in, for instance, production cost or inventory capacity on various variables in the model. A reduction in production cost in, say, the first period and the first product, can be modeled by setting g\{x\, K', K") = K(x\) + K'x\ + K" (5.27) where K'x\ is the variable (linear) production cost of producing product 1 in the first period, K" may be a setup cost, and K(x\) represents the (convex) remainder of the cost function, possibly including upper and/or lower bounds. The functions g\(-, •, K") and g\(-, K', •) thus defined are subadditive, and are convex in x\ if so is K(x\). Moreover, it is assumed that all other costs involved are also convex in the flow variables. In this event an increase in K' (or in K") will have the following effects on the optimal production-inventory schedule. Chapter 5. A Constrained Inventory-Production Model 116 *[ x1 2 X1 x3 4 X1 xs X1 g vi y\ vi vi xl c s c c xl 2 s c s c I 3 c s c c s s c * 5 c s s c 4 s c s vi c s c c y2 c c s c c y3 c s s c y4 s c y5 c c s c Table 5.3: Substitutes and Complements, / = 1 or 2 C: Complements, S: Substitutes, " ": Neither A T2 X 1 x\ X2 xA *2 4 yl yl yl yl A X2 s c s s s X3 x\ 4 c s c c c v! v^ s c s s s yl s c s" s s y\ yl s c s s s Table 5.4: Substitutes and Complements: across products 1 and 2 C: Complements, S: Substitutes, " ": Neither Chapter 5. A Constrained Inventory-Production Model 117 (i) A decrease (Monotone Optimal-Flow Selection Theorem,) in the production level x\ of product 1 in the first period. (ii) An increase (Monotone Optimal-Flow Selection Theorem, x\ and x\ are substitutes) in the production level x\ of product 1 in the second period. (iii) A decrease (Monotone Optimal-Flow Selection Theorem, x\ and y{ (resp., y\) are complements) 4n the inventory levels y\ and y\ of product 1 in the first and second periods and no other predictions may be made without supplementary data. For similar reasons, an increase in production costs for product 1 in the second period will cause decreases in x\ and y\ and increases in x\ and y\, as well as decreases in x\ and increases in x\ and y\, y\ and y\, whereas an increase in production costs for product 1 in the fourth period will cause decreases in x\ and y\ and increases in x\ and y\. Suppose now that a decision maker is interested in the effect of variations in inventory capacity in, say, the first period and the first product. Such a change can be modeled by expressing the inventory cost in the first period for the first product as having the form h\(y\,U) = K'(y\) + p(y\-U), where the function K' includes fixed and variable costs. The function h\(y\,U) thus defined is subadditive, and h\(-,U) is convex if so is K'. Thus a decrease in the inventory capacity U will have the following effects. (i) A decrease (Monotone Optimal-Flow Selection Theorem,) in the inventory level y\ of product 1 in period 1. (ii) A decrease (Monotone Optimal-Flow Selection Theorem, y\ and x\ (resp., y\) are com-plements) in the production level x\ of product 1 in period 1 and in the inventory level y] in period 2. Chapter 5. A Constrained Inventory-Production Model 118 (iii) An increase (Monotone Optimal-Flow Selection Theorem, y\ and x\ are substitutes) in the production level x\ of product 1 in period 2. Similarly, a decrease in inventory capacity in the third period for the first product will cause a decrease in x\ and y\, and an increase in x\ and x\. • 5.4 Narrow constraints and pseudo—rims In order to further illustrate the theory of substitutes and complements developed in Chapter 4, we now turn to a special case where the constraint coefficients are concentrated in one part of the graph, that is, when the side constraint involves at most a small number of consecutive periods. In practice, such a situation may happen if the limitations reflected by the constraint are localized in time. It will be seen that, for this special case, it is easy to determine certain pairs of substitutes and complements without computation. We start with definitions of a special class of constrained graphs and the properties thereof, and state two results that will then be applied to this specific case. Note that, even though we develop this theory to apply it to problem (5.22), it also applies to a much larger class of Singly-Constrained Monotropic Network Flow Problems. 5.4.1 Pseudo-rims and their properties We call a graph G a pseudo—rim if and only if it contains a biconnected neutral subgraph, say G, called a pseudo—component, which only intersects with the rest of G at two nodes, called the pseudo—bolts relative to G. Note that a pseudo-rim may have one or several pseudo-components, and that these may be attached to one or several of the biconnected components of G. Some of the possible combinations are given in Figure 5.22 (note that a rim is a special kind of pseudo-rim, whose bolts and components are the pseudo-bolts and pseudo-components). 0 Chapter 5. A Constrained Inventory-Production Model 119 A pseudo-rim with one pseudo-rim component Figure 5.22: A Pseudo-Rim Chapter 5. A Constrained Inventory-Production Model 120 The interest in pseudo-rims is motivated by the following two results, which follow di-rectly from the definition of pseudo-rims and from the types of elementary vectors in singly-constrained graphs. L E M M A 38 Projection of Elementary vectors on pseudo—components. The projection of any given elementary vector of a pseudo-rim onto one of its pseudo-components, if nonzero, is either a simple neutral cycle or a simple path that joins the two corresponding pseudo-bolts. P R O O F . The proof is straightforward, but is included for completeness. Let / be any elementary vector in G that contains at least one arc in G. If / is a simple cycle it either lies entirely in the pseudo-component in question, say G, in which case no further proof is required, or else, since G only shares two nodes with the rest of G\G, f is composed of two simple paths between the corresponding pseudo-bolts, say n\ and n 2 , one of which lies entirely inside G, and the other, in the remainder of G, and the proof is complete (see Figure 5.23-a). Suppose now that / is of the form / = c1 — (ac1 jac2)c2, where c1 and c 2 are simple active cycles that share at most either a single node or a simple path, and assume without loss of generality that c1 contains at least one arc in the pseudo-component in question. Since c 1 is active, then it may not lie entirely inside G which is neutral, and thus we may write c 1 as p 1 — q1, where p 1 (resp., q1) is a simple path in G (resp., in G\G) that joins pseudo-bolts n i to n 2 (see Figure 5.23-b). If c 2 contains no arcs in G, then the A. _ projection of / on G is p1, and the proof is complete. Otherwise, we may write in a similar fashion c2 = p 2 — q2, where p 2 (resp., q2) is a simple path»in G (resp., in G\G) that joins pseudo-bolts n i to n 2 . Clearly c1 and c 2 then share at least one of p 1 or q1. In the first case, p1 = p2 (see Figure 5.23-b), and the proof follows, whereas if q1 = q2, then Chapter 5. A Constrained Inventory-Production Model 121 / = c1-(acllac2)c2 = (p1 - q1) - (atf - ql)la{p2 - q2))(p2 - q2) = ( P l - 9 1) - (aq'/aq^p2 - q2) . = (P1-q1)-(p2-q1) = p1-p2 which lies in G. Thus / contains no active cycles, yielding a contradiction and completing the proof. • (a) (b) Figure 5.23: Projection of elementary vectors in pseudo—rims THEOREM 39 Sensitivity Analysis in Pseudo—Components. Let G be a pseudo-rim, G (one of) its pseudo-component(s), and T H and n2 the corresponding pseudo-bolts. Consider the unconstrained graph G' = G\J{e0} where e0 = (n 2 ,ni). Then for any given triplet of arcs e,, ej and e* in G, the following holds. (i) e, and ej are complements (resp., substitutes) in G if and only if they are complements (resp., substitutes) in G'. (ii) Mij = 1. Chapter 5. A Constrained Inventory-Production Model 122 (iii) e,- <j ek is equivalent to e,- <' ek, and holds if and only if a similar relation holds in G'. PROOF. The proof follows directly from Lemma 38. • Thus, as far as arcs that lie inside a pseudo-component are concerned, the theory devel-oped by Granot and Veinott [GV85] holds. Notice however that if the arcs lie in different pseudo-components, these results do not apply. 5.4.2 Application to Narrow Constraints In this subsection we now apply the above concepts and results to certain classes of multi-period multi-product inventory problems. Pseudo-rims will occur in the subgraph corresponding to product /, J = 1, • • • ,p, if either one or both of the following hold. • There exists a period index k0 > 2 such that a' = 0 for all i < ko and ft' = 0 for all i < feo—1 (or, more generally, if 7( = 0 for all fe < feo). The two (left) pseudo-components then correspond to the arc sets {z',t < feo, y'j,i < feo — 1} and {y[0}-• There exists a period index k'Q < n — 1 such that a[ = ft' — 0 for all i > k'0 (or, more generally, if 7^ = 0 for all fe > fe0). The two (right) pseudo-components then correspond to the arc sets {x',t/',i > k'0} and {*/[<_!} (see Figure 5.24). From Lemma 38 and Theorem 39, we may conclude that (i) inventory arcs in the same pseudo-component are complements. (ii) production arcs in the same pseudo-component are substitutes. (iii) A production arc x\ and an inventory arc that lie in the same pseudo-component are complements (resp., substitutes) if i < j (resp., j < i). Notice that each of the p product subgraphs may either not be a pseudo-rim or may have one or two pseudo-component(s). We now give two examples of narrow constraints and provide the corresponding tableaus of relations between the arcs and the parameters. Chapter 5. A Constrained Inventory-Production Model 123 0 Figure 5.24: A p s e u d o - r i m w i t h fou r pseudo—components : T h e Ith p r o d u c t s u b g r a p h (fc0 = 1, K - 4) E X A M P L E 12 F i r s t Q u a r t e r B u d g e t . Consider a model with p products and six periods, and suppose that there is a fixed initial operating budget (production and inventory) on the cost of operation in the first three periods. The following side constraint will reflect this fact. E E ^ + t E ^ = «o (5.28) j = i t = i ; = i i = i where a[ > 0 is the unit operating cost of producing item I in period i, f}\ > 0 is the unit inventory operating cost for item I in period i, i = l ,--- ,3 , and OQ is the startup budget. Using Theorem 39 and without further considerations (in particular regardless of the magni-tude of the nonzero entries of a), one obtains the table of substitutes and complements given in Table 5.5 (Clearly, more arcs may be substitutes or complements. However, determining these requires the full knowledge of the side constraint an*d the computations described in Section 5.3.). Moreover, for all pairs of arcs e, e' for which Table 5.5 provides information, the Ripple coefficient Meei is equal to 1. Now, suppose that one is interested in the effect of A r e d u c t i o n i n p r o d u c t i o n cost in, say, the last (sixth) period and the first product. Such a reduction can be modeled as in Chapter 5. A Constrained Inventory-Production Model 124 1 *^ 2 x i x i X1 y'l yi yl vi yl x i A x i C s s s c c x' s c s s s c x 6 s s c s s s y'x y\> yl s s s c c c vi c s s c c c yl c c s c c c Table 5.5: Substitutes and Complements (I = l , - - - ,p) Example 11, equation (5.27) by setting g\{xl K>, K") = K(x\) + K'x\ + K" (5.29) where K(-) and all other costs involved are convex in the flow variables. In this event an increase in K' (or in K") will have the following effects on the optimal production-inventory schedule. (i) A decrease (Monotone Optimal-Flow Selection TheoremJ of, say, S units (where S > 0) in the production level x\ of product 1 in the last period. {ii) Increases (Monotone Optimal-Flow Selection Theorem, Xg and x\ (resp., x\) are sub-stitutes) of at most 6 units (Ripple property,) in the production levels x\ and x\ of product 1 in the fourth and fifth periods. • (iii) Increases (Monotone Optimal-Flow Selection Theorem, x\ and y\ (resp., y\) are sub-stitutes) of at most S units (Ripple property^ in the inventory levels y\ and y\ of product 1 in the fourth and fifth periods. and no further predictions may be made without supplementary data. For similar reasons, an increase in production costs for product 1 in the fifth period will cause a decrease of, say, Chapter 5. A Constrained Inventory-Production Model 125 8 units (where 8 >0) x\ and decreases in y\ and increases in x\, x\, and y\, all of at most 8 in magnitude. No further conclusion may be drawn at this point. • E X A M P L E 13 Shared Machine. In this example, suppose that the number of periods is again n — 6 and that the same machine is used in the production of item 1 in periods 1 and 2, then it is switched to the production of item 2 in periods 3 and 4, and lastly to that of item 3 in periods 5 and 6. The constraint on total machine time (or capacity) can then be expressed as a\x\ + a\x\ + a?,!2, + a2,!2 + Q5X5 + Q | X | = a0 Using Theorem 39 results in the pairs of substitutes and complements given in Table 5.6. This time, assume that there is a reduction in production cost for the first product in, the last period. Such a reduction can be modeled as in Example 11,by defining the cost function associated with arc x\ as in (5.29). Under similar convexity assumptions, an in-crease in K' (or in K") will have the following effects on the optimal production-inventory schedule. (i) A decrease (Monotone Optimal-Flow Selection Theorem,) of, say, 8 units (where 8 > 0) in the production level x\ of product 1 in the last period. (ii) Increases (Monotone Optimal-Flow Selection Theorem, Xg and x\ (resp., x\, x\) are substitutes) of at most 8 units (TUpple property,) in the production levels x\, x\ and x\ of product 1 in the third, fourth and fifth periods. (iii) Increases (Monotone Optimal-Flow Selection Theorem, x\ and y$ (resp., y\, y\) are substitutes) of at most 8 units (Hippie property^ in the inventory levels y\, y\, y\ and y\ of product 1 in the third, fourth and fifth periods and no further predictions may be made without supplementary data. • Chapter 5. A Constrained Inventory-Production Model 126 First Product x i x\ x\ x\ yl y\ y\ y\ yl 1 x 2 x\ c s s s s c c c x\ s c s s s s c c Xl s s c s s s s c *S s s s c s s s s y\ yl s s s s c c c c vl c s s s c c c c vl c c s s c c c c vl c c c s c c c c Second Product x\ yl yl x\ x\ yl xl X g yl yl i c s c c s c s c y? c s c c yl c s c c i 3 x\ yl T 2 x 5 c s s c T 2 x6 s c s s yl s s c c yl c s c c T h i r d Product A X 2 x\ A x\ Ig vi yl yf yl yl i c s s s c c c c x 2 s c s s s c c c x 3 s s c s s s c c T 3 x 4 s s s c s s s c r3 y? c s s s c c c c y? c c s s c c c c y33 c c c s c c c c y? c c c c c c c c yf Table 5.6: Substitutes and Complements (No further information available without numerical information on the side constraint coefficients) Chapter 5. A Constrained Inventory-Production Model 127 5.4.3 R e c o g n i t i o n o f pseudo—rims As was shown in Chapter 3, recognizing whether a given constrained graph is a rim can be achieved in linear time. It is thus natural to ask the same question of pseudo-rims. One way to answer this is by trying all possible pairs of nodes, test whether their removal augments the number of biconnected components of G (by at least one), and whether at least one of the newly cremated biconnected components is neutral. Since testing for the neutrality of a subgraph can be done in linear time (see Chapter 3), the running time of the whole procedure is a polynomial of degree 3. 5.5 F i r s t P e r i o d C o n s t r a i n t s We will focus in this section on a another special case where the constraint involves solely quantities related to the first period, that is, a' = /3' = 0 Vz > 2. Such examples will arise if, for instance, resources are limited in the first period. Indeed, a manager may be especially concerned with implementing startup conditions on one or several of the manu-facturing chains. For example, a m a n p o w e r r e q u i r e m e n t in the first period limited to the production of items 1, • • • ,po (where 2 < po < p) will be expressed by a side constraint of the form 23f=i a[x[ = Qo where a[ > 0 is the per-unit work-hour required for the production of item / in the first period and ao is the total number of work-hours to be assigned in the first period. In a similar scenario, a plant manager may wish to achieve a $-value objective on the first period production. Such a constraint can be translated as a side constraint of the form £ ? = i a i x i = ct0 where a[ > 0 is the $-value of item / produced (in period 1) and a 0 is the first period objective. In a third example, one may wjsh to fix the operating expenses (production and inventory) in the first period to meet a limited startup budget, resulting with an additional constraint of the form Y%=i aix[ + £?= i PWi = Qo where a[ > 0 is the unit operating cost of producing item I in period 1, /?( > 0 is the unit inventory operating cost for item / in period 1, and a 0 is the startup budget. Chapter 5. A Constrained Inventory-Production Model 128 5.5.1 Dependency It is easy to verify that the examples given above have the common property that each one of the product subgraphs either is neutral or is a rim. Indeed, Gl is a neutral subgraph if and only if orj- + f}\ — 0. Each such neutral subgraphs is a dependent component of G, which is independent of the rest of the graph, and thus the qualitative theory developed by Granot and Veinott [GV85] for unconstrained network flow problems applies. In particular, the coefficients Mjk introduced in the Ripple Theorem are identically equal to 1, and the arcs are all either substitutes or complements as described in Table 5.1. Furthermore, recall that any parametric modification of the cost structure in one depen-dent component will have no effect on the optimal solution in another dependent component. For that reason in the remainder of this section, we restrict ourselves to product subgraphs which are active and thus are rims, and G is a dependent graph 1. It is easy to verify that the r i m components of Gl correspond to the arc-sets {x[}, {y[}, {xl2, • • • , z „ , y [ , • • • ,yn-i} and its bolts are the nodes 0,1 and 2 (see Figure 5.25). 0 Figure 5.25: The subgraph Gl is a r im with three r i m components 1 It was shown in Chapter 3 that if only one of the product subgraphs is active, and therefore a rim, then the problem is equivalent to an unconstrained one. The theory of Granot and Veinott [GV85] then applies. Chapter 5. A Constrained Inventory-Production Model 129 5.5.2 Positive Arcs , Complements and Substitutes Recall from Section 4.3 that two positive or two negative (resp., one positive and one negative) rim arcs in a rim subgraph are complements (resp., substitutes), whereas two positive or two negative (resp., a positive and a negative) rim arcs from two different rim subgraphs are substitutes (resp., complements). Under the above assumptions on the signs of the entries of the vector a, it is obvious that the arcs x[ and y[ are positive arcs, and any positive rim cycle c in Gl contains both x[ and y[ as forward arcs and verifies ac = a\+P\ > 0. Incidentally, the elementary vectors are either neutral cycles in a product subgraph, that is simple cycles that do not contain the arcs x[ and y[, or are of the form / = c[l] - (a[ + /3<)/(aT + PTWrn] (5.30) where c[l] (resp., c[m]) is a simple cycle of Gl (resp., Gm) that contains x[ (resp., Xj") as a forward arc. A brief look at the structure of the product subgraphs will convince the reader that all inventory arcs are also positive arcs, whereas all but the first production arcs are negative arcs. The following theorem is a direct application of the above and of equation (5.30). T H E O R E M 40 Substitutes and Complements in Rims. • Two arcs e and e' in a same product subgraph (rim) are complements (resp., substitutes) if and only if they are complements (resp., substitutes) in the unconstrained version of that rim. Moreover, the corresponding Ripple coefficient is given by Mee> = 1. • Two arcs e and e' that lie in different product subgraphs are complements (resp., sub-stitutes) if and only if they are substitutes (resp., complements) when placed in the corresponding position but in the same rim, and that rim taken as an unconstrained graph. Moreover, the corresponding coefficient is given by Tit i i a\: + P\ M e e i = Mil, m) = — v ; a? + # V Chapter 5. A Constrained Inventory-Production Model 130 Where e (resp., e') belongs to Gl (resp., Gm). • The reader will notice that every pair of variables is either substitute or complement (see Table 5.7), and thus the qualitative theory developed in Chapter 4 is most informative. In particular we will show in subsection 5.5.4 that, given an increase in the parameter of one arc, predictions can be made regarding the direction of optimal flow changes in every other variable in the model. x\ x) x\ i < j k > j yl vl i < j k> j y) S[l] C[ l ] S[l] C[l ] C[ l ] S[l] S[l] C[ l ] C[l] C[ l ] x ? 1 y?1 i > 2 S[M(1,/)] C[M(1,/)] S[M(1,/)] Xj>2 C[M(1,/)] S[M(1,/)] C[M(1,/)] yf S[M(1,/)] C[M(1,/)] S[M(1,/)] Table 5.7: F i r s t P e r i o d E x a m p l e : S u b s t i t u t e s , C o m p l e m e n t s a n d R i p p l e Coe f f i c i en t s C : Complements, S: Substitutes, [Ripple Coefficients] 5.5.3 L e s s - d e p e n d e n t - o n R e l a t i o n s Other examples of questions we would like to address are the following. Given that a parameter is changed, can one be assured that the variation in a given variable will be less than (some constant times) the variation in a second variable? Is it possible to limit the effect of such a change by imposing restrictions on a (small) subset of variables? Is it possible that some variable would vary more than the one whose parameter is being changed? In order to answer the above questions, we will appeal to the two Less-Dependent-on relations. Indeed, the D-Ripple property states that if ej <j ek then the optimal flow variation in arc e, is at most, in absolute value, M^i times the magnitude of the optimal flow variation in e*;, while the Q-Ripple property, states that the magnitude of the optimal flow change in Chapter 5. A Constrained Inventory-Production Model 131 a given arc ek does not increase the less dependent qualitatively on ej this arc is. For that reason, we investigate in this subsection the cases where one or both of these partial order relations hold. In order to do so, we systematically examine the cases where the three arcs lie in various numbers of product subgraphs and use the definitions of the two relations given in Subsections 4.2.1 and 4.2.2 . (a) If the three arcs e,-, ej and ek correspond to three different products, then clearly deleting ek leaves ej and ej in the same dependent component, thus et- < j ek does not hold, and therefore neither does e,- <' ek. (b) Let us assume that ej, ej and ek lie in two different product subgraphs and consider the following cases. (b-1) ej and ej belong to the same product subgraph, say G1, and ek belongs to another, say G2. In order for the deletion of ek to cause ej and ej to end up in different dependent components, it is necessary and sufficient that (i) G2\ek is not an active subgraph, that is, ek = x\ or yf, (ii) there are only two active product subgraphs, G1 and G2, and (iii) ej and ej lie in different rim components of G1 (that is, at least one of ej and ej belongs to {xi,2/i}). If the above holds, then it follows from (5.30) that ej <' ek if and only if l«i + # l > l « ? + tf|. _ (5-31) (b-2) ej and ek belong to the same product graph, say Gx, and ej belongs to another, say G2. In order for the deletion of ek to cause ej and tj to end up in differ-ent dependent components, it is necessary and sufficient that Gx\tk is a neutral subgraph, that is, tk = x\ or y\. In that event it follows from (5.30) that any elementary vector / that contains tj verifies | /j | = |/*|, and thus ej <' tk also holds. (b-3) tj and ek belong to the same product graph, say G1, and Cj belongs to another, say G2. Since ej and ej play symmetric roles in ej <j ek, (b-2) also applies here. Chapter 5. A Constrained Inventory-Production Model 132 If e,- <dj ek holds, then (as for (b-1)), e,- <* tk if and only if (5.31) holds. (c) Lastly we consider the case where the three arcs are in the same product subgraph, say G1. From (5.30), the projection of any elementary vector on G1 either is empty or is a simple cycle, and thus e,- <j ek and e,- <? ek holds if and only if deleting tk leaves e{ and ej in two different biconnected components of G 1\ejt. One of the following is necessary. (c-1) tk is any inventory arc, and et- and tj lie on either side of ek. (c-2) tk = x\ and either e,- or tj is y\ or, by symmetry, tk = x\ and either e,- or ej is Vl-i-The above information will be best displayed using the Hasse Diagrams of both partial orders. Given an arc ejt, the partial order relation <j (resp., <*) will give rise to a directed graph whose nodes are the equivalence classes for <j (resp., <*) and where an arc joins a class to another if and only if the arcs in the first class are <j (resp., <*) than the arcs in the second class, a n d no class comes in between in the partial order. The resulting graph is a forest of rooted trees? called a Hasse Diagram, and the full order can then be inferred from it by applying transitivity. The lower an arc is in the Hasse diagram, the less <j (resp., <j) it is, and thus, by the D-Ripple property, (resp., Q-Ripple property), the less it will be affected by parameter changes in arc tj. For that reason, ej is a root and will usually be chosen as the arc whose parameter change is studied. We will provide examples of Hasse Diagrams in Subsection 5.5.4. 5.5.4 Variations in production capacity and inventory holding cost In this subsection we give several examples of situations that may occur and answer some questions regarding sensitivity analysis. In the first scenario, we consider the likely effects of a reduction in production capacity in, say, the first period and the first product. 2 A rooted tree is a directed tree such that the unique oriented path from any given node to a specific node, the root, only has forward arcs. Chapter 5. A Constrained Inventory-Production Model 133 Note that such a reduction may reflect (partial or complete) machine breakdown, manpower reduction or material shortage, or even temporary shutdown of the corresponding production unit. These occurrences can be modeled by setting g{(x\,U) = K(x\)-rn(x\-U), where K(x\) represents the (convex) production cost of product 1 in period 1, and the parameter U represents the production capacity for product 1 in the first period. The function g\(-, •) thus defined is subadditive, and gl(-, L) is convex if so is K(x\). Moreover, it is assumed that all other costs involved are also convex in the flow variables. In this event a decrease in U will have the following effects on the optimal production-inventory schedule. (i) A decrease (Monotone Optimal-Flow Selection Theorem) of, say, 8 units (where 8 > 0) in the production level x\ and of the inventory level y\ of product 1 in the first period. (ii) A decrease (Monotone Optimal-Flow Selection Theorem) of at most 6 units (Ripple property) in the inventory levels of product 1 in periods 2, • • •, n — 1. Moreover, the magnitudes of these variations decrease in time (period index) (Q-Ripple property). (iii) An increase (Monotone Optimal-Flow Selection Theorem) of at most 8 units (Ripple property) in the production of product 1 in periods 2, • • • , n. However, these changes may or may not be monotone in the time component. (iv) An increase (Monotone Optimal-Flow Selection Theofem) of 8' where 8l < M(l,l)8 = (a- + #)/(a' + @i)8 units (Ripple property) in the production level x[ and of the inventory level y[ of product I = 2, • • • ,p in the first period. (v) An increase (Monotone Optimal-Flow Selection Theorem) of at most 8l units (D-Ripple property) in the inventory levels of product 1 in periods 2, • • • , n — 1. As for product 1, the magnitudes of these variations decrease in time (Q-Ripple property). Chapter 5. A Constrained Inventory-Production Model 134 (vi) A decrease (Monotone Optimal-Flow Selection Theorem) of at most Sl units (D-Ripple property) in the production of product I = 2, • • • ,p in periods 2, • - •, n. The way the changes ripple down from x\ axe reflected in the Hasse Diagrams given in Figure 5.26 for both partial orders <*x and <'i (for the sake of convenience, we will assume in these diagrams that / = 3, M(l ,2) < 1 and M(l ,3) > 1). Figure 5.26: Hasse Diagrams, ej = x\ We now turn to a second scenario in which there is a change in the cost associated with the inventory variable y\ (we will assume for the sake of convenience that n > 5). To that end we may for instance express the inventory cost in the fourth period for the first product as having the form h\(y\,H) = K'(y\) + Hy\ Chapter 5. A Constrained Inventory-Production Model 135 where the function K' includes upper and lower bounds as well as a fixed cost. The function h\(y\,H) thus defined is subadditive, and h\(-,H) is convex if so is K'. Thus an increase i n the m a r g i n a l i n v e n t o r y cost H will have the following effects. (i) A decrease (Monotone Optimal-Flow Selection Theorem) of, say, 5 units (where S > 0) in the inventory level y\. (ii) A decrease (Monotone Optimal-Flow Selection Theorem) of at most 6 units (Ripple property) in the inventory levels of product 1 in all other periods. Moreover, the - magnitudes of these variations decrease as the period index gets further from 4, in the past as well as in the future (Q-Ripple property). (iii) A decrease (resp., increase) (Monotone Optimal-Flow Selection) of at most 8 units (Ripple property) in the production of product 1 in periods 1, • • •, 4 (resp., 5, • • •, n). Let 61 (0 < 61 < 6) be the magnitude of that decrease in the first period production. (iv) An Increase (Monotone Optimal-Flow Selection) of Sl < Af(l,/)o"x = (a] + f3})l(ct\ + /?,')o"x units (D-Ripple property) in the production level x[ and of the inventory level y{ of product / = 2, • • • ,p in the first period. (v) An increase (Monotone Optimal-Flow Selection) of at most 6l units (D-Ripple property) in the inventory levels of product 1 in periods 2,---,n — 1. As for product 1, the magnitudes of these variations decrease with time (Q-Ripple property) but this time with a maximum variation in the first period. (vi) An decrease (Monotone Optimal-Flow Selection) of at most 8l units (D-Ripple property) in the production of product / = 2, • • • ,p in periods 2, • • •, n. The corresponding Hasse Diagrams given in Figure 5.27 for both partial orders <d 1 and < J i (with the same assumption that / = 3, M(l,2) < 1 and Af(l,3) > 1). • • • Chapter 5. A Constrained Inventory-Production Model 136 Chapter 6 A Cash-Flow Asset Allocation Management Mode l Chapter Abstract We show in this chapter how a Cash-Flow Management model can be formulated as a nonlin-ear parametric network flow problem with one additional linear constraint. We then recom-mend a method by which a decision maker could understand qualitatively how to respond to changes in the environment such as variations in interest rates, taxes or asset prices without any additional computation. • • • 6.1 A Cash—flow Management Mode l Many cash-flow management models can be represented as generalized network flow problems. That is, as network flow problems with arc-gains or losses, see for example [M84]. In this chapter we show how one such model can be transformed into an equivalent singly-constrained network flow problem. One can then apply the qualitative theory developed in Chapter 4 for singly-constrained network flow problems in order to help decision makers respond to changes in their environment without having to perform any additional compu-* tations. Given an existing set of assets, the problem is to decide what would be the "best" distribution of the assets over the next planning period. The objective may be to maximize expected return, to minimize a (quadratic) risk function, or some combination of both. We will adopt the notation of Mulvey [M84]. To this end let us denote by 137 Chapter 6. A Cash-Flow Asset Allocation Management Model 138 / Set of asset indices, | / | = n bQ Cash available for investment purposes bi Initial value invested in asset i € I Si Value of asset t € I sold Pi Value of asset i £ I purchased Zi Value of asset i £ I unsold y,- Additional value invested in asset i £ I in the revised set of assets xr Amount invested in riskless asset in the revised set of assets y3 Expected value at the end of the planning horizon of the revised set of assets ^•,1(^,2) Arc multiplier for the buy (sell) transaction Po Interest rate on riskless asset pi Rate of return on asset i £ I o~i Standard deviation of the return on asset i . Moreover, we associate a convex parametric penalty or carrying cost b(-, •) with the quantities Si, pi, Zi, y t, i £ I, and xT. The nonnegativity constraints on the variables will be embedded in this cost as well as upper and/or lower bounds on the amount invested in each asset. For instance, we will denote the total cost associated with the amount xT invested in the riskless asset by tf(xr,tT) where V is a parameter associated with this investment. The expression 52»ei °"22/,2 represents the risk factor 1. Using a goal programming approach, we give a weight A > 0 to the risk factor in the objective function as was suggested in [M84] for portfolio management and obtain the for-mulation of the problem as a generalized network flow problem whose objective function is convex. That is Notice that in the portfolio models described for instance in [Ma59,M84] the risk factor is given by yiQy where Q is the variance-covariance matrix of the assets (portfolios) returns. In order to apply the Singly-Constrained Network Model described in earlier chapters we further require the limiting assumption that the various assets have i n d e p e n d e n t r a t e s o f r e t u r n , thus the non-diagonal elements of Q are zero and y*Qy = 2^i€/cr?I'«2- ^ e recognize that the independence assumption does not apply in many real life situations. For that reason, the results presented here only claim to apply in the cases where this assumption can be made. Chapter 6. A Cash-Flow Asset Allocation Management Model 139 ( G E N ) min - y , + \ZieI*2y? + E * / + E. €/4?(*,*f) + E.-€/4?(ft.«T) + E * / - ^ <f ) + -?(*', *r) 6j — 5» — z t = 0 Wi £ I L,iPi + z, - y, = 0 Vi E J E . e K 1 + POW + (1 + Po)*r - y, = 0 &o + - E ie /P . - x r = 0. The corresponding graph is given in Figure 6.28 (Triangles on arcs signify arcs with gains). Figure 6.28: The graph G G E N We now show how this model can be transferred into a Singly-Constrained Monotropic Network Flow problem (SCMF). Indeed, if we let qi = *,,ip,, we may rewrite (GEN) as Chapter 6. A Cash-Flow Asset Allocation Management Model 140 (SCF) min E,6/thti) + E*/*?(?.*?) + E.e/bi(Vi,*?) + s.t. qi + Z{ — yi = 0 Wi € I Zieih2*i + E.-6/(1/«.M)* + x r = bo + E,E/ *,,2&. where the costs b*{ziMt\) 6?(yt»'*.Pf»o"i) bT(xrttrlPo) are also convex. This is a network flow problem on the directed graph given in Figure 6.29 with a side constraint of the form ax = ao where a? = tia, aqi = l/titi, a\ = 0 Vi € I, ar = 1 and a0 = b0 + Y^bi-fe/ = VHzi^+Mibi-Zi^) = 4?(*/«.M,«?) = _ ( i + pt)y, + fcr(y.-,<r) + AcT 2 y 2 = - ( l - r - p 0 ) x r - r - 6 r ( x r , < r ) Chapter 6. A Cash-Flow Asset Allocation Management Model 141 6.2 Properties of the Graph G S C F In this section we study various properties of the graph GSCF a n d verify hypotheses needed in order to apply the theory developed in Chapter 4. Since the elementary vectors play a central role in the theory presented above, we start by obtaining a complete list of them. First notice that, under the assumption that transaction costs are nonzero, GSCF does not contain any neutral cycles. Therefore, all elementary vectors / are weighted sums of simple cycles. Thus, as was shown in Chapter 3, they satisfy / = ci — (aci/ac2)c2 (6.32) where c\ and c2 are two active cycles that either intersect at a single node, on a simple path or do not intersect. Given the simple topology of the graph GSCF, we know that the possible values for c\ and c2 are ef + ey, t\ + e?, ef — e\ for all i 6 /, and er. We will identify the elementary vectors by their supports, that is, by the variables corresponding to the cycles that form them. Such elementary vectors may, if they involve only arcs in one of the "leaves" of GSCF, be of the form / ( * . - , ft, Vi) = (e? + e?) - (or?/aJ)(eJ + e?) = e\ - Utlti<2t] + (1 - ru*,-,2)e? or, if they involve two leaves of GSCF, say corresponding to i,j € /, they will be of the form Chapter 6. A Cash-Flow Asset Allocation Management Model 142 /(*, Vi, Vi) = {< + «?) " + ej) = ef + eV - ( r , ) 2 / * i > 2 ) e * - (^ /«W)«J /(*, «,",%) = « + ^ ) - (o?/aS)(eJ + ej) = e? + eV - (U,2t^)e) - (Uat^)e) / ( * , y « 9.) = («? + <*) - (o?/(aJ - aj)(ej - ej) / ( * , y . - , © , y i ) = (e? + er) - K/aj)(ej + ED = E.? + E? " (W'.MM " / ( f t , y . , ft) = («? + er) - aJ/(o$ - ar«)(e< - ej) = c? + er + tjxl/(titl(l - tjat^))e) - t:tl/(titl(l - t]at^))t) /(*,?,•,*;,?,•) = ( e f - e ? ) - ( a f - a H / ( c ^ - a ] ) ( e ^ - e ] ) = e\ - t\ - tjtl(l - tiAtit2)/{titl(l - thltjt2))e) + ^ (1 - <,M*,:I2)/(*.M(1 ~ Wit) /(*,-, y,-,xr) = (e f - f e r ) - (a ,Va r ) e r = e f - r e r - < , - , 2 e r ffayux*) = (e? + ef)-(a?/ar")e' = e J + e?-(l/«.-.iK « z,-, x') = (e* - e?) - ((a? - a?)/or> r = < - e? + (1 - U^/t^ as well as any combination obtained by reversing i and j . We may assume for practical purposes that 0 < < 1, 0 < Ut2 < 1 and thus 0 < 1 — *,,it\,2 < 1 for all i G P. 2In practice, the transaction costs are of the order of 1%. Thus Uti and f,-j2 are close to .99. Chapter 6. A Cash-Flow Asset Allocation Management Model 143 We may now determine whether a given pair of arcs in GSCF are substitutes, comple-ments, or neither, by simply looking at the signs of the entries of the elementary vectors. For example, we may deduce that e\ and are complements, for the only elementary vectors that contain them both are /(-?,-, y,), /(z,-, y„ zit yj), /(*,-, y,-, qj, yj), f(z{, y„ ZJ, qj) which all verify f'ff > 0. Table 6.8 shows the signs of the entries of these elementary vectors (i ^ j) and Table 6.9 shows which pairs of arcs are substitutes (S), complements (C) or neither (n). Support: e*i e i zi, qi, Vi + - + Zi,Vi,Zj,yj + + - -*i,yi,qj,yj + - -qi,yi,zj,yj + + - . -Zi,yi,zj,qj + + + -z>,qi,zi,qj + - + + qi,yi,qj,Vj + + - -qi,yi,zj,qj + + + -zi,qi,qj,yj + - + + zi,qi,zj,qj + - - + Zi,yi,x r + + -qi, yi, x r + + -zi,quzT + - + zj,yj,xr + + -qj,yj,*T + + -Zj,qj,x r + - + Table 6.8: Table Signs of Respective Elementary Vector Entries Zi qi yi Zj qj yj XT Zi C s C qi s C s s .s yi C C s s s Table 6.9: Substitutes and Complements in the Cash-flow Problem Next, we obtain in Table 6.10 the coefficients M , ; which appear in (4.7). In order to break ties, we will make the additional assumption that l/t,,i — r.t)2 < r, ( 2 (1 < 2 U,\U,2) for all i G / which, for most real situations, is indeed the case. Chapter 6. A Cash-Flow Asset Allocation Management Model 144 x\x' e? el «5 e? er e,? 1 1 1 *i .2*i .l ti.a.i.i l - t , . l* , .2 l - t , . l* , .2 t,.a el e? I 1 <U<..2 1 1 1 1 1 *i.i(i-*y.i*>,2) «.,i(l-*>,i*>.a) • i . i *..i*>,a 1 1 l- t . . l*. .2 l-*.M*.-.a *..i(l-*t.i«t.a) *i. i(l-*i. i*i ' .a) •i.i«..a t.M er ti.l 1 *,-.{ 1 1 l-U.lU.2 l-*i.l*.-.8 *i.2 l - t | . l t f .2 *i.a Table 6.10: Coefficients of the Ripple Theorem 6.3 Qualitative Sensitivity Analysis In the event that the arc costs are convex and, under appropriate parametrization, subadditive, one can apply the results given in Chapter 4 to various scenarios, we provide in the following two such examples. In order to give orders of magnitude, the following statements are respectively given for general values of the transaction costs as functions of and *,-,2, for tifl - ti>2 = .99 Wi e I and for titl = ti<2 = .90 Vi G / . • Changes in Sales Taxes. Assume that a tax is imposed on sales of asset i at rate T{. This will result in an additional cost of T{S{ = 7\(o; — z,), which may be incorporated in the cost associated with Zi (recall that s, is not explicitly a part of the SCF formulation). In order to investigate the qualitative effect of changes in the tax rate r,- on our cash-flow allocation revision, we express the cost associated with z,- as &?(*,•, Ti) = Ti(bi - Zi) + #(*,•) + b>(bi - Zi). where 6f(z,) and ££(&,• — z,) denote the (non-parametric) costs of selling an amount Si and keeping an amount zt- of asset i excluding the tax. The function if (•, •) thus defined is subadditive, and 6f(•,Tj) is convex if so is i£(z;) + 6^ (6,- — z,). In this event an increase in the tax rate r, on sales of asset i will have the following effects. (i) An increase of, say, $6 (where 6 > 0) in the amount Zi kept invested in asset i and thus a decrease of $«5 in the amount of that asset sold (s,). Chapter 6. A Cash-Flow Asset Allocation Management Model 145 (ii) A decrease of at most $6/i*,il (resp., $1,016 if i , ti = i*,i2 = .99 Vi G / , and $1,116 if U,i — ti,2 = -90 Vi € /) in the amount of asset i bought (p,- = o,/£,,i). (iii) An increase of at most $6 in the amount of asset i in the revised set of assets (y,). (iv) A variation of at most $6f»,2*j,i/(l~"*j,i'j,2) (resp., $49,256", $4,266") in the amount of asset j ^ i (ZJ) kept and an opposite variation of the amount of asset j sold (v) A variation of at most Utii2tj,i/(ti,i(l - *i,i'j,2)) (resp., $49,756, $4,746) in the amount of asset j ^ i purchased (pj). (ui) A variation of at most $6£, ) 2 /t 'j i 2 (resp., $6, $6) in the amount of asset j ^ i in the revised set of assets (yj)- . (vii) A variation of at most $6r;i2 (resp., $.996, $.906) in the amount invested in riskless asset (xr). • Variations in Expected Rate of Return. Recall that the cost associated with the level y, invested in asset i in the revised allocation is given by where if(y,-, ti) denotes the other costs besides asset return and risk component. Sup-pose now that there is an increase in the rate of return /?, and all other parameters remain fixed. We can thus write mvu Pi) = - ( i + rivi + $ (yi) + ^ h l The function o*(y,-, Pi) thus defined is subadditive, and 6f(-, p.) is convex if so is ^(y,) + Aofy2. Thus an increase in the expected rate of return on asset i will have the following effects. (i) An increase of, say, $6 (where 6 > 0) in the amount y, invested in asset i in the revised set of assets. Chapter 6. A Cash-Flow Asset Allocation Management Model 146 (ii) An increase of at most $6/(1 — U^t^) (resp., $50,256, $5,266) in the amount of asset i kept in the set of assets (ZJ = gi/£,,i). (iii) A variation of at most $6ij i 2/(l — U,iL,2) (resp., $49,756", $4,746) in the amount purchased of asset i (p,). (iv) A variation of at most $6f J ) i / (£, ) i ( l—t,,!*,^)) (resp., $50,256, $5,266) in the amount of asset j i (ZJ) kept and an opposite variation of the amount of asset j sold (SJ). (v) A decrease of at most $<^i_7i /(t1(1(l — *j,i^i,2)) (resp., $50,256, $5,266) in the amount of asset j j£ i purchased (pj)-(vi) A decrease of at most $8/ti,itjt2 (resp., $1,026, $1,236) in the amount of asset j ^ i in the revised set of assets (yj)-(vii) A decrease of at most $6/ ,^1 (resp., $1,016, $1,116) in the amount invested in riskless asset (xr). Remark. Similar results can be obtained if one considers changes in market prices, interest rates, and more. • Subadditivity of the optimal value. Recall from Subsection 4.4.2 that, under the above assumptions, the optimal value b(-) is subadditive in the parameters. In the case where one studies the effect, say, of increasing the tax rates r,, i € / , on the sales of more than one asset, the subadditivity reflects the following reality. If increases were to be introduced successively, a given increase will have less impact on the expected return the later it is introduced, all other parameters being equal. Similarly, as far as increases in rates of returns on individual assets are concerned, such an increase will have a more significant effect on the overall objective if it happens alone than if it were to follow a series of similar increases in other assets. • • • Appendix index 2-connected a-one—forest 8 124 A{q) 23 [DN] 84 [MWOP-D] 78 [MWOSC] 74 [M] 74 [QLD] 78 84 Al[M] 74 A/[QLD] 78 C(a) (constrained circulation space) 11 E, set of arcs 10 E, set of arcs 1 F(a,cto,d), set of constrained flows 10 H(a), set of elementary vectors 20 H}{a) 63 N, set of nodes 1 N, set of nodes 10 P(<x,a0) 2 Q 22 s, size of an instance 13 tj, arc parameter 60 Tj, parameter lattice 60 X(t), set of optimal flows 60 active 11 additional constraint 1, 10 adjusted version 48 A L G O R I T H M I 41 A L G O R I T H M II 51 ancestors 12 147 Appendix A. index arc redirecting 41 arcs with common degree-two nodes 86 ascending optimal-arc-flow multifunction 91 backlogged demand 102 backward 11 basic variables 16 basis for the tucker representation 16 biconnected component 21 biconnected 12, £1 bolts 25 branches of G 31 changes in sales taxes 144 circulation space 15 circulation 10 complements 81 conditional transitivity of complements and substitutes connected 12 constrained circulation 11 constrained graph 10 constrained palm graph 12 constrained circulation space 11 constrained problem 60 consumption node 102 contain 11 cost 10, 1 cost 60 cut 12 cycle graph 25 d-equally dependent on 63 d-equivalence classes 63 D-ripple property 70 decision problem 13 demand vector 1, 10 dependent component 21 dependent component-additive 56 dependent 21 descendant 12 detection of VQ and WQ 4% detection of the bolts 4% directed graph 1, 10 directed spanning tree 12 disconnected version of G 4$ disposal of goods 102 Appendix A. index doubly subadditive dual 94 94 elementary vector elementary support 11 11 elementary circulation 11 evaluation problem expanded one-rim 13 35 expansion arc 35 father 13 feasible 10 flow " 1, 10 forward 11 fundamental basis associated with B 19 hasse diagram 132 head 1, 10 incidence matrix 1, 10 independent rates of return 138 instances 13 iterated limit 92 iterated optimal-constrained-flow selection iterated optimal constrained flow 92 join 91 lattice 60, 103 leaf branch 40 leaf arcs 16 less-dependent-on 61 lower semicontinuous 92 manpower requirement 127 market demand 102 maximum weight oriented simple cycle 74 meet 91 monotone optimal-flow selection 94 monotonically step-connected 95 monotropic programming problem 1 multiple constraints 57 negative arcs 11, 113 negative rim arcs 87 neutral 11 node labelling 41 nonbasic variables 16 nonlinear and inequality constraints 56 one-rims 35 one-rim split, (if G is a one-rim) 4% Appendix A. index oriented cycle 11 oriented path 11 palm graph 12 parallel arcs 86 parameter vector 60 parameter 60 parametric singly-constrained monotropic network flow problem (pscmf) parametric unconstrained monotropic network flow problem 60 periods 102 • positive arcs 11, 113 positive rim arcs 87 problem 13 product subgraphs 102 production node 102 products 102 \ pseudo-component 118 pseudo-bolts 118 pseudo-rim 118 q-equally dependent on 68 q-equivalence classes 68 Q-ripple property 70 qualitative determinacy 4 quantitatively less dependent on 61, 68 R-cycle 31 R-arc 31 reduction in production cost 123 reduction in production capacity 132 reduction in production cost 115 reduction in production cost 125 return arcs 12 return arc partitioning 41 reversed 11 rim components 25 rim 25 risk factor 138 • root 12 rooted tree 132 S-cycle 31 S-arc 31 schedule 103 series arcs 86 shared machine 125 side constraint 104 Appendix A. index simple cycle 11 simple path 11 single-product unconstrained case 104 singly-constrained monotropic network flow problem (scmf) size of an instance IS spanning forest 12 spanning tree 12 special types of constraints 57 step-function 1Q2 subadditive 91 submodularity 91 substitutes 81 supp(x) 11 support 11 tail 1 tail 10 tree arcs 12 Tucker representation 16 unconstrained problem 15, 60 unconstrained monotropic network flow problem 2, 15 underlying tree 12 variations in expected rate of return 145 weights 74 • • • Bibliography [AHU74] A. V . Aho, J . E . Hopcroft and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addisson-Wesley, Reading, Massachusetts, 1974-[Ba89] U. Bagchi. Simultaneous Minimization of Mean and Variation of Flow Time and Waiting Time in Single Machine Systems. Opns. Res. 37, No. 1, 1989. [BMM88] K. Belling-Seib, P. Mevert and Chr. Muller. Network Flow Problems with One Side Constraint: a Comparison of Three Solution Methods. Comput. Opns. Res. 15 No. 4, 381-394, 1988. [Be63] C. Berge. Topological Spaces. Macmillan, New York, 115-116, 1963. Translation of Espaces Topologiques, Fonctions Multivoques. Dunod, Paris, France. [Be73] C. Berge. Graphs and Hypergraphs. North-Holland, 1973. [Bert76] D. P. Bertsekas. A New Algorithm for Solution of Restrictive Networks Involving Diodes. IEEE Trans. Circuit Sys. CAS-23, 599-608, 1976 [BC80] R. E . Bixby and W. H. Cunningham. Converting Linear Programs to Linear Pro-grams. Math of Operations Research 5, 312-357, 1980. [Cu83] W. H. Cunningham. A Class of Linear Programs Convertible to Network Pro-grams. Operations Research 31 387-391, 1983. [CS77] S. Chen and R. Saigal. A Primal Algorithm for Solving a Capacitated Network Flow Problem with Additional Linear Constraints. Networks, 7, 59-79, 1977. [Ci89] I. Ciurria. Substitutes and Complements in Multicommodity Flows and Invento-ries. Doctoral Dissertation, Department of Operation Research, Stanford Univer-sity, 1989. [CGV89a] I. Ciurria, F. Granot and A. F. Veinott. Substitutes, Complements and Ripples in Multicommodity Production Planning. Working Paper, Faculty of Commerce and Business Administration, The University of British Columbia, 1989. [CGV89b] I. Ciurria, F. Granot and A. F. Veinott. Substitutes, Complements and Ripples in Multicommodity Flows on Suspension Graphs. Working Paper, Faculty of Com-merce and Business Administration, The University of British Columbia, 1989. [CD73] P. Crawley and R. P. Dilworth. Algebraic Theory of Lattices. Prenctice-Hall, 1973. [DK81] R. S. Dembo and J. G. Klincewicz. A Scaled Reduced-gradient Algorithm for Con-vex Network Flow Problems. Math. Prog. Study, 15, 125-147, 1981. 152 Bibliography 153 [GP81] D. Gale and T. Politof. Substitutes and Complements in Network Flow Problems. Discrete Applied Math 3 175-186, 1981. [GJ79] M . R. Garey and D.S. Johnson. Computers and intractability: A guide to NP-Completeness. W. H. Freeman and Company, New York, 1979. [GG89] A. Gautier and F. Granot. A Linear Transformation of a Singly-Constrained to an Unconstrained Monotropic Network Flow Problem. Working paper, Faculty of Commerce and Business Administration, The University of British Columbia. June 1989, revised September 1990. [GG90a] A. Gautier and F. Granot. Ripples, Complements and Substitutes in Singly-Constrained Monotropic Parametric Network Flow Problems. Working paper, Faculty of Commerce and Business Administration, The University of British Columbia. March 1990. [GG90b] A. Gautier and F. Granot. A Parametric Analysis of a Nonlinear Cash-Flow Asset Allocation Management Model. Working paper, Faculty of Commerce and Business Administration, The University of British Columbia. May 1990. [GG90c] A. Gautier and F. Granot. A Parametric Analysis of a Constrained Nonlinear Inventory-production Model. Working paper, Faculty of Commerce and Business Administration, The University of British Columbia. October 1990. [GKKR78] F. Glover, D. Karney, D. Klingman and R. Russell. Solving Singly-constrained Transshipment Problems. Transport. Sci. 12, 277-297, 1978. [Go64] T. Gorman. More Scope for Qualitative Economics. Rev. Econ. St. 31, 65-68, 1964. [GV85] F. Granot and A. F. Veinott, Jr. Substitutes, Complements and Ripples in Network Flows. Math. Oper. Res. 10, 471-497, 1985. [Gr81] H. J . Greenberg. Measuring Complementarity and Qualitative Determinacy in Matricial Forms, in Proceedings of the Symposium on Computer Assisted Analysis and Model Simplification, H. J. Greenberg and J. S. Maybee, Eds. Academic Press, New York, 1981. [GLM83] H . J . Greenberg, J. R. Lundgren and J . S. Maybee. Rectangular Matrices and Signed Graphs. SIAM J. Alg. Disc. Meth. 4 No.*l, 50-61, 1984. [GLM84a] H. J . Greenberg, J. R. Lundgren and J. S. Maybee. Inverting Graphs of Rectan-gular matrices. Discrete Applied Mathematics 8, 255-265, 1984' [GLM84b] H. J. Greenberg, J . R. Lundgren and J . S. Maybee. Inverting Signed Graphs. SIAM J. Alg. Disc. Meth. 5 No. 2, 216-222, 1984. [HK77] R. V. Helgason and J. L . Kennington. An Efficient Specialization of the Convex Simplex Method for Nonlinear Network Flow Problems. Technical report IEOR 99017. Southern Methodist University. 1977. Bibliography 154 [Hi39] J . R. Hicks. Value and Capital, 2nd edition, Oxford Press, Garendon 1939. [HA34] J. R. Hicks and R. G. D. Allen. A Reconsideration of the Theory of Value, Parts I and II, Economica, I, 52-76, 196-219, 1934-[HT73] J . E . Hopcroft and R. E . Tarjan. Efficient Algorithms for Graph Manipulation. Comm. ACM, 16, 372-378, 1973. [Ki47] G. Kirchhoff. Annalen der Physic und Chemie, 72, 497, 1847. [K177] D. Klingman. Finding Equivalent Network Formulations for Constrained Network Problems. Mgmt. Sci. 23, 737-744, 1977. [La67] G. M . Lady. The Structure of Qualitative Determinate Linear Systems. Rice Uni-versity, Houston, Texas, Systems Report No. 19-14, 1967. [La62] K. Lancaster. The scope of Qualitative Economics. Rev. Econ. St. 29, 99-132, 1962. [La65] K. Lancaster. The Theory of Qualitative Linear Systems. Econometrica, 33, 395-408, 1965. [La66] K. Lancaster. The Solution of Qualitative Comparative Static Problems. Quart. J. Econ. 80, 278-295, 1966. [Ma59] H. Markowitz. Portfolio Selection. John Wiley & Sons, New York, 1959. [Ma73] R. M . May. Stability and Complexity in Model Ecosystems, Princeton University Press, Princeton, New Jersey, 1973. [MQ69] J . Maybee and J. P. Quirk. Qualitative Problems in Matrix Theory. SIAM Review II 30-51, 1969. [M84] J. M . Mulvey. Nonlinear Network Models in Finance, in "Advances in Mathemat-ical Programming and Financial Planning", Vol. 1, pp. 253-271, J.A.I. Press. [Or82] J . B. Orlin Minimum Convex Cost Dynamic Network Flows. Working Paper, Sloan School of Management, M.I.T. 1982. [PS82] C. H. Papadimitriou and K. Steiglitz. Combinatorial Optimization; Algorithms and Complexity. Prenctice-Hall, Englewood Cliffs, New Jersey, 1982. [Pa71] K. Paton. An Algorithm for the Blocks and Cutnodes of a Graph. Comm. ACM, 14, 468-475, 1971. [Pr83] J. S. Provan. Determinacy in Linear Systems and Networks. SIAM J. Alg. Disc. Meth. 4 262-278, 1983. [Pr86] J. S. Provan. Substitutes and Complements in Constrained Linear Models. Work-ing paper, Curriculum in Operations Research and Systems Analysis, University of Carolina at Chapel Hill, December 1986. Bibliography 155 [PK80] J . S. Provan and A. S. Kydes. Correlation and Determinacy in Network Models. BNL Report No. 51243, Brookhaven National Laboratory, Upton, NY. 1980 [QR65] J . P. Quirk and R. Ruppert. Qualitative Economics and the Stability of Equilib-rium, Review of Economic Studies 32 311-326, 1965. [Ro67] R. T. Rockafellar. The Elementary Vectors of a Subspace of R". In Combinatorial Mathematics and its Applications, Proceedings of the Chapel Hill Conference, 104-127, R. C. Bose & T. A. Dowling eds., University of North Carolina Press, 1967. [Ro70] R. T. RocTcafellar. Convex Analysis. Princeton University Press, Princeton, N.J., 1970. [Ro84] R. T. Rockafellar. Network Flows and Monotropic Optimization. John Wiley & Sons, 1984. [Sa47] P. A. Samuelson. Foundations of Economic Analysis. Anthenum, New York, 1971. Originally published by Harvard University Press, 1947. [Sa74] P. A. Samuelson. Complementarity: An Essay on the Fortieth Anniversary of th Hicks-Allen Revolution in Demand Theory. J. Econ. Lit., 1255-1289, 1974. [Sh61] L . S. Shapley. On Network Flow Functions. Naval Res. Logist. Quart. 8 151-158, 1961. [Sh62] L . S. Shapley. Complements and Substitutes in the Assignment Problem. Naval Res. Logist. Quart. 9 45-48, 1962. [SL89] S. B. Spalti and T. H. Liebling. A Special Case of a Network Problem with one Side Constraint. Working Paper R.O. 890429, Departement de Mathematiques, EPF Lausanne, Switzerland, 1989. [Ta72] R. E . Tarjan. Depth-First Search and Linear Algorithms. SIAM J. Comput. 1, 146-160, 1972. [To78] D. M . Topkis. Minimizing a Submodular Function on a Lattice. Oper. Res. 26, 305-321, 1978. [TV73] D. M . Topkis and A. F . Veinott, Jr. Monotone Solutions of Extremal problems on Lattices, (abstract). VIIIth Internat. Math. Prog», Abstracts. Stanford University, 1973. [Tr83] K. Truemper. How to Detect Hidden Networks and Totally Unimodular Section in Linear Programs. TIMS/ORSA Bulletin No. 5, 1978. [Tuc63] A. W. Tucker. Combinatorial Theory Underlying Linear Programs, In Recent Advances in Mathematical Programming, 1-16, R. L. Graves & P. Wolfe eds., MacGraw-Hill, 1963. [Tut66] W. T . Tutte. Connectivity in Graphs. University of Toronto Press, Toronto, 1966. Bibliography 156 [Ve64] A. F. Veinott. Production Planning with Convex Costs: a Parametric Study. Man-agement Science 10, No. 3, 44i~4^0, 1964-[Ve65] A. F. Veinott. Monotone Solutions of Extremal Problems, (unpublished). 1965. [Ve68] A. F. Veinott. Substitutes and complements in Network Flow Problems. Presenta-tion to the TIMS/ORSA meeting, San Francisco, CA, 1968. [Ve84] A. F. Veinott. Lecture Notes in Inventory Theory. Department of Operation Re-search, Stanford University, Stanford, CA. 1984-[Vefo.] - A. F. Veinott. Lattice Programming. Forthcoming. [Wh32] H. Whitney. Non Separable and Planar Graphs. Trans. Amer. Math. Soc, 34, 339-362, 1932. • • •
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Singly-constrained monotropic network flow problems...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Singly-constrained monotropic network flow problems : a linear time transformation to unconstrained problems… Gautier, Antoine 1990
pdf
Page Metadata
Item Metadata
Title | Singly-constrained monotropic network flow problems : a linear time transformation to unconstrained problems and qualitative sensitivity analysis |
Creator |
Gautier, Antoine |
Publisher | University of British Columbia |
Date Issued | 1990 |
Description | This thesis examines several problems related to singly-constrained Monotropic Network Flow Problems. In the first part, a linear time algorithm that reduces the solution of a monotropic network flow problem with an additional linear equality constraint to the solution of lower dimensional subproblems is presented. Of the subproblems, at most one is a singly-constrained monotropic network flow problem while the others are unconstrained. If none of the subproblems is constrained, the algorithm provides a linear-time transformation of constrained to unconstrained monotropic network flow problems. Extensions to nonlinear and inequality constraints are given. In the second part the qualitative theory of sensitivity analysis for Unconstrained Minimum-Cost Flow Problems presented by Granot and Veinott [GV85] is extended to Minimum-Cost Flow Problems with one additional linear constraint. The departure from the unconstrained network structure is shown to have a profound effect on computational issues. Two natural extensions of the "less-dependent-on" partial ordering of the arcs given in [GV85] are presented. One is decidable in linear time while the other yields more information but is NP-complete in general. The Ripple Theorem gives upper bounds on the absolute value of optimal-flow variations as a function of variations in the problem parameter. Moreover, it shows how changes may "ripple down" throughout the network, decreasing in magnitude as one gets "further away" from the arc whose parameter initiated the change. The Theory of Substitutes and Complements presents necessary and sufficient conditions for optimal-flow changes to consistently have the same (or the opposite) sign in two given arcs. The complexity of determining Substitutes and Complements is shown to be NP-complete in general. However, for all intractable problems, families of cases arise from easily recognizable graph structures and can be computed in linear time. The Monotonicity Theory links the changes in the value of the parameters to the change in the optimal arc-flows. Bounds on the rates of changes are discussed. We further provide a number of practical situations where our theory may apply. We discuss some Multi-Period Multi-Product Inventory-Production models that can be formulated as nonlinear parametric network flow problems with one additional linear constraint. We then apply our theory to help decision makers understand qualitatively how to respond to changes in the environment such as machine breakdown, strike or variations in inventory carrying costs without additional computation. In a second example, we show how a Cash-Flow Management model can be formulated as a nonlinear parametric network flow problem with one additional linear constraint. The theory is then recommended as a method by which a decision maker could understand qualitatively how to respond to changes in the environment such as variations in interest rates, taxes or asset prices without any additional computation. |
Subject |
Linear time invariant systems Monotonic functions Mathematical optimization |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-01-26 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0100489 |
URI | http://hdl.handle.net/2429/30879 |
Degree |
Doctor of Philosophy - PhD |
Program |
Business Administration |
Affiliation |
Business, Sauder School of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1991_A1 G38.pdf [ 9.03MB ]
- Metadata
- JSON: 831-1.0100489.json
- JSON-LD: 831-1.0100489-ld.json
- RDF/XML (Pretty): 831-1.0100489-rdf.xml
- RDF/JSON: 831-1.0100489-rdf.json
- Turtle: 831-1.0100489-turtle.txt
- N-Triples: 831-1.0100489-rdf-ntriples.txt
- Original Record: 831-1.0100489-source.json
- Full Text
- 831-1.0100489-fulltext.txt
- Citation
- 831-1.0100489.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0100489/manifest