SINGLY-CONSTRAINED MONOTROPIC N E T W O R K F L O W PROBLEMS: A LINEAR T I M E TRANSFORMATION T O 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 T H E DEGREE OF DOCTOR OF PHILOSOPHY in T H E 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 singlyconstrained 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 MinimumCost 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 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 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 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. iii Table of Contents Abstract ii List of Tables vii List of Figures viii Acknowledgement x I Foundations xii 1 Introduction 1 1.1 T h e Singly-Constrained M o n o t r o p i c Network Flow P r o b l e m . . . . 1 1.2 Substitutes, complements and Ripples 4 1.3 Applications 5 1.4 Organization 6 2 II 3 Notation and Definitions 10 Singly—Constrained Network Flow Problems 14 Transformation to an Unconstrained Network Flow P r o b l e m 15 3.1 P r e l i m i n a r y remarks 15 3.2 Tucker Representation and Elementary Vectors of C(a) 16 3.3 Dependency and G r a p h Decomposition 20 3.4 Decomposition Into Independent M o n o t r o p i c 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-dependent78 on Relation III 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 97 Subadditivity of Minimum Cost in the Parameters 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 5.4 Narrow constraints and pseudo—rims , 114 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 6.1 A Cash-flow Management Model 6.2 Properties of the Graph G CF 137 137 1 4 1 S 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 P e r i o d Example: 130 6.8 Table Signs of Respective Elementary Vector Entries 143 6.9 Substitutes and Complements in the Cash-flow P r o b l e m 143 6.10 Coefficients of the Ripple T h e o r e m vii 144 List of Figures 3.1 Decomposition of the graph G 28 3.2 Rims and'Graphs 30 3.3 A o n e - r i m (left) and its expanded version (right) 3.4 A palm graph with its branches 38 3.5 T h e 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 rim G 54 4.9 E q u a l l y dependent pairs of arcs need not disconnect the graph . . . 64 4.10 Construction of the dependent graph G when G^e*} is a r i m . . . . 66 35 4.11 Construction of the dependent graph G when G\{ek} is not bicon67 nected 4.12 =•] does not imply =) 69 4.13 T i g h t bounds in the Ripple T h e o r e m 72 4.14 T h e extended graph G" 75 4.15 O n l y 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 T h e r i m G (left) and the constructed graph T(G')(right) 4.20 Arcs with common nodes need not be substitutes or complements. 88 90 5.21 T h e basic Inventory-Production Network 103 5.22 A P s e u d o - R i m 119 viii 5.23 Projection of elementary vectors in pseudo-rims 121 5.24 A p s e u d o - r i m with four pseudo—components: 123 5.25 T h e subgraph G is a r i m with three r i m components 128 5.26 Hasse Diagrams, e, = x\ 134 5.27 Hasse Diagrams, 136 l = y\ 6.28 The graph C E N • G 6.29 The graph G C F S ••- •• ix 1 1 3 4 9 0 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 Administration, 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 T h e Singly-Constrained M o n o t r o p i c Network Flow P r o b l e m A M o n o t r o p i c P r o g r a m m i n g P r o b l e m is an optimization problem in which the objective 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, subject to an additional linear constraint. This problem will be referred to as the S i n g l y - Constrained M o n o t r o p i c Network Flow P r o b l e m ( S C M F ) . To state S C M F 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,e , • • • ,e } 2 m (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 A j = 0 otherwise. x A demand vector (for G) is a real valued vector d £ 3£ for which £ ? = i n = 0. For a given real-valued row-vector a 6 3? and a real number ao € R we define the additional m constraint ax = a for x € 3 £ . With each arc e, £ E we associate a flow x,- 6 m 0 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 3ft is the sum of the cost functions on all the m arcs of the graph. S C M F can thus be written as P(a,a ): 0 Min Yl i( i) s.t. Ax = d b ax 1 — x OLQ. Chapter 1. Introduction 2 The usual non-negativity and upper/lower bound constraint(s), if any, are naturally incorporated 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 M o n o t r o p i c Network Flow P r o b l e m , or simply an unconstrained problem. S C M F 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 S C M F , which is the computational bottleneck of a strongly polynomial algorithm. The S C M F 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 features 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 The 3 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 S C M F . 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 possible 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 the concept of 4 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 matrices. 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 complements 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. A n 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 networks transformable into regular (single-commodity) networks are studied. A n 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 answering 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 MultiProduct 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 application, 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, understand 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 graph . The set of optimal solutions of the 1 S C M F 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 decomposition 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 d e p e n d e n c e r e l a t i o n and of the d e p e n d e n 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 Theorem (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 S C M F 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 A 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]. X Chapter 1. Introduction 7 and complements (terms defined in section 4.3). The study of the unconstrained case was 2 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 Ripple Theorem (Theorem 21). To that end, we define two partial orders on the set of arcs, the less—dependent—on relation and the q u a n t i t a t i v e l y - l e s s — d e p e n d e n t — o n 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. Computational 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 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]. 2 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 problem . We show how to provide poly3 nomial time solutions to sensitivity analysis questions for the special graphs associated with singly-constrained multi-product inventory-production problems. A n extension of the concept of rims is proposed which gives sufficient conditions for the qualitative sensitivity questions 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 problem . 4 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 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]. 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]. 3 4 9 Chapter 1. Introduction 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, e , • • •, e } 2 (possibly with parallel arcs). Define the (node-arc) incidence matrix A = (Aij) m ;=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 3ft for which YZ=i ^« = 0. For a given real-valued row-vector a G 3ft n m and a real number ao G 3ft we define the additional constraint ax = ao for x G 3ft . With m 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 3ft is the sum of the cost functions on all the arcs of the graph. The S C M F can be written as P(a,a ): 0 Min i=i s.t. Ax = d . ax = Qo- A flow x = (XJ) G 3ft is said to be feasible (with respect to a demand d) if Ax = d. The m set of constrained flows is denoted by F ( a , a , d) = {x G 3ft : x > 0, Ax = d,ax = a }. The m 0 0 graph G = (N, E) together with the constraint ax = ao will be referred to as a constrained graph and denoted by (N E, a). A real-valued vector x G 3ft is called a circulation (of G) m y 10 Chapter 2. Notation and Definitions 11 if Ax = 0, and a constrained circulation if it further verifies ax = 0. A n arc e< is said to be neutral if a, = 0 and active if c*j ^ 0. We denote by C(a) = {x 6 5R : Ax = 0, ax = 0} m space the linear subspace of circulations constrained by the vector a. The support of a given vector x G S , denoted Supp(x), is the subset of indices m i G {1,2,... ,m} for which i,- ^ 0. Given a linear subspace K of 9J , an elementary m vector [Ro67] of K is a vector x € K whose support is minimal among the supports of nonzero vectors of K. A n 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. A n oriented cycle c is said to be neutral (with respect to the constraint ax = a ) if ac — 0 and active if ac ^ 0. By extension a subgraph of G is active 0 (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 12 Chapter 2. Notation and Definitions 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 c o n n e c t e d 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 c o n n e c t e d 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 c u t of G if and only if G can be partitioned into two connected subgraphs G\ = (Ni, E\) and G = (N , E ), with Ni U N = N and Ni f\N 2 2 2 2 2 = 0, so that Zj = 1 (resp., —1) if ej = (ii, i ) (resp., (i , h)) with ii £ Ni and i £ N , and Zj = 0 2 2 2 2 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 f o r e s t of G if it contains all the nodes of G but no cycles, and a s p a n n i n g t r e e 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 r e e and node 1 its r o o t . The nodes of p(i) are then the a n c e s t o r s of i and i is their d e s c e n d a n t . 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 r a p h , T its u n d e r l y i n g t r e e , and the arcs in E\T are the r e t u r n a r c s while the arcs i n T are the t r e e a r c s . 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 o n s t r a i n e d 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 13 Chapter 2. Notation and Definitions 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 G r U f e j } = (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 designate 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(mlog n + £ l o g ( | 4 | + 1) + £ log (\aj\ + 1))'. t=i j=i. 2 2 • 2 • • Part II Singly-Constrained Network Flow Problems 14 Chapter 3 Transformation to an Unconstrained Network Flow P r o b l e m C h a p t e r Abstract A linear time algorithm that reduces the solution of a monotropic networkflowproblem 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 flo 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 networkflowproblems. 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,a ): 0 Min Yl i( i) b s.t. x Ax = d OCX = Qo. • A problem similar to the above, but without the additional constraint, will be referred to as an Unconstrained M o n o t r o p i c Network Flow P r o b l e m , or simply as an unconstrained problem. Notice that if x and x are feasible, possibly optimal, for P(a, ao), then 1 2 the difference x — x belongs to the circulation space C(a) = {i£ 3? : Ax = 0, ax = 0}. 1 m 2 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 3.2 16 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? rX? 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 = (F ,F ), B N where F B is nonsingular, is of full row rank, so that (F )~ F B 1 = (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 variables x r r are called the basic variables while the called the nonbasic variables for this particular Tucker represen- tation. Clearly, for any given value x r + i , . . . , x of the nonbasic variables, the basic variables q x j , . . . , x of a vector x € K(F) will be uniquely determined by the system of equalities r = 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) • LEMMA 1 [Ro84, p. 456]. Let F € 3? « then a subset B of columns of F is a ba rx for some Tucker representation of K(F) if and only if it is a basis (in the usual sen linear algebra) for the subspace spanned by the columns of F, that is for B(F) = {y e £ : 3 x € ft« with Fx = y}. d r Chapter 3. Transformation to an Unconstrained Network Flow Problem LEMMA 2 17 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). PROOF. 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-oneforest. We will assume without loss of generality that T = {ei, e , • • •, e „ _ i } and that k = n. 2 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 A , fl.A'\ a obtained by replacing the last row of A by a, will result with a matrix A' = I 0 : a J where a / is an (n — 1) x (n — 1) identity matrix, A' = (a,j) where a,j = — c(ej, GT){, with c(ej, (7T),denoting the i th component of c(ej, GT) and ctj = ctj — YX=i <*i ija Note that a, = ctj + YAZI i c(ej,Gr)i = ac(ej,Gr) for all j = n , . . . , m and, since Q GT U {e } is an a-one-forest, d ^ 0. Now by adding to each row i of A' row n divided by n a n n and multiplied by — a, matrix, and A a Q one obtains the matrix A" = (I: A ) where / is an n x n identity n a a = (a,j) with a' a,j = a 0 - -~-a in t' = l , . . . , n - l , j = n + 1,..., m (3.1) a Now nj = — j =n + l,...,m. - 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. LEMMA 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 PROOF. Wefirstshow that any basis contains no more than one cycle. Assume, on the 18 contrary that there exists a basis B C E for the Tucker representation of C(a) which contains two different simple cycles, say C and C (which differ by more than their orientation). 1 2 Further let c (resp., c ) be an oriented cycle corresponding to C (resp., C ) . If c is a 1 2 1 2 1 neutral cycle, then A Ac 1 ac 1 0 A— c = a 0 is a linear combination of the rows of A that are in B and whose coefficients are the entries a of c , and thus not all equal to zero. Therefore B is not a basis for the linear subspace 1 {t/G & B(E,a) ^ d n + 1 : 3x G 3 i with m y = A x) a and by Lemma 1 not a basis for the Tucker representation of C(a). Clearly the same holds if c is a neutral cycle. Let us assume now that both cycles are active. Then similarly 2 A (ac )Ac — (ac )Ac 2 0 (ac )ac — (ac )ac 2 0 2 1 l [{ac )c - (ac^c } = 2 l 2 a 2 is a linear combination of rows of A a x 1 that are in B and whose coefficients are the corre- sponding entries of (ac )c — (ac )c , and thus not all equal to zero. A contradiction arises 2 1 1 2 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 THEOREM 4 a-one-forests. 19 The bases for the Tucker representation of the subspace C(a) are the • 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 -a j kEB k The subset of C(a) given by {/ 1 k= j 0 otherwise. : j £ E\B} J 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 {e } n 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) a e + ej kj k = ~ $3 °*i * ~ c = = - c £ <*njG + ej n a jei, + ej+ k £ (ej,G )-?ic(e ,Gr). a T n n ^r-a ek - ?r-e kn n (3.2) Chapter 3. Transformation to an Unconstrained Network Flow Problem Therefore, / 20 is either a neutral oriented cycle (if ctj = 0), or a weighted sum of two active J oriented cycles, in which the weights are determined, up to a multiplicative factor, by the equation a/- = 0. Observe further that any elementary vector thus constructed will fall into 7 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 / = c - (ox7ac )c 1 2 (3.3) 2 with ac ^ 0 and ac ^ 0. In this situation several cases may occur 1 2 (ii-a) c and c? are two disjoint active cycles 1 (ii-b) c and c are two simple active cycles intersecting on a single node or on a path. 1 2 (ii-c) c and c are two simple active cycles whose intersection includes more than 1 2 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. THEOREM 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 G r a p h 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 d e p e n d e n 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 f 1 and / * that respectively contain e,- and ej, and ej and e*, then there exists an elementary vector / that contains e, 3 and ejfc. A constrained graph G = (A , E, a) is said to be d e p e n d e n t if and only if every pair of 7 arcs in E is dependent. A d e p e n d e n 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 c o n n e c t e d 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 c o n n e c t e d 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 G = (N , E ,a ), T r r r r = 1, • • •, £ where a is naturally obtained by keeping in a the entries corresponding to arcs r in E . Then for each biconnected component we test whether G contains at least one active T T cycle. We will assume without loss of generality that for some 1 < p < £, 0 G\,--- ,G Po each contain at least one active cycle, and that G>„+i, • • • ,Gi contain no active cycle. THEOREM 6 Let G\, • • •, G ,G i, • • •, Gt be defined as above, and define the PQ Po+ G* = (N*,E*) = Gx U G ... U G . If p > 2 then G*, G 2 P 0 0 Po+1 , • • •, G are the depende t 22 Chapter 3. Transformation to an Unconstrained Network Flow Problem components of G. If po = 1 there exists a partition of Gi into Q > 1 subgraphs G (N*,E*,cfl), q = l,...,Q, Ei =U?=i^, E qnE"' = 0 ? whenever q ^ q' and |7Y« n 7Y» for q ^ q', such that Gi,..., Gq^G^x — G , • • •, Gt are the dependent components 2 Moreover if po = 1 and Q > 2 the dependent components of G\ are biconnected su that form a r i m (a term which is defined later) and none of them contain any active The proof of Theorem 6 requires the following four Lemmas. (N,E,a) Let G =• LEMMA 7 be a constrained biconnected graph. If there exi active cycle in G, then for each arc ej in G there exists an active cycle containing e,. Let c° be an active cycle in G and e, an arc in E. If e, is in c° the proof is PROOF. complete, otherwise let ej be any arc in c°. Since G is biconnected there exists a simple cycle, say c , that contains both e,- and e . If ac ^ 0 then c is the required active cycle 1 1 1 ; 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 whose first and last nodes, namely ni and n , belong 1 2 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 n and n and contains (resp., does not contain) ej, oriented from n to x 2 2 n\. Consider the two cycles c = p + p' and c = p + p", both oriented so that c = cf = 1. 2 3 2 Clearly c — c = p' — p" = ± c ° , therefore ac — ac = ±ac° ^ 0, which implies ac ^ ac . 2 3 2 2 3 3 Now, since both c and c contain e,- and either ac ^ 0 or ac ^ 0 the proof follows. 2 LEMMA 8 3 2 • 3 Let G = (iV, E, a) be a biconnected constrained graph, and suppose tha be written as the union of two constrained graphs Gi = (N 1, JE^a ) 1 and G = 2 (N 2, where E l 0 E 2 = 0, E l U E 2 = E. Moreover suppose that G\ is dependent and con least one active cycle. Then G\ and G are dependent. 2 23 Chapter 3. Transformation to an Unconstrained Network Flow Problem PROOF. We start by proving that for any given arc e, in G there exists an arc in G\ 2 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 , such that c}c] ^ 0. If c is a neutral cycle, that is, a c = 0, then c is an 1 1 1 1 elementary vector of H(a), e,- and ej are dependent, completing the proof. Let us assume on the contrary that c is an active cycle and define the simple cycles c and c in a similar 1 2 3 manner as it was done in the proof of Lemma 7. If ac = 0 (resp., a c = 0) then c (resp., 2 3 2 c ) is an elementary vector that contains e, and at least one arc in Gi, and the proof follows. 3 Otherwise both ac ^ 0 and ac 2 3 ^ 0, and since c and c intersect on the simple path p 2 3 (defined in the proof of Lemma 7) then / = c — (ac / ac )^ 2 2 3 is an elementary vector of H(a) that contains all the arcs of c°. Moreover, since / , = c — (ac / ac )c = 1 — ac /ac 2 2 3 3 2 3 ^ 0 for we showed in Lemma 7 that ac ^ ac , / is the required elementary vector and the proof is 2 completed. 3 • LEMMA 9 Suppose that a biconnected constrained graph G = (N, E, a) has several dependent components G q = (N ,E ,a ),q q q 9 = 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) = PROOF. N"n\Jm^N . m To show the first part of the Lemma, suppose that for some 1 < q < Q, G contains an active cycle. By applying Lemma 8 to the case where G\ is G and G is Um#? G q 2 q m 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 . Moreover since A ( l ) is the node-cut m between G i and G, any such cycle contains at least two nodes in A ( l ) . 24 Chapter 3. Transformation to an Unconstrained Network Flow Problem 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 n . Indeed if 2 this does not hold let ej be any arc of G\ which is in p, n (resp., n ) the first node of A ( l ) x 2 (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 in G\ (such a path exists for G\ is 2 connected). Since |A(1)| > 3 there exists a third node common to G\ and G, say n , and since G is 3 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 is in G , denote by n the first 3 4 node of A ( l ) encountered on c° starting from n and by,p' the part of c° which lies in G 3 between n and n . 3 4 We first look at the case where n ^ n 4 l 5 n and show that we can assume without loss 2 of generality that p and p' have at most one node in common. Indeed if they do not, let n 5 (resp., n ) be the first (resp., last) node of p' encountered on p when starting from n (if 6 x necessary exchange the names of n and n so that n is encountered on p' before 3 4 when 5 starting from n ), then replace p (resp., p') by the part of p that joins n to n (resp., n to 3 x s 2 n ) together with the part of p' that joins n to n (resp., n to rie) and exchange n and n . 6 3 5 4 2 3 Define now two arc-disjoint paths p" and p'" in G\ that join respectively ni to n and n to 2 3 n (To prove the existence of p" and p'" add to G i two arcs joining respectively ni to n and 4 3 n to n . Since G i is still biconnected there exists a simple cycle of G\ that contains the two 2 4 arcs, and removing these two arcs from the cycle results in p" and p"'). Further define the cycle c (resp., c ) obtained by joining p and p" (resp., p' and p'"). Both c and c are active 1 2 1 2 for they have arcs in G\ and in G, and they meet in at most one node, thus c — (etc / ctc )^ 1 1 2 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 , say n i , is equal to n . First, 2 4 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 be the first node of p encountered on j/ starting from n (thus n ^ n{) 5 3 5 and replace in p the portion between ns and r\\ by the corresponding portion in p, so that 1 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 n and ni to 713 (the proof of their existence 2 is similar to the proof of the existence of p" and p'" in the previous case, by introducing an arc between n and 713), and the cycles c and c? as above. For similar reasons c and c? are 1 1 2 active, and now meet in at most a single node or a simple path, thus c — (ac / a c ^ c is an 1 elementary vector, yielding a similar contradiction. 1 2 • 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 G = (N ,E ,a ) q q q q 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 G has exactly 2 nodes in common with the other dependent components. For q q = 1,..., Q we define the arc e+ = (i,j) where i and j are the two nodes common to N and q Uq'^q N q> as described in Lemma 9, and associate with it a scalar a+ = ap where p is any q oriented path in G from i to j. Moreover, if E = {e+ : q = 1,..., Q} and a + q then the induced cycle graph is the constrained graph G — (N , E , a ). + + + + q = (otg)q=i,...,Q, + We will refer to G as a rim and to its biconnected components G , q = 1,..., Q as the rim components. q 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 , + by G. Then a + + a ) be the cycle graph induce + + is independent of the choice of the paths (p') =i,...,<j and G + ? is a simple activ cycle. PROOF. To see that a+ does not depend on the choice of p suppose that there exist q two oriented paths in G , say, p and p' between the two nodes i, j G N fl N q q + such that ap ^ ap'. Clearly p — pf is a circulation on G , and therefore a sum of simple cycles [Be73, q 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 G contains no active cycles as was shown in Lemma 9. q 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 G ,q = 1,...,Q, contradicting the fact that the latter are independent. Let us assume q now that G x = (ac )c +2 contains at least two distinct active cycles, say c + +1 — (ac )c +1 +2 is a constrained circulation on G + + 1 and c . Then the vector + 2 since it verifies Ax = 0 and ax = 0, and therefore x is a sum of elementary vectors of G . Let / + elementary vectors. Since G two active cycles in G + + does not contain neutral cycles / + be any one of those is the weighted sum of + 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 p . q 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 goe 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 T H E O R E M 6. Each subgraph G Po+u • • •, G is clearly dependent since t 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' - is a neutral 1 7 Chapter 3. Transformation to an Unconstrained Network Flow Problem cycle, that is, a c ,,J = 0, then c ,,J 27 is an elementary vector and hence e,- and e- are dependent. 7 Otherwise ac*'- ^ 0, and since po>2 there exists an active cycle, say c, in some G 7 m with 2 < m < p such that / = c *' — (ac'^/ac)c is an elementary vector of G with /,•/, ^ 0. (it) e,1 0 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*, G +i, • • •, Gt) are dependent, there must exist an elementary Po 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. EXAMPLE 1 Figures S.l-b and S.l-c illustrate the decomposition procedure applie the graph G given in Figure 3.1-a (the circled numbers on the arcs designate the no entries of a). As shown in Figure 3.1-b, G hasfivebiconnected components of which 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 c: Aggregation into 3 dependent components Figure 3.1: D e c o m p o s i t i o n o f t h e g r a p h G 28 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*, E , a'), I — 1, • • • , Q such that no subgraph contains an active cycle and, if Q = 2, l A ^ n i V = {ii,* }, whereas if Q > 3, 2 2 N lnN i+1 = {i } t for t = 1,... , Q - 1 , 7V«niV = {i }, 1 Q JV'niV* = 0forifc>£+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 denoted by i i , i , etc... The reader will notice that, depending on a, the graph may be a rim 2 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 i not a rim notice that, if it were one, the only possible bolts would be the nodes n\ and n , 2 the cycle e\ — e is active. Therefore, if G were a rim, it would have two components, one 2 of which would contain one of the arcs either e\ or e and the rest of the graph. However, 2 both subgraphs G\{ei} and G\{e } contain active cycles and thus do not qualify as rim 2 components, proving that G is not a rim. • In the following Theorem we present a characterization of the bolts of a rim. T H E O R E M 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 adjacen 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 a n d G r a p h s Chapter 3. Transformation to an Unconstrained Network Flow Problem PROOF. 31 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 G i (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' , then x 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 v be the largest ancestor 0 of all R-arc tails, that is, v — max{l : / £ p(i) (i,k) 6 R) and w the largest R-arc head, 0 0 that is, w = max{k : (i, k) € R}. The above definitions are demonstrated in. Figure 3.4. In 0 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. Ifw < v , the intersection of all R-cycles is the path p(w ,vo), wherea Q 0 if v < WQ this intersection is empty. Q 0 32 Chapter 3. Transformation to an Unconstrained Network Flow Problem PROOF. For any R-cycle c(ej, T), with ej = (i, k) £ R, v is an ancestor of t and w > k. 0 0 Thus, if wo < v , then k < wo < VQ < i, p(wo, vo) is a part of c(ej, T), and hence is common 0 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, w belongs to p(i). Moreover, from 0 the definition of VQ, vo also belongs to p(i), and thus v 0 < w implies that u is a strict 0 0 ancestor of wo. Now, there exists another R-arc, say, ej» = (£', k) € R, such that p(vo, i') and p(u , wo) have only VQ in common, for otherwise the immediate descendant of VQ on p(vo, WQ) 0 would be an ancestor of all R-arc tails strictly greater than VQ, contradicting the definition of v . We show that c(ej/, T) has no node in common with c(ej, T). Indeed, if k < VQ we can 0 write c(ej/,T) = p(k,i') + ej- = p(k,v ) + p(v ,i') + Cji. 0 0 Now, the nodes of p(k, VQ) are all ancestors of VQ and thus, since VQ < wo, p(k,v ) contains no descendant of wo and from the 0 choice of ej# neither does p(vo,i'), whereas c(ej,T) uses only descendants of w . The same 0 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. PROOF. 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 33 Chapter 3. Transformation to an Unconstrained Network Flow Problem ac(ei, T) = —ac(e , T). By Lemma 13, the intersection of c(ei, T) and c(e , T) is a path, say 2 2 p(w,v), with U J < u> < v < v and combining with Corollary 11 we obtain that p{wo,v ) 0 0 0 contains all the bolts of G, and thus WQ < VQ. Therefore c = c(ci, T) — c(e , T) is an oriented 2 cycle of G, which is active for ac = ac(ei,T) — ac(e ,T) = 2ac(ei,T) ^ 0, and thus c also 2 contains all the bolts of G. Now, since v and w are the sole nodes common to c, c(ei,T) and c(e , T) by Corollary 11 they are the only two bolts of G and hence v = VQ and w = WQ. 2 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(w ,vo) lies in, say, G\ then c(ei,T) — p(u>o,t>o) and 0 c(e ,T) — p(wo, vo) lie in G , and therefore so does c. We have obtained an active cycle c 2 2 inside a rim component, and thus a contradiction to Lemma 9. • In the following we will denote by a the unique value of ac(ej,T), ej G R, whenever T 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 tha 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(w ,v ) or vo (resp., wo) if 0 0 it is the tail (resp., head) of all R-arcs. Let us first assume that i = v (resp., wo) but 0 0 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 i 0 is a bolt, and by Corollary 11 all active cycles do), and thus through He. Let i and i x 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\, i ) the 2 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 i are distinct nodes of Hi. Now, since Hi is biconnected there exists a path in Hi, say p, 2 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,i ) 2 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 , i ) in c(ej, T) by p results in another active cycle c(ej,T) — p(ii, i ) + p x 2 2 of G that does not contain io, contradicting the fact that io is a bolt. The proof for the case where io & {VQ, W ) is a bolt but not a cutnode of H on p(vo, Wo) is identical except that we 0 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(w , VQ) are bolts of G, and from Theorem 12 it suffices to show that all active cycles of G go 0 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 6 S u f l ! / j ( i ) ^ ) - Now, let Hi be a branch of G that contains at least-one cutnode of c e 1 > H on p(w , v ), say, i . If we regard cycles as flows, then clearly no flow corresponding to an 0 x 0 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> ,t;o) contains all the bolts 0 of G, and hence i ) . Thus, the flow corresponding to c leaving Hi through i i is equal to x iHejeKJ/j- Now, since the S-cycles are neutral and ac(ej,T) = a for all R-cycles, the fact that c is active implies ac = T T.^syj c{ h ) + T, ,zRyj<xc(ej,T) = a £ e f l 2 / ; ^ 0. a & T r c e > Chapter 3. Transformation to an Unconstrained Network Flow Problem \ac\ = | a | , £eyefl Vj From Lemma 10, r = tna * *i * s n e fl° w 35 corresponding to c leaving Hi through i i is nonzero. Therefore i\ is a node of c and the proof is complete. Similarly, if v Q (resp., u>) is the tail (resp., head) of all R-arcs then obviously deleting 0 VQ (resp., wo) yields a graph with no active cycle and, by Theorem 12, vo (resp., tu ) is a 0 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' and i", assigning the arcs of each of these subsets to i[ and to i", x 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 will be determined in Algorithm I. x Figure 3.3: A o n e - r i m (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 36 Chapter 3. Transformation to an Unconstrained Network Flow Problem 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}. T H E O R E M 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, w < v 0 0 and p(w ,v ) Q 0 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 = J2aeR i * e sa c u * °f G i , for all paths from iq to i\ in G i contain a forward R-arc. Any cycle c of G i can be written, as in Lemma 15, c = Z)eieSuH » ( «j^ )> c 0 = c*z = £ e i € f l C , - , thus ac = a J2 eR i T c ei c = e 1 0 a n ( a n < c ^ i l since cuts and cycles are orthogonal s neutral (recall that a is the unique r 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^show 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 w , and a unique color is assigned to each node. The coloring of the 0 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. T H E O R E M 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. We start by showing that all the white branches are rim components of G. To PROOF. 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 (/( )i ) ( u 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(w ,vo) it contains u. Also recall 0 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). ALGORITHM 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,-. N o d e Labelling. a 7 Set o f = 0, then, whenever a node v is visited for the first time set = <xj( ) + oti where e» = (f(v),v). v C o m p u t a t i o n of x. Recall that o% — ap(y). 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). R e t u r n 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. 42 Transformation to an Unconstrained Network Flow Problem 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> v and we color u in red (notice that it is not indispensable to also color in red all the Q pink nodes between u and its red ancestors). The last node to be colored in red is v . The 0 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 < WQ we conclude that G is not a rim. 0 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, • • •, G , while G\ is equal to the remainder of the graph. 2 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 i i 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 C o m p l e x i t y of A l g o r i t h m 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 M o n o t r o p i c 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 S C M F , 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 modified 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 A of problem P(a, a ) a can be written as 0 Chapter 3. Transformation to an Unconstrained Network Flow Problem A 44 1 A 2 i i i \ i i \ * A' a a 1 where A (resp., A ,..., 1 a 1 2 A ) is the incidence matrix corresponding to Gi (resp., G ,..., Gt) 2 1 2 and a (resp., a , . . . , a*) the parts of a corresponding to the arcs in G\ (resp., G ,..., Gt). 1 2 2 Following the notations used in Theorem 6 assume without loss of generality that the biconnected components Gi, • • •, G components G +i,... Po a po+i ( esp., a P o + 2 r PQ of G contain active cycles, whereas the remaining biconnected ,Gt do not. Since G +i, • • •, Gt do not contain any active cycle then Po , • • • , a*) is a linear combination of rows of A Po+1 (resp., A P 0 + 2 , • • •, A ) and 1 thus by an appropriate modification of a and a we can assume, without loss of generality, 0 that a P o + 1 = • • • = a = 0. Clearly if po = 0, that is, if no biconnected component of G 1 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 A so that the a row follows the last row of A ° then clearly p a A a will have the block-diagonal form. We will denote the north west block containing the rows of A ,...,A 1 Po 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, a ) into / — po + 1 subproblems, only one of which 0 (corresponding to the north-west block) is a S C M F , the other I — po being unconstrained 45 Chapter 3. Transformation to an Unconstrained Network Flow Problem 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 S C M F . We first require the following construction. CONSTRUCTION 1 G = (N ,E ,a ), q Q to N q q and N Let G = (N,E,ct) q = 1,... ,Q > 2 and q be a rim palm graph with rim components GQ+I = G\. Denote by i the bolt that is common q (see Figure 3.6-a). Consider now the expanded rim G — (N,E,a) obtained q+1 from G by splitting each bolt i into two copies i' and i", in such a way that all the arcs of q E q (resp., E ) incident to i q+1 q q in G are now incident to i' (resp., i" ) in G, and by adding q q to E the arcs e = (i' , i' ), q = 1, • • •, Q, with an associated parameter q q q = 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 ,T), 7 i € N, ej £ E in G. It will be useful to notice that p(i) = p(i) + £; r;(,») e Vi £ N, ap(i' ) e q q = dtp(i ) = ap(i ) = cxj^ for all q = 1, • • • , Q and ap(i) = aj for all other nodes. Moreover q q c{ej,T) — c(ej,T) for tj £ S and c(ej,T) = c(ej,T) + a w _£, I,...,Q = e for ej £ R. Recall that q is the unique value of ac(ej,T), ej £ R, and define on G a demand vector d as follows h = £ iez>(t,) d, + ^ ( a o - E ^ f ) a t/i forq = di» = d d,- = d,- iq l,---,Q, (3.4) - J,, for all other nodes.O Transformation to an Unconstrained Network Flow Problem c: The decomposed rim Figure 3.6: Rim Decomposition and Expansion 46 Chapter 3. Transformation to an Unconstrained Network Flow Problem T H E O R E M 18 47 Suppose that a biconnected constrained palm graph G = (N, E, a) has several dependent components, say G = (N , E , a ), q = 1,---,Q > 2. q q 9 q Then the set of constrainedflowson 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 depende 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{ is shared by i' and i' ' in such a way that q q + J,» = d{ . q We start by temporarily q apportioning the demand at the bolts between their respective copies by setting d^ = 0 and d{» = di for q = \,---,Q, di = d< for all other nodes. q 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). the additional constraint ax = a , we pick any R-arc 0 Since this flow may not meet £ 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 also meets the demand requirements for, since c(ejt,T) is 1 a cycle, Ac(e , T) = 0, and A x = Ax° + l/a 1 r k (a - E,#i <fc*f )Ac(ejt, ) = Ax° = d, as well T 0 as the additional constraint, for ax 1 = a E ^ W + T( °-E^n«c(eic,T) a = E ha* + (a - J2 di<*J) = «o 0 48 Chapter 3. Transformation to an Unconstrained Network Flow Problem (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 constrained flow, say x , and of some constrained circulation, say, x . 1 2 As in the proof of Lemma 15, x can be written x = J2cjesuRyjc( jiT) where a x = 0 implies that Y^ejeRVj — 2 2 e 2 0, and thus the general expression of any constrained flow on G is given by x =x + x 1 = E*P(0 + - 7 ( « o - E ^ f ) 5 ( e * . r ) + 2 t/l Q £ e^esuR %c( ,r). Ci (3.5) Further, notice that the entry of p(i) on some arc e is equal to 1 if p(i) uses the arc q e,, that is, if i is a descendant of i ' in G, and to 0 otherwise, whereas the entry of any q R-cycle (resp., S-cycle) on that same arc is equal to 1 (resp., 0). Therefore x = x^ + x ^ 2 iq = X)te.D(,») di+l/oc (ct —J2i?i di J) for all 9 = 1, • • •, Q and is independent of the constrained T Q Q 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' and share di can then be adjusted in order to restrict theflowon g q the arcs e , q = 1, • • •, Q to zero by adding x , to d^ and subtracting it from d^, resulting q g in the adjusted version of G where d<; = 2Z <* • . + - 7 ( 0 0 - 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, = (i ,i ) a flow equal to the change q of q resulting in x = 0 for all q = 1, • • •, Q. Now, deleting the arcs e,, q = 1, • • •, Q that iq 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 49 Chapter 3. Transformation to an Unconstrained Network Flow Problem 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 D(i) ^« f (recall that, by definition, a g € aj = 0), and a is also obtained in Algorithm I. T 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\ — xj + 2 t 2i23 — 2x37 + 3X.JI + 3xsi = 28 and the demands di = di = d*> = d7 = 0, and d = 4, <f3 = I, de = —5 2 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), the unique value a T = ac((4,1),T) = ac((5,1),T) = 6. ej £ R takes on Thus, from Theorem 16, G is a rim whose two components Gi and G have for respective node-sets Ni — {3,4,5,6} an 2 N = {1,2,3,7}, its bolts being the nodes ii = 3 and i — 1. Figure 3.7-b illustrates the 2 2 expanded rim, G in which the bolt i\ (resp., i ) is split into nodes i' = 3' and i" = 3" (resp 2 x i' = 1' and i' ' = I"). Given that aj = 0, aj = 1 aj = ct% = aj = aj = 3, aj = 1, then 2 2 from (3.4) we obtain .€D(3) = ' t#l a dyi — d$ — <f3/ = —1 and di> = d~v = E 2 ieD(i) i + -r( o - E ^ « ^ ) = d a a a 6 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 51 Chapter 3. Transformation to an Unconstrained Network Flow Problem We now return to the original problem P(a, a ) and use the results obtained above to 0 present Algorithm II which decomposes a S C M F defined on the constrained graph G = (N, E, a) into independent subproblems on the dependent components of G. After a feasibility 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 contain 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 S C M F (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> = (N , E , a ) r = 1, • • • , £, r r T * 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 p = 1), 0 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 P : Min k bj( ) £ Xj s.t. A x = d k k k = po + k l , . . . , e where x = (x,) ,e^ and d = (d,),-^, for k — po + 1,... ,£. If, further, non k e k of the biconnected components of G contain active cycles that is, if po = 0, and if ocYlr=i,-,t ( ) x r — o (where x(r) is the feasible unconstrained flow for the subgraph a <S>, computed as "x" in Algorithm I) then P(a, ao) is feasible and equivalent to P , k k = 1, • • • ,£ and thus is transformable to an unconstrained networkflowproblem. If, However, po = 0 and aJ2r=i,-,t ( ) i o then P(a,a ) is infeasible. 1 x r Step 5. Q 0 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,) . £;. and d* = (d,)i £;.. P{a, Q ) is equivalent to P*(a, a ), together e € with P , k = po + 1, • • • k € 0 0 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 P : q Min s.t. £ bjixj) A'xW = $ti q = l, 9 where x^ = (x,) .E,, and d^ \q = 1,••-,(?, is the part of the modified demand q ei€ vector J obtained in (3.4) corresponding to N . The original problem P(a,ao) is then q " equivalent to the Q + £ — 1 independent unconstrained problems P*, k = 2 , . . . a n d P , q = 1,..., Q, and thus transformable to an unconstrained problem. q Note that the problems P q 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 onevariable problems of the form Min{6j(x^) : x^ = cPf^} where ej is the unique arc of G q (in particular, this is the case of the component {ei} of the expanded version of a onerim). 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. P r o o f of the V a l i d i t y of A l g o r i t h m II The preliminary decomposition into subproblems corresponding to G*, C + i , • • • , Gt is a P o direct result of the block-diagonal nature of A a 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 (p Q = 0). We choose for x ° the flow X)r=i,. ;t ( )> where x(r), r = l,---£, x r is a feasible unconstrainedflowon 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 C o m p l e x i t y of A l g o r i t h m 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(\E \ + \N \) on each biconnected component r r G for a total of 0(rn + n) and Steps 4, 5 and 6 also take linear time, thus Algorithm II runs T in 0(m -f n). It is interesting to note that in the event where P(ct, a ) is transformable to an uncon0 strained network flow problem its constraint matrix A is not necessarily totally unimodular. a The following example shows a constrained network flow problem that is transformable to an unconstrained one but whose matrix is not totally unimodular. EXAMPLE 4 Consider the graph G with two nodes and two arcs given in Figure 3.8 together with the additional constraint x\ — x = 1. G is clearly a rim whose two compone 2 have respectively {e\} and {e } as their arc sets, and the bolts of G are i\ and i . Thus any 2 2 problem P(a, ao) on G is transformable to an unconstrained networkflowproblem. However the constraint matrix of such a problem has ["l !*] 1 s a a submatrix, whose determinant is equ to 2, and thus the constraint matrix is not totally unimodular. • Figure 3.8: T h e r i m 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 problem", 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 underlying 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 ) ) £ ; . , the subproblem e>€ P*(a, QQ) on the constrained dependent subgraph G* can be decomposed into two independent subproblems, say, P ' and P ", over two subsets E{ and E of the set of arcs E*. Since t 2 2 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.E . 2 Consider now the problem P*(a, a ) obtained by setting bj(xj) equal to zero if Xj = fj or if ej G E^, 0 and to + 0 0 otherwise. One of its optimal solutions is x = / , and if the subproblem is indeed decomposable then the projection x = f obtained by setting to zero all the components of 1 1 / that correspond to arcs in E should form a feasible solution for P{. Moreover, the zero 2 vector on E\ is clearly optimal for P ', and since the solution set of P*(a, a ) is the Cartesian 2 0 product of those of P{ and P it contains f which is therefore feasible for P"{ct, ao). Thus 1 2 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 / , which is strictly contained in that of / (for x / has nonzero components on at least one arc of E ), contradicting the fact that / is an 2 elementary vector, and proving our claim. A similar proof holds if P*(a, a ) decomposes into 0 more than two subproblems, and this trivial extension is omitted. The foremost consequence of the above is that if the original S C M F 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 detect 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. 56 Chapter 3. Transformation to an Unconstrained Network Flow Problem 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 A corresponding to the dependent a 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 e , between x its two copies, such that the additional constraint is equivalent by a linear transformation to x ix (c) = 8, where 6 depends on a and the demand vector d. G is either a one-rim or a rim and i\ is a bolt. PROOF. * 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. Moreover, 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 e = (i\, i"). For the constraint x t Sl = 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 i n the expanded graph G defined i n Theorem 19 is a linear function of the quantity ax, say, x gl = /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 ^((x Sl — 7)//?) = 0, and to + 0 0 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. Special Types of Constraints 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. Multiple Constraints If the original problem includes several additional constraints, our procedure can be applied successively to each of them. It is then necessary that the S C M F 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 C h a p t e r 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 lessdependent-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 Theorem 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 sam (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 l 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. 60 Ripples, Complements and Substitutes 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 realvalued function on 3ft. The m-vector t = (tj) ^E is called the parameter vector and lies ej in the lattice product T = x^e-E^'- The cost of a flow x = (ij) 6 3ft is the sum of the cost m 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 M o n o t r o p i c Network Flow P r o b l e m ( P S C M F ) , also referred to as the Constrained P r o b l e m , can be written as m p(cx,a ,ty. 0 Mm E M ; ' * ; ) 3=1 1 s.t. Ax = d ctx — ao. We will denote by X(t) the set of optimal flows of P(a,a ,t). 0 A problem similar to the above, but without the additional constraint, will be referred to as the Parametric U n constrained M o n o t r o p i c Network Flow P r o b l e m , or simply as the Unconstrained P r o b l e m . The usual non-negativity and upper/lower bound constraint(s), if any, are naturally 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 i n 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 o n the magnitude of change of the optimal flow in two given arcs, the main results being given in the Ripple Theorem (Theorem 21). To that end, we define two partial orders on the set of arcs, the l e s s - d e p e n d e n t - o n relation and the q u a n t i t a t i v e l y - l e s s - d e p e n d e n t - o n 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. Computational 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 ~ n o r m of the corresponding parameter variation. Finally, Theorem 34 shows the subadditivity property of the minimum cost. 4.2 The Ripple Theorem For Constrained Graphs. 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 62 Chapter 4. Ripples, Complements and Substitutes 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 th entry, then there exists an optimal solution x' to P(a,a ,t') Q 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. T y p e (I) Each neutral biconnected component is a dependent component. T y p e (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 component. T y p e (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 associated subproblem is unconstrained, and therefore one can apply the qualitative theory developed by Granot and Veinott [GV85] for Unconstrained^Monotropic Network Flow Problems. 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 4.2.1 63 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 for all / e H(a), fifj ^ 0 f ? 0 k (for all / € Hj(a), / , 0 / * ^ 0). 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 equivalence 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. EXAMPLE 5 Consider the graph G with 8 arcs and 6 nodes given in Figure 4-9, with cti = 1/2, Q = 1, a , - = 0 for all i ^ 1,6. 6 vectors that contain both Clearly e3 =\ ee, for the only elementary and ti (resp., e& and e ) are, up to a multiplicative factor, 2 f = 2(ci + e + e ) - (e + e + e ) = (2,2,2,-1,-1,-1,0,0) and g = 2 ( d + e + e ) 2 3 4 5 6 2 3 Chapter 4. Ripples, Complements and Substitutes 64 (e6 + 67 + eg) = (2,2,2,0,0, —1, —1, —1), which also contain e (resp., e$) and thus e <\ e& 6 (resp., e > 3 t$). However, deleting e and e$ leaves a connected graph. 2 3 3 • Figure 4.9: E q u a l l y dependent pairs of arcs need not disconnect the graph T H E O R E M 20 Let G = (N,E,a) e be arcs in E. Then e,k PROOF. be a constrained dependent graph and let e,, ej and e if and only if deleting e leaves e, and ej independent. k k 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 e and H'(a) to be the set of elementary vectors of the constrained circulation k space of G'. H'(a) = {/E It follows trivially from the definition of elementary vectors that H(a) : f = 0}. Now, e,- <f e if and only if k k V/€iT(a), fifj^O VfEH(a), / => f ?0 k or equivalently which is the same as t = 0 => fifj = 0 65 Chapter 4. Ripples, Complements and Substitutes V/€/T(a),/,/,=() completing the proof. • Note that Theorem 20 provides a linear time algorithm to verify whether three arcs e,-, ej and e satisfy e,- <j e , for it suffices to decompose G\{ejt} into dependent components k k 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 e holds. k In order to do so, we will start with all the possible configurations of a non-dependent graph G\{e } and investigate the possible ways of adding an arc e = (ni,n ) that will result in a k k 2 dependent graph. For e, <j e to hold, it then suffices that the arcs e, and ej belong to two k different dependent components of G\{e }. The classes of non-dependent graphs that will k become dependent when an extra arc e is added in an appropriate fashion are described k below. We start with the case where G\{e ] is biconnected, and therefore is a rim (e,- and k ej belong to two different rim components). • If one (resp., two) of the rim components of G\{e }, say G' (resp., G', G"), contains (resp., k contain) both ni and n , then G is dependent if and only if e does not close a neutral 2 k cycle in G' (resp., in G' or in G"). For otherwise G would be a rim and G'U{ Jfe} e (resp., G'\J{e ) or G"\J{e }), one of its rim components, contradicting the fact that k k G is dependent (notice that, since G' is neutral, one of the cycles that e closes in G' k is neutral (resp., active) if and only if so are all the cycles that e closes in G') (see k Figure 4.10-(i)) . • If none of the rim component of G\{e } contains both ni and n , then let c be any active k 2 cycle of G\{e } that contains ni and n , and write c = pi — p?, where p and pi are k 2 x two arc-disjoint oriented paths from n to n\. Notice that ac = api — ap ^ 0, and 2 2 since G\{e ) is a rim, the set {ap\,ap } does not depend on the choice of the active k 2 cycle c. Now, since G \{ejt} contains active cycles, so does G, and thus G is dependent r if and only if it is not a rim, that is, if both cycles e + p and e + p are active or, k t k 2 equivalently, if a* £ {api^ap^} (see Figure 4.10—(ii)). Figure 4.10: Construction of the dependent graph G when G\{e ] is a rim k We now turn to the case where G\{ek] has several biconnected components, say G\, • • •, Gi, and since G\{e ) is not dependent, then at least one of these, say G i , is neutral (e,- and ej k 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 e is added to a neutral (sub-)graph G', then k G'U( Jfe} e is either neutral or one of its biconnected components, which contains e^, is a rim for all the active cycles go through e . Therefore, if G' is neutral, G'\J{e } is active if and k k only if all the cycles that contain e are active. k • Let us first assume that one of the biconnected components of G\{e ) contains both ni and k n . Clearly, it has to be a neutral one, say G\, and the cycles created have to be active, 2 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{ *} is then e a rim with bolts n i and n and rim components G\ and {e^}.). Moreover G , • • • , G/ 2 2 need to be active and thus G\ is the unique neutral biconnected component of G\{e } k (see Figure 4.1 l-(i)). Chapter 4. Ripples, Complements and Substitutes 67 Figure 4.11: Construction of the dependent graph G when G\{e ) is not biconnected k 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 . Recall that we assumed G to be of type (II) or of type (in). If G is of 2 type (II), then all the arcs that lie in neutral biconnected components of G\{e } belong k to some active cycle in G, and therefore to some cycle that contains e , so that all the k 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\{e }, including k all the neutral ones, form a chain, and n\ (resp., n ) belongs exclusively to the first 2 (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\{e ] be part of the chain and at least one of them k be active, for otherwise G would be a rim (see Figure 4.11-(iii)). 4.2.2 Quantitative Less-Dependent-On Relation For any three arcs e,, ej and e 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 k less d e p e n d e n t o n ej t h a n e is and write e, <* e (resp., e, <] e ) if and only if k for all / <E H(a), k /,/, ^ 0 => k | / , | < | / * | (resp., | / , | < |/ |) fc or, equivalently, if |/,-| < |A| (resp., |/,-| < |M) for all / G Hj(a). If ei <' e and e < ' e, we say that e, and e are q—equally d e p e n d e n t o n ej and write k k k e,- = ' t . Clearly, e, = ' e if and only if for all / £ Hj(a), k k = 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 - e q u i v a l e n c e classes S] induced by it are partially ordered by <'. We will denote by S](k) the unique element of £ ' that contains arc e . k 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 equivalent to Granot and Veinott's [GV85] less-biconnected-to relation (where <j e if and k Chapter 4. Ripples, Complements and Substitutes only if any simple cycle that contains 69 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 x = x 2 by the configuration 3 of the graph. Therefore for any elementary vector f £ H(a), fi = 2f 2 ei = 2 e 3 but e\ 7^2 3 e and f = / . Hence, 2 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 T h e Ripple T h e o r e m 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 T H E O R E M 21 T h e Ripple T h e o r e m . 70 Let G = (N, E, a) be a dependent constrained graph of type (II) (i.e., several active biconnected components) or type (IH) (a unique act biconnected component which is neither a rim nor a one-rim) and suppose that t and t' diffe only in one component ej 6 E, b (-,t ) is convex for each e € E\£j(j), k k x is an element of k 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 P r o p e r t y : For any two arcs e, and e in E, if e,- <j e then k k Wi-XilKMkilx't-Xk] (4.6) where. Mki = max{|/,/M : / e H (a)}. k (4.7) (R.3) Q—Ripple P r o p e r t y : \x' — x \ does not increase the less quantitatively dependen k k e is on ej. k PROOF. 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 z = 0 for all k G £f{j) since, k by definition, any elementary support that does not contain ej does not contain e* either whenever e =j ej. Therefore, by the convexity hypotheses, k 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 z > 0 for all a (4.10) a /a conformal and, from the conformality of the sum, \x't-xt\= E *«!/»< I for all*. (4.11) conformal Moreover, <j e implies that f k ai the definition of M , \f \ < M \f ki ai ki ak = 0 for all elementary vector / „ G Hj(a)\H (a) k \ for all f G H (a). a k and, by Thus, conformal conformal conformal - E /o6H>(a)nH (Q) k conformal < E *.M«I/.J = E ^M«i/ j = M«|xi-**l e Za6lfj(«)nH («) faZHj(a) conformal conformal t completing the proof of (R.2). To prove (R.3) we need to show that for any two arcs e,-, e G E such that e,- <' e we k k have |x- - x,| < |x' - x \. By hypothesis, | / | < | / J for all f G Hj(a), thus (4.11) yields f c l * k i ai E a E /a€Hj(a) faeHj(a) conformal conformal a *.l/.J = l**-x*l (4-12) Chapter 4. Ripples, Complements and Substitutes completing the proof of (R.3). 72 • Notice that under the assumptions of the Ripple Theorem, the following special cases are trivial consequences. • If x' = Xk then x\ = x,-. k • 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 quantitativelyless-dependent-on relation, since if e,- = ' ejt, then by definition | / - | = | / J for all a a f G Hj(a), and thus by (4.11), |x- — x,| = \x' — Xk\. However this is no longer the a k case for the less-dependent-on relation as demonstrated in example 7 below. EXAMPLE 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 2x + X5 = 3. 4 Let the demand be given by d{ = 0 Vi and the costs by bi(x ,t ) = (x -t ) , 2 1 1 1 1 6 (x ,i ) = | x - l | , 9 7 r 7 bj{xj,tj) = 0 Vj^l,7. Figure 4.13: T i g h t bounds in the R i p p l e T h e o r e m 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, e 4 and e$ are in the same d-equivalence class £ j ( 5 ) . Indeed, the sole elementary vector / = (ei + e -f e ) — 2(e + e + es) = (1, —2,1,1, —2, —2,0) that contains e± and e (resp., 4 3 2 6 4 ande ) also contains es (resp., e J , and thus e =f es. However, \x' —z | = 1 ^ 2 = \x' —x \. 5 4 4 4 4 s • Before discussing in subsection 4.2.4 the computational complexity involved in determining 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. EXAMPLE 8 T i g h t bounds in the Ripple T h e o r e m . Consider again the graph given in Figure 4-13. The elementary vectors that contain both e\ and e are 2 f= (ej + e + e ) - 2(e + e + e ) 9= (ei + e + e - e + e ) 4 3 2 and thus M 12 2 6 6 7 5 3 =(1,-2,1,1,-2,-2,0) =(1,1,1,0,0,1,-1) = max{|2/l|, |1/1|} = 2. Now, if we let t = (0,0,---,0) and f = (l,0,---,0) the unique optimalflowsfor 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' — x \ = Mi \x[ — xi\ and the bound given in equation 4-6 is tight. 2 2 2 • « 4.2.4 C o m p u t i n g the Bounds in the R i p p l e T h e o r e m 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. s Chapter 4. Ripples, Complements and Substitutes T H E O R E M 22 74 The problem [M] of computing the coefficient M =max{\f /fj\:feHj(a)} jk k for any given pair of arcs (ej, e ) of a constrained graph G = (N, E, a), is NP-Hard. k PROOF. Assume that there exists an algorithm AI[M] which, given a constrained graph G = (N, E, a) and fwo arcs e , e £ E, evaluates the coefficient Mj , and runs in at most 3 k k P[M\{ ) elementary operations, where P^r](s) is some function of s (recall that s is a measure S 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 whose entries will be called weights, define the constrained graph G* = (N',E',a*) N* = NU{n E" — E U { e M by + l,n + 2} = (n + l , n + 2 ) , e m+1 and cti m + 2 = (n + 2,n + 1)} if i < m a' = { —1 if i = m + 1 0 if i - m + 2 and let e be any given arc in G (See Figure 4.14). Now, since no simple cycle goes through k both e and e k 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 ) + fc k where c is an active cycle of G for which c = 1 and f k k (4.13) is determined by (3.3), resulting in 75 Chapter 4. Ripples, Complements and Substitutes m+2 Figure 4.14: T h e extended graph G* fk = -a'(e +i +e m m+2 )/or"c = l/a*c = 1/ac. (4.14) Therefore, for the constrained graph G*, we can write M where Hl(a') k m + 1 = mox{\f /f \: = max{\l/f \ : ( c = mai{|acj : c = 1, c simple cycle of G) m+1 k k f e H;(a*)} m + 1 +e m + 2 + f c) € ^(a*)} k k is the set of elementary vectors of the circulation space of G* that contain e . Thus AI[M] will, when applied to G' and a particular pair of arcs (ejt,e i), determine k m+ the oriented cycle of maximum weight that contains arc e . k 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 (s)). [M] Since the [MWOSC] is NP-Hard, so is [M], completing the proof. • In the following we present five examples where the value of Mj can easily be computed. k For convenience we will assume without loss of generality that all elementary vectors / encountered with fj ^ 0 have fj = 1. Arcs in R i m s . 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 e is a rim k (are rims). At this point, it is interesting to notice that a biconnected subgraph, say G\, 76 Chapter 4. Ripples, Complements and Substitutes 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 e are either simple k neutral cycles'of Gi or active cycles of G\ paired with active cycles not in G\. All such elementary vectors verify | / j | = \f \, and thus Mj = 1. k k • If at least two of the biconnected components of G, say G\ and G , are rims, then for 2 every ej G G\ and e G G , any elementary vector that contains both ej and e is of 2 k k the form f = c + fc 1 2 k where c and c are respectively active cycles of G\ and G , c* = c\ = 1 and f 1 2 2 as in (3.3). Therefore \f /fj\ = | ( — a c /ac )/l\ —ac jct(? x 1 2 k k = {ac 1 /ac \ 2 = is independent of the choice of c and c , and Mj is equal to that ratio. 1 2 k T h e s u p p o r t o f a o n s o m e 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 a r c s . Suppose now that a,- = 0 for all arcs e,-, e, ^ ej, e and e,- belongs to the same biconnected compok nent (s) of G as ej or e . Since the above treats the case where the two ares lie in different k biconnected components of G, we may assume that ej and e lie in the same biconnected k 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\ = \a \) or a pair of active cycles, say / = c — (ac^/ac )^, and l 2 k we may assume without loss of generality that cj = c\ = 1 and c\ = cj' = 0. In either case, \f /fj\ = \aj/a \, and thus M k k jk = \ctj/a \. k 77 Chapter 4. Ripples, Complements and Substitutes • We now suppose that G has several active biconnected components, and that ej and e k 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 e , together with another k active cycle in another biconnected component. \fk/fj\ = 1, and thus M jk For such an elementary vector / , = max{l, \ctj/a \}. k • 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 e , only those that are contained in every simple cycle that also k contains ej and those that are contained in every simple cycle that contains e* may 1 have nonzero entries in a (see Figure 4.15). Indeed, as far as the study of cycles goes, we may replace ctj (resp., a ) by ac, where c is any cycle that verifies Cj = 1 (resp., k 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 In a graph G, the set of arcs contained in every simple cycle that contains a given arc ej is the equivalence 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. J Chapter 4. Ripples, Complements and Substitutes 4.2.5 78 C o m p l e x i t y Issues A t t a c h e d to the Qualitative L e s s - d e p e n d e n t - o n Relation 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 e . The computation k 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) PROOF. are such that e,- <' ejt is NP-complete. Assume that there exists an algorithm AI^QLD) which, given a constrained graph G = (N,E,a) and a triplet of arcs ei,ej,e k £ E, determines whether e,- <' e*. We claim that AI[QLD] t t be used to solve the decision version of the Maximum Weight Oriented Path ca [ M W O P - D ] defined as follows. Given a vector of weights (wi) £ 3? , two nodes say n and n , and a real number m x 2 A > 0, do all oriented path p from n\ to n verify wp < A ? 2 The [MWOP-D] known to be is NP-complete (see [GJ79, p. 213]). Now, add to G the arc eo = ("2, i ) , define the vector a by n -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 e and e 0 rn+2 , |/ | 0 < |/ +i|m From (4.13) and (4.14), this is equivalent to |l/a*c| < 1 for any active cycle c of G* that contains e , that 0 is, \ac\ > 1 for all active cycles of G that contain e . This is trivially equivalent to \ac\ > 1 0 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 to n , we can write that AI^QLD] will return a YES if and only if x 2 for all oriented paths p from ni to n . Now, since |tuc| < 2*, 2 (tup — 2") > 1 and thus wp < X for all path p from rti to n , solving the [MWOP-D]. Since the reduction from one problem 2 to the other is clearly linear, the proof follows. • Recall from Subsection 4.2.1 that e, < ' e =>• e, <^ e*, and thus the list of configurations k for which e,- <j e does not hold (see Subsection 4.2.1) also applies here. We now provide k some cases in which one can easily decide whether e, <' e does hold. In order to do so, we k prove the following lemma. L E M M A 24 Let G = (N,E,ct) be o constrained graph and ej,e , two arcs in G. Then k every active cycle of G which contains ej also contains e if and only if the biconnected k component of G\{e ) that contains ej is neutral. k PROOF. First, every active cycle of G which contains ej also contains e if and only if ej k does not belong to any active cycle in G\{e ) or, equivalently, if ej does not belong to any k 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 c is an active cycle of G\ that contains e,- and c is some active cycle 1 2 of G \ G i (if tj € G\ then c contains ej, otherwise c does). Conversely, any active 1 2 80 Chapter 4. Ripples, Complements and Substitutes cycle c in G\ which contains tj can be completed into an elementary vector that 1 contains e,- as well. Clearly, such an elementary vector contains t does, and thus e, <j t k k if and only if c 1 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\{e } that contains tj is neutral. The possible configurations are given in Figure 4.16 k 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,- < ' e holds whenever e,- <j e does. k k Other Biconnected Figure 4.16: e,- <j t k •2» G has exactly two biconnected components which are both rims, say Gi and G - Then 2 for every e, G G\, tj,e k 6 G , any elementary vector that contains both e,- and e is 2 7 of the form given in (3.3), where c and c are respectively active cycles of Gi and 1 2 Chapter 4. Ripples, Complements and Substitutes 81 (j2- Therefore e,- <j e if and only if every active cycle of G which contains ej also k 2 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 4.3 I / ,I < |/jt| whenever fj ^ 0, which from the above is equivalent to lac ! — Icrc 2 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 = a comes 0 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.) 82 Chapter 4. Ripples, Complements and Substitutes E X A M P L E 9 In the graph given in Figure 4-17 one can see that e\ ande are complements, 2 for the elementary vectors that contain them both are f = (ci + e + e ) - l/3(e + e - e ) P = (e + e + e ) + l / 2 ( c + c 1 2 3 6 5 4 l P = ( d + e + e ) + l/4(e + e 10 + c / 12 + e) 2 5 3 7 = (ci + e + e ) + l/2(e + e 2 3 7 u + e) 9 9 / 4 2 = ( 6 7 + c) 10 8 = (e + e + e ) + l / 2 ( - e + e + e ) a f 3 e i 2 3 8 + e + e ) + l/2(e 2 3 10 9 + e u u - e ) 12 5 i i — 2x — 2xn •+• 3x5 = 2 7 Figure 4.17: S u b s 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, e ) and (ei, e ) , for instance, 7 are other pairs of complements whereas (t\, es) is a pair of substitutes. n • 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 complements (resp., substitutes), f f ai aj > 0 (resp., < 0) for all f a 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 (N,E,a) Variations in pairs of complements and substitutes. Let G = 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' whenever d and PROOF. —Xk) k > 0 (resp., < 0) (4.16) are complements (resp., substitutes). If (x\ — Xj)(x^ — = 0 the proof is complete. Xfc) 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' - x ) k k = ( £ ai conformal = ( E 2af )( °f°*) z conformal £ *./«.•)( conformal £ Zafa„) conformal where all the terms in both sums are nonzero and z > 0 for all / „ E H^k- By conformality, a 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 well . 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 e and en are neither complements nor substitutes, for the elementary vectors f = 4(ei + e + + (e + eio + en + eg) and / = (e + e i 2 — en + es) orient them respectively in the same and in opposite directions. 2 7 1 2 2 7 7 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 but er and en are neither complements nor substitutes. 3 7 0 7 (Indeed, the elementary vectors / = (ei + e 4- e ) + l/4(e + e i + en + e ) and g = (er + e 2 en, e =\ en 9 12 — 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 e be three arcs in a constrained dependent graph G = (N, E,a), and suppose th k fij e,- and ej are complements, [ii] e,- and e are complements (resp., substitutes), and [iii k e <j e, . Then ej and e are complements (resp., substitutes)*. 3 k k PROOF. Let / 6 H(a), and suppose that fjf k ^ 0. By [iii] f { [i] and [ii] / , / , • > 0 and /,•/* > 0 (resp., < 0). Therefore sign(fjf ) k sign(fifj)sign(fif ) ^ 0, and thus by = sign(f?fjf ) k = = 1 (resp., —1) (Where the real-valued sign function is naturally de- k 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 • T h e C o m p l e x i t y 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. PROOF. 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]( )) elementary operations. Now, given a constrained graph G = s 3 4 (N,E,a) In particular, [iii] holds if e, and are in the same d-equivalence class for If 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 / + = (e +i + e m ) + (l/ac )c + m + 2 + and / " = ( e m + i -f e m + 2 ) + (l/ac~)c~ where c and c~ are active cycles of G with c j = c = 1. Moreover, + k 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 , and a rough upper bound on their magnitudes 2 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 . Since an initial element of the interval (Ai, A ) can be obtained in 2 2 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 , and thus X(k) = max{ac : c cycle in G,c = 2 ± 1 } = max{|Ai|, |A |}. 2 k The time required to do so is 0(log 2 P[DN]{S)) a 2 =0(SP[ ](S)) DN (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 constrained graph G = (N, E, a) are substitutes or complements with little computation. Moreover, 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 N with TV = Ni U N and NiD N = <j> and that there exists a 2 2 2 unique pair of arcs say (e,-, ej) joining Ni and N with e; = (a,-,o;) and ej = (a,-,6j) 2 (resp., (bj, a.j)) with a,, a, 6 N\ and bj G N as is illustrated in Figure 4.18.a. In this 2 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 N • • • U N with 2 k TV* H TV = <j> for I y£ m G {1,..., k) and where there exists a unique arc e/ between m some node in Nt and another in A ^ i for all £ = 1,..., + — 1, a unique arc e between k some node in N and another in iVi, and no other arc joins any node in TV, with any k node in Nj, i ^ j = 1,..., k. This situation is illustrated on Figure 4.18.b. We can then condense the subsets Ni,... ,N k 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,..., e ) are complements if they are oriented bythis cycle in the same way, and k 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, = | / | = . . . = \ f \ and therefore 2 k the arcs t\,..., e are all in the same equivalence class for both the dependence and k the quantitative dependence relations. c) A r c s 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 iV = iV \{o} 2 1 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. A n 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 , and is oriented from n\ to n if so is the 2 2 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: T h e r i m G (left) and the constructed graph T(G')(right) L E M M A 28 Characterization of positive r i m 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 PROOF. 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 e as a forward (resp., backward) arc, the correspondence being obtained by 0 replacing the part of c which lies outside of G' by e (resp., —e ). Therefore, every positive 0 0 rim cycle verifies Ci > 0 (resp., Cj < 0) if and only if so does any active cycle which verifies = 1. Moreover, if is a negative rim cycle then — rim cycle, the above applies, and the proof follows. in T(G') is a positive • 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 i m . 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\G . Therefore X 5 That 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 e- and ej in G\ are complements (resp., substitutes) if and only if any cycle t c of G\ verifies CjCj 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' ). Moreover, if the two arcs lie in different rim components of G\, 1 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 G , are rims and that e,- € G\ whereas ej £ G . Then any 2 2 elementary vector that contains both e,- and ej is of the form / = c — (ac /ac )c 1 1 2 2 where c and c are respectively positive rim cycles of Gi and G . Therefore, e,- and 1 2 2 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. 90 Chapter 4. Ripples, Complements and Substitutes 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 2 x i + 3 x — 10^6 = 2. Then 2 /* = (ei + e 4 - e ) + 2 / 5 ( 3 f= ei +e +e ) 2 =(7/5,2/5,-1,1,0,2/5) 6 (c + e - e ) - 2/3(e + e + e ) x 4 3 2 are both elementary vectors. Now f\f\ 3 =(1,-2/3,-5/3,1,-2/3,0) 5 > 0, / / 2 2 < 0 and thus e i and e are neither substitutes nor complements although they share a node. 2 • Figure 4.20: A r c s 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 P(ct, cto,t) : 91 Min b(x,t) s.t. Ax = d ax = ao. L E M M A 29 Ascending O p t i m a l - A r c - F l o w M u l t i f u n c t i o n . In a dependent con- strained graph G =^N,E,a), ifT° is a chain whose elements differ only in one componen j G E-, and bj is subadditive , then the j 6 ih projection of X(t), irjX(t), is ascending in t on rpQ PROOF. 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 itjT and Q 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,a ,t,e): Min 6(x, t,e) 0 s.t. Ax — d ax = ao. Where b(x, t,e)= 6 H u ^ ei) x and 6,(x,-, U,e.) = 6,(x,-, i.) + e,-c"*''. R e c a l l that a f u n c t i o n / o n a lattice T is s u b a d d i t i v e i f for a n y t w o p a r a m e t e r s t a n d t', f(t f(t V t') < f(t) + f(t'), where t A t' and t V t' (4.17) A t') + are respectively the m e e t (coordmatewise m i n i m u m ) a n d j o i n (coordinatewise m a x i m u m ) o f t a n d t' — T h i s p r o p e r t y is also referred to i n 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? , written Ilim ^ f(x) n x Hm ^ Xn Vn y = g if ... lim^y, lim ^ Xl f(x) = g. yi 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 O p t i m a l Constrained Flow. In a dependent constrained graph G = (N,E,a), if t ET, bj(-,tj) is convex and lower semicontinuous for each ej G E, and 7 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 Ilim iQx{t,e) exists and is in X(t). c PROOF. 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) so is L = b(x°,t, is finite and 1). Moreover, since b(x,t,e) is nondecreasing in £, the level set 2L(t,£) = {x : Ax = d, ax = Q , b(x,t,e) < L} 0 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. above inclusion so is 2L{t,e), and thus so is X(t,e). By the Moreover, since bj(-,tj) is convex and continuous on the interval on which it is finite, &(•, t, •) is finite and continuous on the compact Recall that a real-valued convex function / on 3f is l o w e r sets {x : f(x) < a), a G 3t, are closed. 7 m semicontinuous if and only if all its level Chapter 4. Ripples, Complements and Substitutes 93 set XJt, 0) x [0, l ] , and it follows from an extension of [Be63] that for t fixed the graph of m the multifunction of e t - » X(t, e) C X_(t, 0) is compact on [0, l ] . 8 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)\ for all arcs ej and ej and 0 <C £ < e' < 1 differing only in the j since b(-,t, •) is subadditive then, by Lemma 29, Xj(t,z') (4.18) component. Moreover, t h — Xj(t,e) > 0, and (4.18) yields |x,(t,e') - xj(r, )| < ^ . ( x ^ r , ^ ) - ^ ( r ^ ) ) . (4.19) £ We now show that Ilim iox(t,e) exists and is in X(t,§) e = X(t). To this end let the vector obtained by replacing in e components 1 through i by zero. lim io x(t, e) exists and is in X(t, e^). ei be We claim that Indeed by the above remark Xi(t, e) is nondecreasing in £i, so that lim jo:ri(£,£) exists and is finite by the compactness of the graph of X(t,-). ei Now, by (4.19) and the compactness of the graph of X(t,-), \\m i x(t,£) ei 0 finite for each i > 2, so x(t,e^) = \im iox(t,e) exists and is in X(t,e^), d Cl exists and is proving our claim. By induction, given x^,^'" )) G X ( £ , e ( ' ) ) and the fact that (4.19) also holds if e 1 - 1 is replaced by e^, define x(t,e^) *= lim ,[ x(t, e^ )). By a similar argument as above one 1-1 e 0 can show that this limit exists and is in X(t,e^). x(t, 0) = x(t,gt"*)) € X(t,£< )) m Lastly, (4.19) also holds if e = 0, thus = 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 O p t i m a l 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. 8 That is, the multifunction X(t, •) of t where t is kept constant Chapter 4. Ripples, Complements and Substitutes T H E O R E M 31 graph G = (N,E,ct) 94 Monotone Optimal-Flow Selection. In a dependent constrained 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 Proper and for which Xj(t) is nondecreasing (resp., nonincreasing) in t k whenever ej and e are k complements (resp., substitutes). PROOF. 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' . By Lemma 29 we obtain that Xk(t') — x (t) > 0, and since ej and k k 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) — Ilim i x(t,e) e have the desired properties, and the proof is complete . 9 4.4.1 0 which by Lemma 30 will • T h eSmoothing Theorem The monotone optimal-flow selection theorem shows that changes in arc flows are monotone 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£ onto 3? U { + 0 0 } is given by the 2 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 Notice 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. 9 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 stepconnected if there is a finite sequence t° = t, t ,..., t 1 k = t' such that t and f r r + 1 differ at most in one component for all r and t is coordinatewise monotone in r. In Lemma 32 r 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), whose elements differ only in their j th if T° is a chain entry, Tj € 3t, 6* is subadditive and bi(-,tj) is conv for all t € T° and all i ^ j, then the multifunction t i—• tj — TjX(t) is ascending on T°. PROOF. For t € T ° , let y = tj - Xj, then bj(xj,tj) = bf{yj,tj). Therefore Bj[xj,tj] = 5 Bf[yj,tj] = bf(yj,tj) + B'j[tj - xf\ is subadditive on 3? x ITJT for bf is subadditive, and 0 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 T h e o r e m . In a dependent constrained graph, suppose that Ti C 3ft, bi(-,t) is convex and lower semicontinuous for each t € Ti, that 6,- is doubl subadditive for all ei £ E, and that X(t) is nonempty and bounded for each t 6 T. Then ther exists an iterated optimal-constrained-flow selection x(-) wjth the Ripple property and suc that ii(t) and Mjitj — 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,-, € £ , / G # ; ( « ) } ej Chapter 4. Ripples, Complements and Substitutes PROOF. 96 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 j component. From the Ripple Theorem (Theorem 21) th and Lemma 25, 0 < i,(0 - (t) < Mji(xj(t') - xj(t)) Xi => Mj j(t) - *,•(<) < MjiXj{t') - *,•(*') iX 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 (t -Xj(t)) :i + j (M Xj{t)-x {t)) ji i 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 WO - {t)\ Xi <M \xj{t')-Xj{t)\ <M\xj(t')- {t)\ 3i X] < 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, t ,..., t = t' such that t — t ' 1 k l -1 has only one non- component for each / and t is coordinatewise monotone in /, and it follows from (4.20) that l I x(0 - x(t) |U < E M O - x ^ H U < EMIIi'-t'-Ml^MHi'-Oli, *=1 97 Chapter 4. Ripples, Complements and Substitutes completing the proof. • One should observe that in the particular case where e, and ej are complements (resp., substitutes) Mij = Max 4.4.2 {fj/Mies?., - fj/f) : / € H(a), fifj * 0}. Subadditivity of M i n i m u m 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 optimalflowfor P(a, ct , t). For any subset D of E, denote 0 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 x Y T H E O R E M 34 and x' > x . z z Let C be a subset of E such that the arcs in C are all pairwise comple= {<£\c}, bj(-,tj) is convex for each ej 6 E\C', T is a ments, and assume that x £\cTj eje sublattice, be is subadditive and &(•) > -co on T, then b(-) is subadditive on T. PROOF. 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, y Y = x' — x Y and z Y = 0. We now claim that y = 0, and thus that z = x' — x . Indeed, suppose that j/j ^ 0 for some ey € Z, then one z z z z 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' = xc + yc and xc V x' = xc + zc- It now follows from our assumptions c on the arc-costs that c Chapter 4. Ripples, Complements and Substitutes Ut A t') + b(t Vt') <b(x + y,t/\ t') + b(x + z,t V t') < b{x,t) + b(x',t'). 98 • 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 M o d e l C h a p t e r 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 polynomi time for the class of graphs that arises from this formulation. Special cases where little o 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 models can be stated as (singly-constrained) network flow problems and formulate the SinglyConstrained Multi-Period Multi-Product Inventory-Production Problem as a P S C M F . In Section 5.3 we then study this model in its general form, that is, without making any assumptions 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 sensitivity 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. 102 Chapter 5. A Constrained Inventory-Production Model n Number of p e r i o d s 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 s p o s a l o f g o o d s ) , yj Amount of product / stored at the end of period j (Neg'ative values of yj signify b a c k l o g g e d 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( iiA) x h'j(y j, rj) l C o s t associated with a production level xj of product J in period i. 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 y = y' = 0 (If the situation calls for a positive inventory K' at l 0 n the end of the planning horizon, then replace d l by d + similarly, starting inventory l n n 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 n o d e 0 to a c o n s u m p t i o n n o d e , 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 s u b g r a p h s and denoted by G , • • • , G . Note that this formulation 1 P will allow for bounds on the variables xj and yj. In order to see this, define the s t e p — f u n c t i o n fx by Chapter 5. A Constrained Inventory-Production Model 0 if z < 0 +oo if z > 0. 103 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 i th 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 w y,4 \2 \ 2 , -, x,1 x,2 x,3 x , 4 y,1 "y,2 c "y,3 x e ,5 y,4 e x,1 6" X e y,1 x ; 2 x , 3 x,4 e e p y,2 e y,3 J e e x > J e 5 o" y,4 Figure 5.21: T h e basic Inventory-Production Network (p = 3 and n = 5) The find a Multi-Product Multi-Period schedule = (x,y) t = (t\,..., t*, T j , . . . , r _ ) 1 p x (x\,..., Inventory-Production x£, y\,..., y^-\) which, Problem given a is to parameter 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 min s.t 104 EE*i(*i>*i) + EEM(vi.r/) i=i t=i /=i x'i + y'-i-y^d'i P n p i = i Vi,/ (5.22) n—1 E E «W + E E J=l i=l The s i d e c o n s t r a i n t £f = 1 £?=i /=11=1 ce'^+Y^-i YZ=i P[y\ = o may express a variety of economic a or physical realities. Some examples of possible constraints with their interpretations are P n Fixed production budget E E Fixed total inventory E E P Q « '' 1 = a ° a « > 0 Vi n - l = a ° ;=i i = i p Fixed total inventory cost n - l E E P\y\ — o a /=i P\ > 0 Vi. t=i A complete analysis of the S i n g l e — P r o d u c 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 s u b s t i t u t e s 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 s u b s t i t u t e s otherwise. 105 Chapter 5. A Constrained Inventory-Production Model x\ i< j y) S C x) x\ k > j C S C S y} i < j yl k> j s c c c Table 5.1: Complements and Substitutes in the Unconstrained Single-Product M o d e l C : Complements, S: Substitutes 5.3 Substitutes and Complements in T h e 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 / = c - (ac /ac )c , 1 l 2 2 where c and c are simple active cycles that share at most either a single node or a simple path. 1 2 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, • • •, y ^ 1 and x[ (backward) and define a% k) 13? ac'(;, k) = a} - of + £ fi. i=j k 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)/a (j', k'))c (f, k') m with a'(j,fc) ^ 0, « (j',k') m m (5.23) ^ 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 substitut 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 c and c , which verify c*. = cj = 1 1 2 and (ac )(ac ) > 0. Assuming without loss of generality that i < j, then c = c(r,s) and 1 2 1 c = c(u, v) (where l < r < s < u < u < n ; the reader may verify that this is the only way 2 to obtain elementary vectors) may be chosen so that s is as small as possible and u as large as possible. If ac > 0 and etc > 0, then we denote the index of the last inventory arc of c 1 2 1 by L®(i) = s — 1 and that of the first inventory arc of c by 17®(j) = u, whereas if ac < 0 2 and ac < 0, then L (i) 2 e = s — 1 and U (j) = u (for a numerical example, see Example 11). e Similarly, let £®(i)» L (i) (resp., U®(i), e 1 U (i)) be the left-most (resp., right-most) indices e of the right (resp., left) production arcs of cycles c (resp., c ) which verifies c\. = 1 (resp., 1 2 c . = 1) and ore > 0, ac < 0 (resp., ac > 0, ac < 0 ). For j < k, notice that 2 1 1 2 2 k-i QC(J, k) where - ct(j, k) = H 7< t= c*j + # — a We show now how to determine the values L®(i), L (i), e i + 1 . U (i), U (i), L®(i), L (i), 9 e 6 U®(i)) and U (i). To that end, we also define the quantities l®(i), l (i), u®(i) and u ( t ) as follows. 6 e e Chapter 5. A Constrained Inventory-Production Model l®(i) maximizes £ 7* o v e r 1^ 108 ^ *• Jt=J©(i) « / ( i ) minimizes e £ 7fc fc=/e(.) o v e r 1 ^ ^ (0 ^ *• S m 7* > 0, i < m < n — 1}. Z®(i) = min{+oo, m : £ m L ( i ) = min{+oo, m : £ 7fc < 0> » < m < n — 1}. e u®(i) maximizes £ Ik over t < u®(i) < n — 1. Jt=.« («") u ( i ) minimizes £ 7* e e o v e r *=« • ^ {i) < 1 — 1. u& u®(i) f/®(z) = max{-oo,m : ^ 7^ > 0, 0 < m < z}. k=m f/ (z) = max{—00, m : ^ 7fc < 0, 0 < m < i}. k=m e if i > 2 and L ( i - 1) = 1 - 1 e I®(0 = < min{+oo, m : ^ ^ l " 7jt > 0, i < m <n] otherwise. i if 1 L (i) e min{+00, m : ^"Jj -y^ < 0, i < m <n) 1 i e - 1) = i -1 = < otherwise. if i < n — 1 and-{/®(i) = i max{—00, m : £ ! t = m 7/t < > 1 < m < i} otherwise, i if u U (i) i > 2 and = max{—00, m : Yl'k'Jm 7* > 0> 1 < m < i} i < n — 1 and U (i) = i e otherwise. With the convention that an empty sum is equal to zero. It is then possible to show the following. Chapter 5. A Constrained Inventory-Production Model T H E O R E M 36 109 Substitutes and Complements in a P r o d u c t Subgraph. (i) Two inventory arcs j/,-, yj (i < j) are complements if and only if L®(») > U*(j) and L (i) > U (j). e e (ii) Two production arcs z; and Xj (i < j) are substitutes unless at least one of the following holds (ii-a) Z®(t) < U (j) e orZ©(») < U®(j) (ii-b) Z ® ( t ) = U (j) = i and e 0 • i < i < j, or 0 • 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) L (i) = U®(j) = jo and e • 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 L (i) < Q U (j). e (iii-b) Z ® ( » ) = U®{j) = to and • i 7^ i, or 0 • i = i and 0 < a(t, k') < —a(l (i — 1), t) for some k' > j. e 0 (iii-c) ie(i) = U (j)=j e 0 • jo h o • and r • j = t and 0 < — a(t, k') < a(/®(t — 1), i) for some k' > j. 0 (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 < U {j) e or !©(») + 1 < U*(j). Chapter 5. A Constrained Inventory-Production Model (iv-b) L®(i) + 1 = U*{j) = i 0 • T£ j, i 0 110 and or • i — j and 0 < — a(j, k') < a(l®(j — 1), j) for some k' > j. 0 + 1 = U®(j) = j and (iv-c) 0 • Jo j, or • jo — 3 d 0 < (j, an No other pairs e may h') < —a(l (j — l),j) e be substitutes or for some complements. < i < L (i) @ ii < L (i). < e 9 yL<$(i) and yu®(i) Similarly, all cycles that contain a given production yue(i)). and 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 and k' > j. First, it follows from the above definitions that U (i) PROOF. U (i) of arcs a (resp., j/£,e(i) a forward arc and verify ac > 0 (resp., < 0) lie entirely to the left of xi®^ (resp., X£e(,)) and to the right of f?®(t) (resp., z xrj&[i)). Vi-iVj (* < j) m a In order to prove (i), recall from Lemma 35 that two inventory arcs 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 c and c that contain respectively j/,- and yj and such 1 2 that all inventory arcs of c lie strictly to the left of all inventory arcs of c . From the above 1 2 remark, such a pair will exist if and only if L (i) 9 < 17®(j) or L (i) 6 < U (j), completing the e 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 this is possible if L®(i) < U (j) e L (i) e or if L (i) f f Xi Xj > 0. For similar arguments as above, < U®(j), and impossible if L®(i) > U (j) e e > U®(j), verifying (ii-a). Suppose now that Z®(i) = U (j) Q / exists, then it will be of the form / = c — (ac /'ac?)c 1 1 2 and = io, where t < i < j. If 0 where the cycles c and c share 1 2 the arc x , , c\. — cj. = 1, ac > 0 and ac < 0. It remains to verify that 1 2 0 /..-/,, = [1 - (acVac2)^]^ - (ac'/ac )] > 0. 2 (5.24) Chapter 5. A Constrained Inventory-Production Model 111 One is lead to consider the following three cases. • If i < i < j, then c = c(i,i ), c = —c(i ,j), c.. = c . = 0, thus it follows from (5.24) 1 2 0 0 2 0 x = —(ac 1 etc ) > 0, and i , and Xj are not conformal. 1 fxtfxj 2 • If i = io < j , then c = — c(k,i) for some k < i, c = —c(i,j), (where a(k, i) < 0 and 2 l 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 c = c(i,j) and c = c(j,k') for some fc' > j (where a(i,j) > 0 and 1 2 a(j,k') < 0). Therefore c . = 0, c\. - - 1 , and 2 f , f x 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 U (j), io = J < n — 1). e A similar argument holds if L (i) = U®(j), where a is replaced by —a. e To show (iii), observe that since a production arc x- and an inventory arc yj (i < j) may t only be complements, we attempt to find an elementary vector / for which f will be possible if l®(i) < U®(j) or if L (i) < U (j), e L (i) > U (j). e e 1 i f y j < 0, which and impossible if L®(i) > U®(j) and e Suppose now that L®(i) = U®(j) = io, where i < i < j. If / exists, then 0 / = c — (ac jac )^ 1 X where c and c share the arc x, , c\. = (? . = 1, ac > 0 and ac > 0. 2 1 2 1 0 2 y It remains to verify that / . * / , , = [1 " • If i < i 0 < j , then c 2 = c(i,i ), 1 0 c 2 2 2 < 0. (5.25) = c(i ,k') where k' > j, c . = c . = 0, thus 1 0 2 = —(ac /ac ) > 0, and X{ and yj are not conformal. 1 fxtfyj • If i = i 0 2 < j, then c (where a(fc,i) fxify, (ac7ac )c X - (acVac)] 1 = — c(k,i) and c < 0 and a(i,k') 2 > 0). = [1 + cr(fc, i)/a(i,k')][a(k,i)/a(i,k')} = c(i,k') for some k < i and Jk' > j , Therefore c . = 2 1 and = 0 and has the sign of ~(a(i,k') + a(k,i)) and Chapter 5. A Constrained Inventory-Production Model < a(i,fe')< —a(fe, i) thus may be negative if 0 112 for some k < i and k' > j or, equiva- lently (from the definition of Z ® ( i ) , i = i > 2), if 0 < a(i, k') < -a(l (i - l),i) for e 0 some k' > j. A similar argument holds if L (i) — U (j). e @ The proof of (iv) follows from similar considerations. Since an inventory arc y,- and a production arc Xj (i < j) may only be substitutes, we attempt to find an elementary vector t / for which / / y i > 0, which is possible if Z®(i) + 1 < U (j) e x > L®(i) is the node L®(i) + 1) or if L ( i ) + 1 < U®(j), and impossible if L®(i) > U (j) and e L (i) > U®(j). e (recall that the head of arc e Suppose now that L (i) +1 = U (j) = io, where i + 1 < i < j. If / exists, 9 6 0 then / = c — (ac jac )c 1 1 2 where c and c share the arc x, , c . = c 2 1 2 1 0 2 j = 1, ac > 0 and 1 ac < 0. It remains to verify that 2 = (I - (acVacXK - (ac'/ac )} > 0. (5.26) 2 • If i + 1 < io < j, then c = c(k,i ) where k < i, c = — c(io,j), c\ = c\. = 0, thus 2 1 0 fxifyj — —(etc 1 ac ) > 0, and y, and Xj are not conformal. 1 • If i + 1 < i 2 = j, then c 1 0 = c(k,j) and c j , (where a(fe,j) > 0 and a(j, fe') < 0). = — 1 — Q (k->j)/ (jy a ^ nas e s ig n a 2 = c(j,k') for some Therefore ( ^ » i ) + 0)fe') a < i and fe' > = —1 and c . = 0 and 2 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 L (i) + 1 = U®(j). e consequence of Lemma 35. 5.3.2 Finally, the last statement is a direct • P a i r s of A r c s C o r r e s p o n d i n g t o T w o Different P r o d u c t s 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 a (i,j) < 0 (resp., l > 0) and a {j, k) > 0 (resp., < 0) for all 1 < i < j < k < n. l • A n 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 T w o P r o d u c t 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 L (i) 6 — +oo and U (i) Q — - c o (resp., L®(i) = +oo and U®(i) = - c o ) , whereas an inventory arc y\ is a positive (resp., negative) arc if and only if L (i) = +co and Q U (i) e = - c o (resp., L®(i) = -foo and U (i) = — oo). @ PROOF. First suppose that some arc e, is neither a positive nor a negative arc, that is, there exists two active cycles c and c that contain it as a forward arc and such that ac > 0 1 and ac 2 2 1 < 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 f 1 = c — (ac /ac)c 1 l and f 2 = c — (ac /ac)c. 2 2 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 l®{i), U®(i), L (i), e U (i), L®(i) and U®(i). e • Z (i), e U (i), e Chapter 5. A Constrained Inventory-Production Model 5.3.3 114 C o m p u t a t i o n a l Complexity- It follows from the above that in order to obtain all pairs of substitutes and complements it suffices to obtain the quantities /®(i), / ( i ) , L®(i), L (i), e u®(i), "(0> e e U*(i), U [i), Z®(i), e X ( i ) , £/®(i) and £ 7 ( i ) . These may be calculated using the following recursion equations: e e «®(0 if E U 7 > 0 i +1 otherwise *(0 if £U,*(, )7*<0 x+ 1 otherwise W e l (i + l)=< e u®(i - ! 1) = < i —1 otherwise ' u(0 if £ l ! i ° 7 f c < 0 e u (i-l) =< e i— 1 e ^®(*)i otherwise. ^(0i®(0> e Thus the quantities /®(i), / ( i ) j t u " 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., L (i) > t' + l) e then L®(» +1) = L®(i) (resp., L (i +1) e = L (i)), e and if c7®(i) < i - then U®(i — 1) = i7®(i) (resp., C / ( i — 1) = U (i)). e e 1 (resp., £7(0 < i - 1) e One may thus obtain all the pairs of arcs which are either substitutes or complements in at most 0(n p) elementary operations. 2 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\ +2x 2 + + 5 x 3+ 7 x 4+ llx l +13*2 - 9y? +vl + ivi + u 1=3 i ' = l + ny 2 5 ;=3 i = i = a. 0 Chapter 5. A Constrained Inventory-Production Model 115 a', i = l , - - - , 6 , /?', t = l , - - - , 5 , and a Where for products I = 3, 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 H l*(i) P(i) L*(i) -10 1 1 2 1 12 2 1 2 -f oo 5 2 3 3 + 00 -4 2 4 4 4 15 2 4 5 +oo 5 1 1 1 5 2 2 —oo 5 4 3 —oo 5 4 4 4 5 5 5 —oo 3 2 1. 1 2 +oo 2 —oo 4 3 3 2 6 4 4 4 5 5 5 3 L (i) Q u®(i) u {i) U®(i) 6 U (i) e L®(i) L (i) U (i) e 9 ue<i) 6 +oo 6 — CO' 5 Table 5.2: Substitutes and Complements: Computations Positive arcs: x , y , J/3, J/5 Negative arcs: x 2 2 6 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 thefirstperiod 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', •) thu defined are subadditive, and are convex in x\ if so is K(x\). Moreover, it is assumed that a 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. 116 Chapter 5. A Constrained Inventory-Production Model *[ x 1 2 1 4 X 1 s Xg 1 x vi y\ vi vi c c s c c s c c s s c c s s c s c s 4 c c vi c s y c c s c c y c s s c y s c y c c s c l x I x l 2 c s s c 3 x X 3 * 5 2 3 4 5 Table 5.3: Substitutes and Complements, / = 1 or 2 C: Complements, S: Substitutes, " ": Neither A X2 X3 \ 4 A T 1 2 X \ x X 2 x A *2 4 yl yl yl yl s c s s s c s c c c s s c c s s s" s s s s c s s s x v! v^ yl y\ yl 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 thefirstperiod. (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\ an 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' includesfixedand 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 complements) in the production level x\ of product 1 in period 1 and in the inventory level y] in period 2. 118 Chapter 5. A Constrained Inventory-Production Model (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 caus 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 120 Chapter 5. A Constrained Inventory-Production Model The interest in pseudo-rims is motivated by the following two results, which follow directly from the definition of pseudo-rims and from the types of elementary vectors in singlyconstrained 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. PROOF. 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 , one of which 2 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 / = c — (ac jac )c , 1 1 2 2 where c and 1 c are simple active cycles that share at most either a single node or a simple path, and 2 assume without loss of generality that c contains at least one arc in the pseudo-component 1 in question. Since c is active, then it may not lie entirely inside G which is neutral, and 1 thus we may write c as p — q , where p (resp., q ) is a simple path in G (resp., in G\G) 1 1 1 1 1 that joins pseudo-bolts n i to n (see Figure 5.23-b). If c contains no arcs in G, then the 2 2 A. _ projection of / on G is p , and the proof is complete. Otherwise, we may write in a similar 1 fashion c = p — q , where p (resp., q ) is a simple path»in G (resp., in G\G) that joins 2 2 2 2 2 pseudo-bolts n i to n . Clearly c and c then share at least one of p or q . In the first case, 1 2 1 1 2 p = p (see Figure 5.23-b), and the proof follows, whereas if q = q , then 1 2 1 2 Chapter 5. A Constrained Inventory-Production Model / . = c -(ac lac )c 1 l 2 121 2 = (p - q ) - (atf - q )la{p - q ))(p - q ) = ( 1 l P 1 l 2 2 2 - 9 ) - (aq'/aq^p - q ) 1 2 = (P -q )-(p -q ) 1 2 1 2 1 = 2 p -p 1 2 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 T H E O R E M 39 Sensitivity Analysis in Pseudo—Components. Let G be a pseudo- rim, G (one of) its pseudo-component(s), and T H and n the corresponding pseudo-b 2 Consider the unconstrained graph G' = G\J{e } where e = (n ,ni). Then for any g 0 0 2 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 compl (resp., substitutes) in G'. (ii) Mij = 1. Chapter 5. A Constrained Inventory-Production Model (iii) e,- <j e k 122 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 developed 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 k > 2 such that a' = 0 for all i < ko and ft' = 0 for all i < feo—1 0 (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' < n — 1 such that a[ = ft' — 0 for all i > k' (or, more Q 0 generally, if 7^ = 0 for allfe> fe ). The two (right) pseudo-components then correspond 0 to the arc sets {x',t/',i > k' } and {*/[<_!} (see Figure 5.24). 0 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. 123 Chapter 5. A Constrained Inventory-Production Model 0 Figure 5.24: A p s e u d o - r i m w i t h f o u r p s e u d o — c o m p o n e n t s : T h e I p r o d u c t s u b g r a p h (fc = 1, K - 4) th 0 E X A M P L E 12 First Quarter Budget. Consider a model with p products and six periods, and suppose that there is afixediniti operating budget (production and inventory) on the cost of operation in the first three period The following side constraint will reflect this fact. E E ^ +t E ^ j=it=i ;=ii=i = «o (5.28) 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 giv 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 i Section 5.3.). Moreover, for all pairs of arcs e, e' for which Table the Ripple coefficient Now, M i ee 5.5 provides information, is equal to 1. 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 124 Chapter 5. A Constrained Inventory-Production Model 1 *^ 2 xi xi X C s s s c s s c c s s c yl vi yl s s c s s s c s s c c s s s s c c c c c c c c c 1 y'l yi xi A xi x' x 6 y'x y\> yl vi yl 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 substitutes) 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 substitutes) of at most S units (Ripple property^ in the inventory levels y\ and y\ of product 1 in the fourth andfifthperiods. 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 125 Chapter 5. A Constrained Inventory-Production Model 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?,!, + a ,! + Q5X5 + 2 2 2 Q|X| = a 0 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 thefirstproduct 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 increase 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 andfifthperiods. (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 andfifthperiods and no further predictions may be made without supplementary data. • 126 Chapter 5. A Constrained Inventory-Production Model First P r o d u c t x \ x\ x\ yl y\ y\ y\ yl i x 1 2 x x\ \ l *S c s s s s c s s s s c s s s s c s s s s c s s s c c s s c c c s vl vl vl s c c c s s c c s s s c s s s s c c c c c c c c c c c c c c c c yl l Xg yl yl c s s c s c s s x X y\ yl i Second P r o d u c t \ x c s y? c yl c i s c s s yl yl \ \ c s c c c c c c x x x 3 \ yl x T x 2 5 T 6 2 x yl yl s s c c c s c c Third Product i x 2 x 3 T 4 3 x r A X2 c s s s s c s s c c c c s c c c x\ A x\ s s c s s s s c s s c c s s s c Ig vi yl yf yl yl c c s s c c c s c c c c c c c c c c c c c c c c c c c c c s s s 3 y? y? y y? yf 3 3 Table 5.6: Substitutes and Complements (No further information available without numerical information on the side constraint coefficients) 127 Chapter 5. A Constrained Inventory-Production Model 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. First Period Constraints 5.5 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 manufacturing 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 = Q o 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 i i = ct where a[ > 0 is the $-value of item / produced (in period 1) and a a x 0 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 i [ a x + £ ? = i PWi = o where a[ > 0 is the Q unit operating cost of producing item I in period 1, /?( > 0 is the unit inventory operating cost for item / in period 1, and a is the startup budget. 0 Chapter 5. A Constrained Inventory-Production Model 5.5.1 128 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, G is a neutral subgraph l 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 dependent 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 . It is easy to verify that 1 the r i m components of G correspond to the arc-sets {x[}, {y[}, {x , • • • , z „ , y [ , • • • ,y -i} l l 2 n and its bolts are the nodes 0,1 and 2 (see Figure 5.25). 0 Figure 5.25: T h e subgraph G is a r i m with three r i m components l 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. 1 129 Chapter 5. A Constrained Inventory-Production Model 5.5.2 Positive A r c s , Complements a n d 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 G contains both x[ and y[ as forward arcs and verifies ac = a\+P\ > 0. l 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 (5.30 / = c[l] - (a[ + /3<)/(aT + PTWrn] where c[l] (resp., c[m]) is a simple cycle of G (resp., G ) that contains x[ (resp., Xj") as a l m 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 R i m s . • 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 that rim. Moreover, the corresponding Ripple coefficient is given by M > = 1. ee • 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 M e e i = Tit i i Mil, v m) ; = \: — a + P\ a? + # V Chapter 5. A Constrained Inventory-Production Model 130 Where e (resp., e') belongs to G (resp., G ). l • m 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. y) x\ x) i <j S[l] C[l] C[l] C[l] x? j>2 X yf x\ k> j S[l] S[l] yl i <j S[l] C[l] 1 S[M(1,/)] C[M(1,/)] S[M(1,/)] vl k> j C[l] C[l] y? 1 i >2 C[M(1,/)] S[M(1,/)] C[M(1,/)] 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 : Substitutes, Complements and R i p p l e Coefficients C : Complements, S: Substitutes, [Ripple Coefficients] 5.5.3 Less-dependent-on Relations 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 e then the optimal flow variation in arc k 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 e does not increase the less dependent qualitatively on ej this arc is. For that k 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 e correspond to three different products, then clearly deleting k ek leaves ej and ej in the same dependent component, thus e- < j e does not hold, and t k therefore neither does e,- <' e . k (b) Let us assume that ej, ej and e lie in two different product subgraphs and consider the k following cases. (b-1) ej and ej belong to the same product subgraph, say G , and e belongs to 1 k another, say G . In order for the deletion of e to cause ej and ej to end up in 2 k different dependent components, it is necessary and sufficient that (i) G \e 2 k is not an active subgraph, that is, e = x\ or yf, (ii) there are only two active product k subgraphs, G and G , and (iii) ej and ej lie in different rim components of G 1 2 (that is, at least one of ej and ej belongs to 1 {xi,2/i}). If the above holds, then it follows from (5.30) that ej <' e if and only if k l«i + # l > l « ? + tf|. _ (5-31) (b-2) ej and e belong to the same product graph, say G , and ej belongs to another, x k say G . In order for the deletion of e to cause ej and tj to end up in differ2 k ent dependent components, it is necessary and sufficient that G \t x k is a neutral subgraph, that is, t = x\ or y\. k In that event it follows from (5.30) that any elementary vector / that contains tj verifies |/j| = |/*|, and thus ej <' t also holds. k (b-3) tj and e belong to the same product graph, say G , and Cj belongs to another, 1 k say G . Since ej and ej play symmetric roles in ej <j e , (b-2) also applies here. 2 k Chapter 5. A Constrained Inventory-Production Model If e,- < j e holds, then (as for (b-1)), e,- <* t d k k 132 if and only if (5.31) holds. (c) Lastly we consider the case where the three arcs are in the same product subgraph, say G. 1 From (5.30), the projection of any elementary vector on G either is empty or is 1 a simple cycle, and thus e,- <j e and e,- <? ek holds if and only if deleting tk leaves k e{ and ej in two different biconnected components of G \ejt. One of the following is 1 necessary. (c-1) tk is any inventory arc, and e- and tj lie on either side of e . t k (c-2) tk = x\ and either e,- or tj is y\ or, by symmetry, t k = x\ and either e,- or ej is Vl-iThe 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. 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. 2 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 productioninventory 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) A n 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) A n increase (Monotone Optimal-Flow Selection Theofem) of 8' where 8 < M(l,l)8 l = (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) A n increase (Monotone Optimal-Flow Selection Theorem) of at most 8 units (D-Ripple l 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). 134 Chapter 5. A Constrained Inventory-Production Model (vi) A decrease (Monotone Optimal-Flow Selection Theorem) of at most S units (D-Ripple l 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\ 135 Chapter 5. A Constrained Inventory-Production Model where the function K' includes upper and lower bounds as well as afixedcost. The function h\(y\,H) thus defined is subadditive, and h\(-,H) is convex if so is K'. Thus an i n c r e a s e i n t h e 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 6 (0 < 6 < 6) be the magnitude of that decrease in thefirstperiod production. 1 1 (iv) An Increase (Monotone Optimal-Flow Selection) of S < Af(l,/)o" = (a] + f3})l(ct\ + l x /?,')o" units (D-Ripple property) in the production level x[ and of the inventory level y{ x of product / = 2, • • • ,p in thefirstperiod. (v) An increase (Monotone Optimal-Flow Selection) of at most 6 units (D-Ripple property) l 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 8 units (D-Ripple property) l in the production of product / = 2, • • • ,p in periods 2, • • •, n. The corresponding Hasse Diagrams given in Figure 5.27 for both partial orders < <Ji (with the same assumption that / = 3, M(l,2) < 1 and Af(l,3) > 1). • • • d 1 and Chapter 5. A Constrained Inventory-Production Model 136 Chapter 6 A C a s h - F l o w Asset Allocation Management M o d e l C h a p t e r 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 changes in the environment such as variations in interest rates, taxes or asset prices with any additional computation. • 6.1 • • A Cash—flow Management M o d e 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 singlyconstrained 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 b 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 x Amount invested in riskless asset in the revised set of assets y 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 . Q r 3 Moreover, we associate a convex parametric penalty or carrying cost b(-, •) with the quantities Si, pi, Zi, y , i £ I, and x . The nonnegativity constraints on the variables will be embedded T t 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 x invested in the riskless T asset by tf(x ,t ) where V is a parameter associated with this investment. The expression r T 52»ei °" 2/, represents the risk factor . 2 2 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 formulation 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 y Qy 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€/ ?I'« - ^ 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. i cr 2 e Chapter 6. A Cash-Flow Asset Allocation Management Model (GEN) min - y , + \Z * y? +E 2 ieI * / + 139 E. /4?(*,*f) € + E.-€/4?(ft.«T) + E * / - ^ <f ) + -?(*', * ) r 6j — 5» —z = 0 t Wi £ I L,iPi + z, - y, = 0 Vi E J E . e K + POW + (1 + Po)* - y, = 0 1 &o + r - E i e / P . - x = 0. r 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. (SCF) 140 A Cash-Flow Asset Allocation Management Model min E , 6 / t h t i ) s.t. qi + Z{ + E*/*?(?.*?) + E.e/bi(Vi,*?) + yi = 0 — Wi € I + E.-6/(1/«.M)* + Zieih2*i where the costs b*{ziMt\) = 6?(yt»'*.Pf»o"i) b (x t ) T r r t lPo x r = bo + E,/ E *,,2&. VHzi^+Mibi-Zi^) = 4?(*/«.M,«?) = _(i+ = -(l-r-p )x -r-6 (x ,< ) p)y, +fcr(y.-,<r)+ A c T y 2 2 t r r r r 0 are also convex. This is a networkflowproblem on the directed graph given in Figure 6.29 with a side constraint of the form ax = ao where a? = t , ia a i = l/t i, q it a\ = 0 Vi € I, a = 1 and a = b + Y^bir 0 0 fe/ Chapter 6. A Cash-Flow Asset Allocation Management Model 6.2 Properties of the Graph 141 GSCF 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/ac )c 2 (6.32) 2 where c\ and c are two active cycles that either intersect at a single node, on a simple path 2 or do not intersect. Given the simple topology of the graph GSCF, we know that the possible values for c\ and c are ef + e , t\ + e?, ef — e\ for all i 6 /, and e . We will identify the y 2 r 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\ - U t t] + (1 - r *,-, )e? tl i<2 u 2 or, if they involve two leaves of GSCF, say corresponding to i,j € /, they will be of the form 142 Chapter 6. A Cash-Flow Asset Allocation Management Model /(*, Vi, Vi) = {< + «?) " + ej) = ef + eV - (r,)2/*i>2)e* - (^/« )«J /(*, «,",%) = « + ^) - (o?/aS)(eJ + ej) = e? + eV - (U, t^)e) 2 /(*,y« 9.) /(*,y.-,©,yi) /(ft, y., W (U t^)e) a = («? + <*) - (o?/(aJ - aj)(ej - ej) = ft) = = (e? + er) - K/aj)(ej + D = . + ? " (W'.MM " («? + er) - aJ/(o$ - ar«)(e< - E c? + er + t /(t (l jxl E ? E ej) - t t^))e) - t /(t (l itl ja :tl - itl t t^))t) ]a /(*,?,•,*;,?,•) = ( e f - e ? ) - ( a f - a H / ( c ^ - a ] ) ( e ^ - e ] ) = e\ - t\ - t (l /(*,-, y,-,x ) = (ef-fer)-(a,Var)er = ef-rer-<,-,2er ffayux*) = (? r - t t )/{t (l jtl e + iA it2 f)-(a?/ar")e' = e - t t ))e) itl e J+ hl + ^ ( 1 - <,M*, )/(*.M(1 ~ Wit) : jt2 I2 e?-(l/«.-.iK « z,-, x') = (e* - e?) - ((a? - a?)/or> = < - e? + (1 - U^/t^ r as well as any combination obtained by reversing i and j . We m a y assume for practical purposes that 0 < 2 2 < 1, 0 < U < 1 and thus 0 < 1 — *,,it\, < 1 for all i G P. t2 In practice, the transaction costs are of the order of 1%. Thus U i and f,- are close to .99. t j2 143 Chapter 6. A Cash-Flow Asset Allocation Management Model We may now determine whether a given pair of arcs in GSCF are substitutes, complements, or neither, by simply looking at the signs of the entries of the elementary vectors. For example, we may deduce that e\ and that contain them both are /(-?,-, verify f'ff are complements, for the only elementary vectors y,), /(z,-, y„ z yj), /(*,-, y,-, qj, yj), f(z , y„ ZJ, qj) which all { it > 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: i, qi, Vi Zi,Vi,Zj,yj *i,yi,qj,yj qi,yi,zj,yj Zi,yi,zj,qj >,qi, i,qj qi,yi,qj,Vj qi,yi,zj,qj i,qi,qj,yj i,qi,zj,qj Zi,yi,x qi, yi, x i,quz j,yj,x qj,yj,* Zj,qj,x z z z z z r r z z T e*i + + e + + + + + + + + + + + + + + + + + + + - r T r i -. - + + - + - + + + - + - + + + + + + + Table 6.8: Table Signs of Respective Elementary Vector Entries Zi qi yi Zi qi yi Table 6.9: C s C s C C C Zj qj yj X T s s .s s s s 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. < r, (1 < 2 U,\U,2) for t)2 all i G / which, for most real situations, is indeed the case. (2 Chapter 6. A Cash-Flow Asset Allocation Management Model x\x' e? e, 1 el I ? el 1 1 1 e? e l-t..l*..2 ti.l l-U.lU.2 r <U<..2 l-*.M*.-.a *i.2*i.l l-t,.l*,.2 ti.a.i.i l-t,.l*,.2 *i.i(i-*y.i*>,2) «.,i(l-*>,i*>.a) • i.i *i.i(l-*i.i*i'.a) *..i*>,a l-t|.ltf.2 *i.a *..i(l-*t.i«t.a) 1 r t,.a 1 1 1 1 •i.i«..a t.M 1 *,-.{ *i.2 l-*i.l*.-.8 e e? «5 1 1 1 144 1 Table 6.10: Coefficients of the Ripple T h e o r e m 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 *,-, , for t 2 ifl - t i>2 = .99 Wi e I and for t itl • Changes in Sales Taxes. = t i<2 = .90 Vi G / . 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 S C F formulation). In order to investigate the qualitative effect of changes in the tax rate r,- on our cashflow allocation revision, we express the cost associated with z,- as &?(*,•, ) = Ti(bi - Zi) + #(*,•) + b>(bi - Zi). Ti where 6f(z,) and ££(&,• — z,) denote the (non-parametric) costs of selling an amount Si and keeping an amount z- of asset i excluding the tax. The function if (•, •) thus t 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) A n 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*, (resp., $1,016 if i, i = i*, = .99 Vi G / , and $1,116 if il t i2 U,i — ti,2 = -90 Vi € /) in the amount of asset i bought (p,- = o,/£,,i). (iii) A n 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 Ut tj,i/(ti,i(l ii2 - *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£, /t'j )2 revised set of assets (yj)- i2 (resp., $6, $6) in the amount of asset j ^ i in the . (vii) A variation of at most $6r; (resp., $.996, $.906) in the amount invested in riskless i2 asset (x ). r • 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. Suppose 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,) + Aofy . Thus 2 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) A n 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 /(l — U,iL, ) (resp., $49,756", $4,746) in the amount i2 2 purchased of asset i (p,). (iv) A variation of at most $6f i/(£, i(l—t,,!*,^)) (resp., $50,256, $5,266) in the amount J) 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_ i/(t (l — *j,i^i,2)) (resp., $50,256, $5,266) in the amount 7i 1(1 of asset j j£ i purchased (pj)(vi) A decrease of at most $8/ti,itj 2 (resp., $1,026, $1,236) in the amount of asset j ^ i t 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 (x ). r R e m a r k . 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 74 Al[M] 78 C(a) (constrained circulation space) A/[QLD] E, set of arcs 10 E, set of arcs 1 F(a,cto,d), set of constrained flows H(a), set of elementary vectors H {a) 11 10 20 63 } N, set of nodes 1 N, set of nodes 10 P(<x,a ) Q 22 2 0 s, size of an instance tj, arc parameter 13 60 Tj, parameter lattice X(t), set of optimal active 60 flows 11 additional constraint 1, 10 adjusted version 48 ALGORITHM I 41 A L G O R I T H M II ancestors 60 51 12 147 Appendix A. index arc redirecting 41 arcs with common degree-two nodes 86 ascending optimal-arc-flow multifunction backlogged demand backward 102 11 basic variables 16 basis for the tucker representation biconnected component biconnected bolts 91 16 21 12, £1 25 branches of G 31 changes in sales taxes circulation space circulation 144 15 10 complements 81 conditional transitivity of complements and substitutes connected 12 constrained circulation constrained graph 11 10 constrained palm graph 12 constrained circulation space constrained problem consumption node contain 102 11 cost 10, 1 cost 60 cut 11 60 12 cycle graph 25 d-equally dependent on d-equivalence classes 63 D-ripple property 70 decision problem demand vector 63 13 1, 10 dependent component 21 dependent component-additive dependent descendant 21 12 detection of VQ and WQ detection of the bolts directed graph 4% 1, 10 directed spanning tree disconnected version of G disposal of goods 4% 102 12 4$ 56 Appendix A. index 94 doubly subadditive dual 94 11 11 elementary vector elementary support 11 elementary circulation 13 35 evaluation problem expanded one-rim expansion arc father 13 feasible flow 35 10 " 1, 10 forward 11 fundamental basis associated with B hasse diagram head 19 132 1, 10 incidence matrix 1, 10 independent rates of return instances 138 13 iterated limit 92 iterated optimal-constrained-flow selection iterated optimal constrained join flow 92 91 lattice 60, 103 leaf branch 40 leaf arcs 16 less-dependent-on 61 lower semicontinuous 92 manpower requirement market demand 127 102 maximum weight oriented simple cycle meet 91 monotone optimal-flow selection monotonically step-connected 94 95 monotropic programming problem multiple constraints negative arcs 57 87 11 node labelling nonbasic variables 41 16 nonlinear and inequality constraints one-rims 1 11, 113 negative r i m arcs neutral 74 56 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 parameter 60 60 parametric singly-constrained monotropic network flow problem (pscmf) parametric unconstrained monotropic network flow problem periods 102 • positive arcs 11, 113 positive r i m arcs problem 87 13 product subgraphs 102 production node products 102 102 \ pseudo-component pseudo-bolts 118 118 pseudo-rim 118 q-equally dependent on q-equivalence classes Q-ripple property 68 68 70 qualitative determinacy 4 quantitatively less dependent on R-cycle 61, 68 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 reversed 25 25 risk factor root 41 11 r i m components rim 60 138 • 12 rooted tree S-cycle S-arc schedule 132 31 31 103 series arcs 86 shared machine side constraint 125 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 step-function subadditive 91 submodularity substitutes 11 support 11 1 tail 10 tree arcs 91 81 supp(x) tail 57 1Q2 12 Tucker representation unconstrained problem 16 15, 60 unconstrained monotropic network flow problem underlying tree 12 variations in expected rate of return weights 2, 15 145 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. Translatio 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 Programs. Math of Operations Research 5, 312-357, 1980. [Cu83] W . H . Cunningham. A Class of Linear Programs Convertible to Network Programs. 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 Inventories. Doctoral Dissertation, Department of Operation Research, Stanford University, 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 Commerce 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 Convex 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 NPCompleteness. 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 SinglyConstrained 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 Rectangular 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, 2 [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 University, 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, 395408, 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 Mathematical 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. Working paper, Curriculum in Operations Research and Systems Analysis, University of Carolina at Chapel Hill, December 1986. nd edition, Oxford Press, Garendon 1939. 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 Equilibrium, 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, 104127, 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). VIII Internat. Math. Prog», Abstracts. Stanford University, 1973. th [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. 156 Bibliography [Ve64] A . F . Veinott. Production Planning with Convex Costs: a Parametric Study. Management 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. Presentation to the TIMS/ORSA meeting, San Francisco, CA, 1968. [Ve84] A . F . Veinott. Lecture Notes in Inventory Theory. Department of Operation Research, 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 |
Aggregated Source Repository | 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:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0100489/manifest