O R D E R E D O P T I M A L SOLUTIONS A N D A P P L I C A T I O N S By Li Liu B. Sc. (Computer Science) Peking University M . A . (Economics) Peking University A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF T H E REQUIREMENTS FOR T H E DEGREE OF D O C T O R OF PHILOSOPHY in T H E FACULTY OF GRADUATE STUDIES MANAGEMENT SCIENCE We accept this thesis as conforming to the required standard T H E UNIVERSITY OF BRITISH COLUMBIA August 1, 1996 © Li Liu, 1996 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. Management Science The University of British Columbia 2075 Wesbrook Place Vancouver, Canada V6T 1Z1 Date: Abstract The Monotone Response and Selection (MRS) Theorems in lattice programming provide a sufficient condition under which the optimal solutions of a parametric optimization problem are monotone in the parameter. The MRS Theorems have many applications. In particular, they explain the monotonicity of minimum cuts in parametric maximum flow problems in certain networks. However, in some parametric optimization problems, monotonicity does not hold. Rather, a totally ordered selection of optimal solutions exists. In Chapter 2, I present some conditions under which there exists a selection of optimal solutions that are totally ordered, but not necessarily monotone. Based on this result, I present necessary and sufficient conditions for some natural classes of parametric maximum flow problems to ensure the existence of a totally ordered selection of minimum cuts. In Chapter 3, I extend the original selection problem studied by Rhys (1970) and Balinski (1970). I introduce the notion of tasks and assume that, facilities are capable of performing multi-tasks. A job then, instead of requiring a fixed set of facilities, requires a set of tasks, which can be performed by different facilities. The objective is to maximize the net return. Although this extended model is NP-hard, by introducing some natural restrictions in the extended selection problem, I obtain two variants thereof, which can be solved as minimum cut problems. A forest-harvest and road-construction scheduling problem can be formulated as one of the two variants and solved as a minimum cut problem. Recently, new legislations have been introduced which require that a logging company cannot harvest a block of forest if an adjacent block has been harvested within the past n 20 years. In order to harvest a block of forest, a road must be ready leading from a saw mill to the block. Roads must be constructed from a tree structured network of potential links. Due to the long planning horizon, forest-harvesting and road-construction must be scheduled together in order to maximize the present value of net income. In Chapter 4, I present a tabu search heuristic to generate schedules which compare favorably with previous studies. in Table of Contents Abs t rac t i i L i s t of Tables v i L i s t of Figures v i i Acknowledgement ix 1 Introduction and Prel iminar ies 1 1.1 Introduction 2 1.1.1 Monotonicity of Optimal Solutions 2 1.1.2 Facility Selection Problems 3 1.1.3 Forest Harvest and Road Scheduling Problem 5 1.1.4 Contributions of the Thesis 7 1.1.5 Organization of the Thesis 10 1.2 Preliminaries 11 1.2.1 Lattice Programming 11 1.2.2 Parametric Maximum Flow Problems 12 2 Tota l ly Ordered O p t i m a l Solutions and Parametr ic M a x i m u m Flows 15 2.1 Totally Ordered Selections 15 2.1.1 The Monotone Response and Selection Theorems 16 2.1.2 Totally Ordered Response and Selection Theorems 18 2.2 Ordered Minimum Cuts in Parametric Maximum Flow Problems 27 iv 2.2.1 Monotone minimum cuts 27 2.2.2 Parallel Arcs in Maximum Flow Problems 29 2.2.3 Totally Ordered Selections of Minimum Cuts 32 2.3 Ordering of Minimum Cuts in Some Parametric Flow Problems 52 3 A n Extended Selection P r o b l e m 61 3.1 The Extended Selection Model 61 3.2 Some Variants of the ES Model 64 3.2.1 The ES Model with Nested Facilities 65 3.2.2 A n ES Model with Nested Facilities and Jobs 71 3.3 Applications of the N F J model 80 3.3.1 A Network Scheduling Problem 80 3.3.2 A Forest Harvest Scheduling Problem 85 3.3.3 An Open Pit Mining Scheduling Problem 86 3.4 Some Qualitative Properties 90 4 Forest Harvest and R o a d Construct ion Scheduling 105 4.1 The Model 105 4.2 The Tabu Search Heuristic 109 4.3 Scheduling Problems in the Tangier Watershed 112 B ib l iography 121 Appendices 126 A Pseudo-Code for the Tabu Heur is t i c 126 v List of Tables 3.1 Jobs in Example 3.1 66 3.2 Facilities in Example 3.1 67 3.3 Jobs in Example 3.2 73 3.4 Facilities and tasks performed by them 82 3.5 Jobs and tasks required 83 3.6 Summary of monotone results 103 4.7 Total volumes at the ends of the planning horizons 113 4.8 Solutions for 219 blocks with 6 periods . . . 115 4.9 Solutions for 219 blocks with 12 periods 116 4.10 Solutions for 491 blocks with 6 periods 117 4.11 Solutions for 491 blocks with 12 periods 118 4.12 Optimal net income for the relaxed problems 118 v i List of Figures 2.1 The sets of minimum cuts are not totally ordered 19 2.2 A n infinite lattice £ 23 2.3 A n example for which a sub-selection cannot be extended 26 2.4 Parallel arcs 29 2.5 Front and back arcs 31 2.6 G' for Case 1 35 2.7 G' for Case 1 36 2.8 G' for Case 2 37 2.9 G' for Case 3 37 2.10 Partition of the node set 40 2.11 A n example where totally ordered selections of minimum cuts does not exist 53 2.12 Two rays in opposite directions 58 3.13 The facility tree for Example 3.1 68 3.14 Network G for Example 3.1 69 3.15 Tree of jobs in Example 3.2 74 3.16 Network G for Example 3.2 75 3.17 Possible links from the suppliers to the consumers 81 3.18 The original network 84 3.19 The modified network 84 3.20 Predecessors in open pit mining 88 3.21 A n example of ore body 88 vii 3.22 Dagdelen's network G 3.23 A sparser network G' A c k n o w l e d g e m e n t I cannot become what I am today without the selfless help and devotion from many people, including my parents, grand-parents, and my teachers. It is impossible to enumerate all these people, yet I am deeply grateful to them. Special thanks should go to my supervisors, Professor Shelby Brumelle and Professor Daniel Granot, for their mentorship and inspiration, for bringing my attention to the problems addressed in the thesis and for their comments and discussions which were cru-cial in every step in my Ph.D. programme. Further, it was from the numerous corrections that they patiently made on the drafts of my thesis that I learned the basics of academic writing. I would like to thank my dear wife Haihua Zheng. Without her support and tolerance, my programme could not have been successfully completed. I have received valuable comments from other members in my supervisory committee, Professor Frieda Granot and Professor Nicholas Pippenger, and from members of the examination committee, Professor Richard Anstee, Professor Eric Denardo, Professor Joel Friedman and Professor Maurice Queyranne. I am grateful to my friends and fellow graduate students for keeping me feel alive. The sports, hiking trips, even discussions in the corridors made my life more enjoyable and memorable. I dedicate my thesis to my grand-parents and parents. I X Chapter 1 Introduction and Preliminaries In this thesis, I will discuss three related topics. First, I will present a qualitative study of optimal solutions and apply the qualitative results to the study of parametric maximum flow problems. Therein, I intend to answer questions such as (1) when are the optimal solutions totally ordered? and (2) on what kind of parametric problems can a well known parametric maximum flow algorithm (the G G T algorithm) possibly apply? Then I will present a natural extension of a well studied facility selection model, which accommodates the fact that modern facilities are often multi-functional. Although this extended model is generally NP-hard to solve, I will show that under some additional assumptions, it can be solved as a minimum cut problem. As a special case of the extended selection model, a forest harvesting and road construction scheduling problem can be solved as a minimum cut problem, when some constraints that occur in real world operations are relaxed. The unrelaxed forest harvesting and road construction scheduling problem is NP-hard and can only be solved to near optimality with known technology. I will present a tabu search heuristic to solve this unrelaxed problem and present some experimental results on real harvest scheduling problems for the Tangier watershed in British Columbia. To facilitate presentation, in this chapter I present a brief introduction to the three topics that are addressed in the rest of the thesis. 1 Chapter 1. Introduction and Preliminaries 2 1.1 I n t r o d u c t i o n 1.1.1 M o n o t o n i c i t y of O p t i m a l S o l u t i o n s Qualitative analysis provides, without data collection or computation, the direction of change of optimal solutions when the problem parameters are changed. As such, it provides the decision makers with valuable insight into the underlying problem. In some cases, qualitative analysis facilitates the solution of an optimization problem. For ex-ample, such an analysis may limit the solution space to a manageable size. Sometimes it is impossible to solve an optimization problem and qualitative analysis may be the only feasible approach to gain some insight to the problem. Lattice programming, developed by Topkis and Veinott 1, is devoted to sensitivity analysis of optimization problems. Fundamental results in lattice programming are the Monotone Response Theorem and the Monotone Selection Theorem. They are concerned with the optimization of a parametric function, for which partial orders are defined on the domain of the function and on the space of the parameters. The first theorem asserts that under certain conditions, the sets of optimal solutions will form a series of ascending sub-lattices when the parameter increases. The second theorem provides sufficient conditions under which it is possible to select an optimal solution for each instance of the parameter so that the selected solutions are monotone in the parameter. Milgrom and Shannon (1994) presented a necessary and sufficient condition for the optimal sets to be ascending sublattices when the optimization problem is parameterized on both a parameter and the feasible set. xSee Topkis (1978) and Veinott (forthcoming). For earlier work, see Topkis (1968), Topkis and Veinott (1973) and Veinott (1974). Chapter 1. Introduction and Preliminaries 3 The Monotone Response and Selection Theorems have many applications. For ex-ample, they were used by Denardo, Huberman and Rothblum (1982) to show that op-timal partitions of a base interval into k sub-intervals are interleaved when k changes; they were used by Granot and Veinott (1985) to justify some monotonicity results in a parametric study of network flow problems; they were used by Lovejoy (1987) to obtain monotone results in a study of the partially observed Markov decision processes; and they were used by Milgrom and Roberts (1990) to characterize some trends in modern manufacturing. Brumelle and Granot (1993) used the Monotone Response Theorem in their parametric study of the repair kit problem2, to show, among other results, that the search for an optimal kit can be reduced to n + 1 monotone subsets of tools instead of 2n subsets, where n is the total number of tools. Topkis (1995) used the Monotone Response Theorem to provide monotone comparative statics results in a model of the firm and to unify and extend previous research that appeared in the literature. 1.1.2 F a c i l i t y S e l e c t i o n P r o b l e m s The original selection model, introduced by Rhys (1970), is concerned with the selection of a set of facilities in order to perform a subset of potential jobs. Therein, a decision maker is given a set of potential jobs J and a set of facilities T. He must choose a subset of jobs J C J to perform and a subset of facilities F C T to acquire. Each job j requires a specific set F(j) of facilities, and the job can be performed if all the required facilities in F(j) have been acquired. A facility does not perish after being used to complete a job and can be reused for another job, therefore, a set J of jobs can be performed if UjejF(j) C F. A cost c(/) is incurred for each facility / acquired, and a revenue r(j) is earned for each job j performed. Thus the profit from selecting facilities in F and performing jobs in J is J2jeJr(J) ~ 52feFc(f)- The decision maker's 2See also Smith, Chambers and Shlifer (1980) and Mamer and Smith (1982). Chapter 1. Introduction and Preliminaries 4 objective is to maximize the total profit. Clearly, a trade off exists between acquiring more facilities and incuring higher facility cost, and foregoing some jobs and loosing some revenues. Rhys (1970) showed that the above optimization problem can be formulated as a linear programming problem. Balinski (1970) further showed that it can be solved as a minimum cut problem in a capacitated network. Several applications of the original selection problem have been studied. For example, Eisner and Severance (1976) showed that the selection problem can be used to find an optimal partition of data blocks between a fast storage and a slow storage. Therein, the cost for storing a block of data in the fast memory is higher than that in the slow memory. However, if a job ever needs to access a block of data stored in the slow memory, then a penalty cost is incurred. The objective is to minimize the sum of the data storage cost and the penalty cost. Smith, Chambers and Shlifer (1980) and Mamer and Smith (1982) studied a single period multi-item inventory control problem known as the repair kit problem. Therein, a repair crew must select a kit of tools that they carry to geographically separate locations for equipment repairs. If a repair job needs a tool that they do not carry, then a penalty cost is incurred, possibly from the delays in fulfilling the job. The repair crew must properly select the kit so as to minimize the sum of the holding cost of the tools and the penalty cost. Mamer and Smith (1982) showed that this optimization problem can be solved by the original selection model. In many real world problems, additional constraints must be considered. For example, there may be a budget constraint so that the total cost of the facilities acquired cannot exceed a certain limit, or there may be a limit on the number of facilities acquired, possibly due to the limited number of slots available to store the facilities. The selection problem with these additional constraints are referred to as capacitated selection problems (CSP), which are usually NP-hard to solve. Crama (1995) provided a comprehensive survey of Chapter 1. Introduction and Preliminaries 5 the literature on CSP and its variants. See also de Matta, Hsu and Lowe (1995). 1.1;3 Forest Harvest and R o a d Scheduling P r o b l e m A distinct change in public attitudes toward the environment has led to demands for a forest management paradigm shift from one of a dominant timber use to one in which forests are managed for multiple values. Among the most significant implications of such a shift in policy on forest management was the introduction of adjacency or green-up constraints. These constraints attempt to eliminate large clear cut areas. For example, legislation in British Columbia requires that the trees in a block must reach a mean height of three meters before any adjacent blocks can be harvested. While environmental issues are more and more recognized by forest resource managers, any policy would not be sustainable if it does not allow logging companies to remain profitable and to continuously provide employment for the community. Thus harvest schedules must be made that do not violate adjacency constraints and at the same time, yield reasonably high income. In order to harvest a block, a road to a saw mill must be ready by the time the block is harvested. Since a planning horizon is at least 40 years and can be as long as 120 years, if a road is built later, then the present value of the cost is much less than if it is built earlier. Besides, a road will degenerate if it is built and left unused for a long period of time. Thus the construction of roads must be scheduled simultaneously with harvesting. Although a lot of work has been done to optimize harvest schedules with adjacency constraints, road scheduling has largely been ignored. Early work incorporating adjacency constraints but not road scheduling includes a mixed integer programming approach by Kirby et al. (1980). Several alternative approaches have been tried to deal with the size of the problem, including random search, Langragian relaxation, simulated annealing, and other heuristics. Random search methods have often been applied to problems with Chapter 1. Introduction and Preliminaries 6 constraints on harvesting adjacent blocks of timber or with other harvest dispersal con-straints (O'Hara et al. .1989; Clements et al. 1990; Nelson and Howard 1991; Sessions and Sessions 1990). Monte Carlo integer programming can overcome some of the limitations of random search methods (Daust et al. 1993; Jamnick et al. 1993; Nelson et al. 1991). Lagrangian relaxation was first applied in forestry by Hoganson and Rose (1984) to max-imize the harvest of a large number of stands subject to a non-declining flow constraint. A variety of heuristic methods have been applied to the formulation of adjacency constraints in conjunction with relaxation methods (Gross and Dykstra 1988; Meneghin et al. 1988; Torres and Brodie 1990). Other methods which have been tried include multiple-criteria decision making algorithms (Howard 1991; Howard and Nelson 1993; Nelson et al. 1991), dynamic programming (Ludwig 1993), fuzzy control (Bare and Mendoza 1992) and sim-ulated annealing (Lockwood et ai. 1993). There is evidence that the Biased Random Search Method proposed by O'Hara et al. is one of the most effective methods to solve the harvest scheduling problem with adjacency constraints. Their method showed excellent results with objective function values at most 8% from linear programming upper bound, and at most 4% from the upper bound of a virtually 100% confidence interval they derived for the true optimum. Brumelle, Granot, Halme and Vertinksy (1996) presented a tabu search heuristic, and when tested on a real world problem in the Tangier watershed in British Columbia, their results compared favorably against the heuristic by O'Hara et al. When the adjacency constraints are relaxed, the forest harvest and road construction scheduling problem can be formulated as an extended selection problem presented in Chapter 3 and be solved as a minimum cut problem. However, with the adjacency constraints, the problem is NP-hard. In Chapter 4, I will present a tabu search heuristic to solve this unrelaxed problem to near optimality. Chapter 1. Introduction and Preliminaries 7 1 . 1 . 4 C o n t r i b u t i o n s o f t h e T h e s i s M y study in Chapter 2 was motivated by a study carried out by Stone (1978), a parametric maximum flow algorithm developed by Gallo, Grigoriadis and Tarjan (GGT) (1989), and by a subsequent extension by Arai , Ueno and Kajitani (AUK) (1993). G G T considered a maximum network flow problem in which the capacities of arcs incident to the source or the sink may change as a function of a parameter, and showed that for k = O(n) instances of the parameter, the maximum flows can be found in a time bound of one maximum flow, or, in 0(mn log(n2/rn) + km log(n2/ra)) elementary operations, where n is the number of nodes and m is the number of arcs. It was observed by Stone (1978) that for the parametric maximum flow problem that they studied, the minimum cuts move monotonically with the change of the parameter. As is shown later in this thesis, the Monotone Response and Selection Theorems offer a simple explanation for this monotonicity property. A U K extended the result of G G T and showed that when the capacities of arcs incident to a single node (other than the source or the sink) change, maximum flows for k = 0(n) instances of the parameter can be found in the time bound of two maximum flows. In their study, the minimum cuts are no longer monotone in the parameter. They may move "back and forth" as the parameter changes, but there always exists a selection of minimum cuts that are totally ordered. In light of the wide applicability of the Monotone Response and Selection Theorems, it seems appropriate to conduct a "parallel" study of the algebraic properties that lead to totally ordered optimal solutions. The Monotone Response and Selection Theorems address two closely related issues, namely, "response" and "selection"3. When the optimal solutions are monotone, the "selection" result follows from the "response" result under some mild topological conditions. When the optimal solutions are only totally ordered, 3Details are provided in Section 2.1. Chapter 1. Introduction and Preliminaries 8 the "selection" result is more complex. However, this result is important as it can be used to reduce the search space for optimal solutions in parametric optimization problems. The objective of this thesis is to present algebraic sufficient conditions that ensure the existence of totally ordered selections of optimal solutions and to identify some classes of parametric maximum flow problems for which the G G T algorithmic approach can be possibly applied. Indeed, we present Totally Ordered Response and Selection Theorems which provide sufficient conditions for the totally ordered "response" and "selection" results to hold. Furthermore, we present some necessary and sufficient conditions which ensure the existence of a totally ordered selection of minimum cuts for some classes of parametric maximum flow problems. Since the existence of a totally ordered selection of minimum cuts is a common property for all parametric maximum flow problems that can be solved by the G G T algorithmic approach, our characterization provides some insight into the class of problems for which extensions of the G G T algorithm could be possible. The classes of parametric maximum flow problems that we characterize, for which a totally ordered selection of minimum cuts exists, subsume the class of problems studied by A U K as a special case. I also present some other interesting special cases. For example, I show that one can further allow the capacity of the "center node" in the study of A U K to change and still maintain the existence of a totally ordered selection of minimum cuts. In another special case, I show that a totally ordered selection of minimum cuts exists when the capacities of arcs on a path are parametrically changed, given that no two arcs on the path are parallel 4. Finally, I study the ordering of minimum cuts in some parametric maximum flow problems. It is shown that under certain conditions, minimum cuts form an ordered sequence of cuts when the capacities in the network change. In Chapter 3 of the thesis, I present an extended selection model, which is based on the observation that many modern facilities are multi-functional. In this extension, a job 4 A definition of parallel arcs is given in Subsection 2.2.2. Chapter 1. Introduction and Preliminaries 9 does not require a specific facility to be present. It can be accomplished as long as some required "functions" can be performed by one facility or another. I introduce the notion of tasks and assume that each job requires a set of tasks, and each facility can perform a set of tasks. Thus in my extended model, a job can be performed if the set of tasks required is covered by the set of facilities acquired. In general, the extended selection problem is NP-hard. However, by introducing some natural restrictions in the extended selection model I derive two variants thereof, which can be formulated and solved as minimum cut problems. Apparently, the two variants of the ES model can be used to formulate classes of problems that could not be formulated by the original selection model. Indeed, the original selection model has mainly been used to study some single-period problems. For example, it has been used to model a network construction problem in which one seeks to construct an optimal set of roads. However, it cannot model the associated scheduling problem, to accommodate for the fact that the revenues and costs vary over time. That is, it cannot be used to determine an optimal schedule for the construction of these roads. By contrast, I show in this thesis that the network construction scheduling problem can be formulated as one of the variants of the ES model and can then be solved as a minimum cut problem. It is further shown that the network construction scheduling problem has applications in telecommunications, forest harvest scheduling and open pit mining. For related research on open pit mining, see Dagdelen (1979). Brumelle and Granot (1993) studied some qualitative properties of the repair kit problem, which are also valid for the original selection problem. For example, it was shown that as the weight on the revenue from the jobs increases, the optimal collection of facilities will increase monotonically. In Chapter 3, I carry out a similar qualitative analysis and show that analogous properties exist for the two variants of the ES model. In Chapter 4, I study a forest harvest and road construction scheduling problem. Chapter 1. Introduction and Preliminaries 10 A tabu search heuristic is used to optimize the net present value obtained from the schedules. This algorithm is tested on a real world problem in the Tangier watershed of British Columbia. The schedules generated in this experiment yield much higher net incomes compared with a previous experiment on the same data 5. 1.1.5 Organization of the Thesis The remaining of the thesis contains three chapters. Chapter 2 presents a study of the totally ordered selection problem and its application to parametric maximum flow prob-lems. In particular, Section 2.1 presents the Totally Ordered Selection Theorems. Using these theorems, in Section 2.2, I present a class of parametric maximum flow problems for which totally ordered selections of minimum cuts exist. Some special cases are also studied in this section. Section 2.3 studies the ordering of minimum cuts for some special parametric maximum flow problems. Chapter 3 extends the original selection problem studied by Rhys (1970) and Balinski (1970). Section 3.1 formally introduces the Extended Selection (ES) model. Section 3.2 presents some sub-classes of the ES model that can be formulated and solved as minimum cut problems. Section 3.3 presents some applications of a restricted model discussed in Section 3.2. In particular, a relaxed forest harvest and road scheduling problem can be formulated as the Extended Selection model and be solved with a minimum cut problem. Section 3.4 presents some qualitative properties of the restricted models. Chapter 4 presents a tabu search heuristic for solving the unrelaxed forest harvest and road construction scheduling problem. Therein, Section 4.1 formally presents the model, Section 4.2 presents the tabu search method used, and Section 4.3 presents the results for a scheduling problem in the Tangier watershed in British Columbia. Appendix A contains the pseudo-code for the tabu search heuristic. 5See Brumelle, Granot, Halme and Vertinsky (1996) Chapter 1. Introduction and Preliminaries 11 1.2 Pre l iminar ies 1 .2 .1 Lattice P r o g r a m m i n g Consider a partially ordered set (£ , •<)• I define z = x V y to be the supremum of two elements x and y in £ if x ^ z, y ~5\ z , and x-<w,y^<w,w€.C imply z ~< w. Similarly, I define z = x A y to be the infimum of x and y if z ^ x, z ~< y, and tu <^ x, w -< y, w £ C imply w ~2 z. The set £ is called a lattice if for every pair x £ £ and y (E £ , x A y and x V y are also in £ . A subset S of £ is a sublattice of £ if x £ 5* and y £ S" imply x A y £ 6* and x V y £ 5. Sublattice 5 is lower than sublattice T, or, S '^yT, if for every x £ S and y £ T we have x V y £ T and x A y £ 5. This order is reflexive, antisymmetric and transitive, and so partially orders sublattices of a lattice. Note that the ~<v order can be defined for arbitrary subsets of £ , although its reflexivity will be lost. This order was introduced by Veinott and will be referred to as the Veinott ordering. Suppose (A, <) is a partially ordered set, (£ , -<) is a lattice and {S\} is a family of subsets of £ indexed in A. If for any Ai and A2 in A, Ai < A2 implies that S\t is lower than S\2 (respectively, Sx2 is lower than S^), then {S\} is ascending (respectively, descending) jn A on A. If Xi < A2 implies that x -< y (respectively, y -< x) for each x £ S\l and y £ S\2, then {S\} is strongly ascending (respectively, strongly descending) in A on A. See Topkis (1978), Veinott (forthcoming) and Zimmermann (1981) for a more detailed discussion on lattice programming. In a finite sublattice S, there always exists a unique minimum element u such that for each x £ S", u Z2 x. This is true since u is simply the infimum of all elements in S. Similarly, a unique maximum element exists in S. If a finite subset S of £ is not a sublattice, at least one minimal element u exists in Chapter 1. Introduction and Preliminaries 12 S such that x € S and x -< u imply x = u. Such a minimal element can be found by descending along a totally ordered chain in S until the bottom of the chain is reached. When S is not a sublattice, a minimal element may not be unique. Similarly, there exists at least one maximal element in a finite set S. A function / defined on a lattice C is submodular if for every two elements x and y in f(xVy) + f(xAy)<f(x) + f(y), and supermodular if f(xVy) + f(xAy)>f(x) + f(y). A function / is modular if it is both submodular and supermodular. A function f(x,X) on X x A has the isotone differences property with respect to (x,X) if for any Aj < A 2 , f(x,\2) — f(x,Xi) is increasing in x, and has the antitone differences property if / ( x , A 2 ) — / ( x , A i ) is decreasing in x. Topkis (1978) showed that the isotone and antitone differences properties are symmetric between x and A; i.e., the above definitions of isotone and antitone differences can be equivalently defined by the monotonicity of f(x2, A) — / ( x i , A) in A for any xx ^ x2. 1.2.2 Parametric Maximum Flow Problems Let G(N, A) denote a directed network, with nodes iV and arcs A. Let s and t be the source node and the sink node, respectively. A n arc capacity, c,-j, is associated with each arc The maximum flow problem in G(N, A) is concerned with finding a flow from s to t of maximum value which does not violate the capacity constraints. Formally, the Chapter 1. Introduction and Preliminaries 13 problem can be stated as follows: max Hi:(s,i)eA x s i subject to Ei:(i,k)eA xik = Ej:(k,j)eA xkj for each k <E N\{s, t}, 0 < Xij < Cij for each £ A. In this study, I assume that arc capacities are strictly positive. This allows me to avoid some degenerate cases. A path in a network is a sequence, < (ni,n2), n2, (n2, n 3 ) , n 3 , • • •, nk-\, (rik-i,nk), nk >, of nodes and arcs. When there is no ambiguity, the above path will also be denoted as < n 1 ; ra2, • • • ,rik >• A simple path is one in which the nodes do not repeat. A n s-t path is a simple path from the source node s to the sink node t. For simplicity of presentation, I will write pi fl p2 = 0 to denote the fact that paths pi and p2 are vertex disjoint; e G pi to denote the fact that arc e is in path p i ; and u € px to denote the fact that node u is in path pi. The flow in a network can alternatively be formulated in the arc-chain form. Let V — {p l 5 p2, • • •, pm} be the collection of all directed simple s-t paths in G(N,A). A flow in G(N, A) is a'function h from V to the nonnegative reals, and the maximum flow problem can be formulated as: max JZpev h(p) subject to £ P e 7 > aij(p)h(p) < °ij for e a c n (hJ) e w here aij(p) = 1 i f ( * , j ) G p , . 0 if g p . The two formulations are equivalent; see for example, Ford and Fulkerson (1962). Chapter 1. Introduction and Preliminaries 14 In a node-and-arc capacitated network, node capacity constraints are introduced: Xik < Ck for each node k G N\{s,t}, i:(i,k)eA where is the capacity of node k. Generally, in a maximum flow problem over a network G(N, A) both arcs and nodes may have capacities. However, a node-and-arc capacitated network can be transformed into an equivalent arc-capacitated network6. A cut is a bi-partition (X, X) of the node set N, where s G X and t £ X? A partial order can be defined on the set of cuts in a network. Namely, (X, X)^C(Y, Y) if X C Y. Under this partial order, the set of cuts in a network is a lattice. (X,X) may be interpreted as the set of arcs between the two sets of nodes X and X. That is, (X,X) = {(ij) G A \ i £ X , j G X } . More generally, for two subsets X and Y of A T , define (X, Y) to be the set of arcs {(hj) € A\i £ X,j e Y} and the capacity of (X, Y) to be c(X, Y) = Y,i£x,jeY c%j- m particular, the capacity of cut (X, X) is defined as c(X,X) — Y^i^x jex c « i - A rninimum cut in a network is one whose capacity is minimum among all cuts in the network. A parametric maximum flow problem is a maximum flow problem in which the ca-pacities of the arcs may change as functions of a parameter A. In such a problem, the notation is modified to include the parameter, so the capacity of an arc (i,j) is denoted by c(A; i,j) and the capacity of (X, Y) is written as c(A; X, Y). Again, I assume that the capacities on the arcs are positive to avoid degenerate cases. 6Transforming a node-and-arc capacitated network into an equivalent arc capacitated network may destroy some nice properties of the original network. For example, such a transformation may destroy the planarity of the original network. Therefore, algorithmically it may be more efficient to consider the original node-and-arc capacitated network rather than its equivalent arc capacitated network. However, since I do not deal with algorithmic issues in this thesis, I wil l consider only arc capacitated networks for ease of presentation. 7 Cuts defined in this way are frequently called node partition cuts. Since cuts in this article are always node partition cuts, they are simply referred to as cuts. C h a p t e r 2 T o t a l l y O r d e r e d O p t i m a l S o l u t i o n s a n d P a r a m e t r i c M a x i m u m F l o w s 2.1 T o t a l l y O r d e r e d Se lec t ions Let (£ , rO be a lattice. Let / (x ,A) be a function defined on £ x A, where A is the parameter. The objective is to minimize /(- ,A) for each A. Let F*(X) be the set of minimum solutions of /(•, A) for a specific A; i.e., F*(X) = argminx{f(x, A) : x G £ } . For an arbitrary subset A 0 of A, a monotone sub-selection of optimal solutions is a mapping, x(-), from A 0 to £ , such that x(X) G F*(X) for each A € A 0 and x(A) is monotone in A. Similarly, a totally ordered sub-selection of optimal solutions is a mapping, x(-), from A 0 to £ , such that x(A) G F*(A) for each A G A 0 and the collection {x(A)|A G A 0 } is totally ordered by A monotone (respectively, totally ordered) selection of optimal solutions is a sub-selection when Ao = A. If F*(X) = 0 for any A G A, then A can be ignored in this study. Therefore, I assume that F*(X) ^ 0 for every A G A. My study is based on lattice programming theory and is closely related to the problem of monotone selections studied by Topkis and Veinott. In this section, I first present the Monotone Response and Selection Theorems and then introduce some sufficient conditions under which a totally ordered selection of optimal solutions exists. 15 Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 16 2 . 1 . 1 The Monotone Response and Selection Theorems The Monotone Response and Selection Theorems assume that a partial order < exists on the set A of parameters, and present sufficient conditions under which the set of optimal solutions, F*(X), is ascending in A with respect to the Veinott ordering, and under which a monotone selection of optimal solutions exists. In order to facilitate further development, I provide a proof of the Monotone Response Theorem. M y proof, which is slightly different from the original one, focuses on the valid-ity of two inequalities which play a prominent role in this paper. These two inequalities are f(x, A O + / ( y , A 2 ) > f(x V y, A O + f(x A y , A 2 ) (2.1) and f(x, A O + f(y, A 2 ) > f(x A y, A O + f(x V y , A 2 ) . (2.2) T H E O R E M 2 .1 (Monotone Response Theorem) Suppose ( £ , ^ ) is a lattice and ( A , < ) is a partially ordered set, / ( x , A ) is submodular in x for each A £ A , and / ( x , A ) has antitone (respectively, isotone) differences in (x,X) on C x A . Then, F*(X) is an ascending (respectively, descending) sublattice in X. Proof . The fact that F*(X) is a sublattice for each A follows from the sub modularity of / ; see, e.g., Theorem 4.1 of Topkis (1978). Consider A x < A 2 in A . For all x and y in / ( x , A i ) - f(x A y , A O > f(x, A 2 ) — f(x A y , A 2 ) by the antitone differences property of /(•, •) > / ( x V y , A 2 ) - / ( y , A 2 ) by the submodularity o f / (• , A 2 ) . Thus (2.2) is valid for arbitrary x, y and A i < A 2 . When x £ F * ( A 1 ) and y £ F * ( A 2 ) , (2.2) must be satisfied with equality, and x A y £ F*(Xi) and x V y £ F * ( A 2 ) . This establishes that F * ( A 0 ^ y i 7 * ( A 2 ) . Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 17 Similarly, if / has isotone differences, then (2.1) holds for all x, y and A t < A 2 . Moreover, if x G F*(X1) and y G F*(A 2 ) , then (2.1) is satisfied with equality. Thus x A y G F*{\2), x V y G F ^ ) and F * ( A 2 ) ^ y F * ( A 1 ) . n T H E O R E M 2.2 (Monotone Selection Theorem) Suppose the conditions in The-orem 2.1 hold. • If it is further assumed that A is countable, then a monotone selection of optimal solutions exists. • Alternatively, if it is further assumed that there exists a minimum element s(X) (respectively, a maximum element S(X)) in F*(X) for every A G A, then s(X) (re-spectively, S(X)) is monotone in X. The original Monotone Selection Theorem (Theorem 6.2 in Topkis, 1978) corresponds to the second half of Theorem 2.2. It asserts that if f(x, •) is lower semi-continuous in x and the parameterized feasible set is compact, then there exists a minimum element, 5(A), and a maximum element, S(X), in F*(A), which are both monotone in A. The proof can be found in Topkis (1978). Below I augment the original theorem by presenting the proof of the first half of Theorem 2.2. Proof. We will only prove Theorem 2.2 for the case when the conditions in The-orem 2.1 are such that F*(X) is ascending in A. Let A = {A1,A2,---}. Suppose a monotone sub-selection, {x(X) \ X G A/;}, has been found for a subset of parameters Ai. = {Ai, A2, • • •, A^ } such that A,- < Aj implies x(A;) ~< x(Xj), i , j = 1, 2, • • • , fc. To prove the first claim in the theorem, it is enough to show that the monotone sub-selection can be extended to A^ U {A^ +i}. Let A], = {A G Afc|A > A^ +i} and A2. = {A G Afc|A < Afc+i}. Let x\+i be an arbitrary element in J^ 1*(A -^j-i). Let xf,_^± be the infimum of {x(A)|A G Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 18 Alk] U and let x(\k+i) be the supremum of {x(A)|A G A 2 } U {x2k+1}. Applying the Monotone Response Theorem inductively, it can be seen that x(Xk+i) G F*(Xk+i). By the definition of supremum, x(Xk+i) >z x(X) for each A G A2k. Consider an arbitrary A G A\. By the definition of A\ and A 2 . , and the inductive assumption, x(A) y x(X') for any A' G A2k. Furthermore, by the definition of x £ + 1 , x(A) ^ x\+\- Thus x(A) is an upper-bound of {x(A)|A G A2.} U {xk+l}. Since x(Afc+ 1) is the least upper-bound of {x(A)|A G A2k} U {x2k+1}, x(Xk+1) ^ x(A) must be valid. Therefore, introducing x ( A / t + 1 ) extends the original monotone sub-selection to A^ U {X^+i}. • It can be seen from the proof of Theorem 2.1 that when /(•, •) satisfies the conditions in the theorem, either (2.1) holds if /(•,•) has isotone differences or (2.2) holds if /(•,•) has antitone differences. It is shown in the next section that a parametric function / (x , A) satisfying either (2.1) or (2.2) for any pair of Ax and A 2 ensures the existence of a totally ordered selection of optimal solutions. 2 . 1 . 2 Total ly Ordered Response and Selection Theorems If it is further assumed in the second half of the Monotone Selection Theorem that A is totally ordered, then a totally ordered selection of optimal solutions will exist. However, the hypothesis of Theorem 2.1 is not necessary for a totally ordered selection of optimal solutions to exist. Indeed, consider the example shown in Figure 2.1. The directed network G(N, A) is composed of 5 nodes on a single directed path. The capacity on arcs ei and e\ is 1.1 — A and the capacity on arcs e2 and ej, is 0.1 + A. Let f(X, A) be the capacity of (X, X) under parameter A, where X C N is a subset of nodes containing s. Then (2^, C ) is a lattice. When A = 1, there are two minimum cuts, (Xi,Xi) and (X2,X^), where Xl = {s} and X2 = {s,a,6,c}, so F*(l) = {{s},{s,a,b,c}}. When A = 0, there are also two minimum cuts, (Yi ,Yi) and (Y2,Y2), where Y\ = {s,a} and Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 19 Y2 = { 3 , a, 6}, so F*(0) = {{s, a}, { 5 , a, 6}}. It can be seen that F*(0) and F*( l ) are not ordered by the Veinott ordering. ex e2 e3 e4 • >• a« =>• .s a 6 c £ Figure 2.1: The sets of minimum cuts are not totally ordered However, in the above example, a totally ordered selection of optimal solutions does exist. In fact, one can pick any solution from F*(0) and any solution from F*(l), and the two cuts will be ordered. Thus a totally ordered selection of optimal solutions is possible even though {F*(A)|A G A} is not totally ordered. In the remainder of this subsection, I consider three successively weaker conditions. Even the weakest is sufficient for the existence of a totally ordered selection of optimal solutions. However, they differ in their ability to ensure that totally ordered sub-selections can be extended to a complete one on A. C O N D I T I O N A For every A 1 ; A 2 G A, either (2.1) holds for every x <G F*(Ai) and y G F*(\2), or (2.2) holds for every x G ^ ( A i ) and,y G F*(X2). C O N D I T I O N B For every XUX2 G A and arbitrary x G F*(Xx), y G F*(X2), either (2.1) or (2.2) holds. Note that for a fixed pair Ai and A 2 , Condition A requires inequalities (2.1) or (2.2) to hold "uniformly" for every x G F*(X1) and y G F*(A 2 ) . In Condition B however, it is permissible for (2.1) to hold for some pairs of x and y and for (2.2) to hold for some other pairs. Clearly, Condition A implies Condition B. C O N D I T I O N C For every A, , A 2 G A and x G F*(A X ) , y G F* (A 2 ) , there exist u,v G C satisfying u ~< x A y and x V i / X w such that either f(x, A x) + f(y, X2) > f(u, AO + f(v, A 2 ) , (2.3) Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 20 Condition B implies Condition C, since when the former is satisfied, one can choose u = x A y and v = x V y. T H E O R E M 2.3 ( T o t a l l y O r d e r e d R e s p o n s e T h e o r e m ) Let C be a lattice and A be an arbitrary set, and let f be a function defined on £ x A . The collection {F*(A)|A £ A} is totally ordered by ^<y if and only if Condition A holds. P r o o f . I first show the "if" part of the theorem. Consider A 1 ; A 2 £ A. Suppose (2.1) is valid for every x £ F*(X1) and y £ F*(X2). Since f(xyy,X1) > f(x,Xi) and f(x A y, X2) > / ( y , A 2 ) , (2.1) and the above two inequalities are satisfied as equations. Thus x V y £ F*(Ai) and x A y £ F*(X2), implying that F * ( A 2 ) ^ y F * ( A , ) is valid. Note that for an arbitrary A £ A, one can show that F*(A) is a sublattice by letting Xi = X2 = X in (2.1). Similarly, if (2.2) holds for every x and y, then F*(X1)^VF*(X2). This shows that the collection {F*(A)|A £ A} is totally ordered. To show the "only if" part of the theorem, let A x and A 2 be arbitrary parameters in A. Since {F*(A)|A £ A} is totally ordered, either F * ( A i ) ^ F * ( A 2 ) or F^X^yF*^). First suppose F * ( A ! ) X y F * ( A 2 ) so that for any x £ F*(Ai) and y £ F* (A 2 ) , x Vy £ F*(A 2 ) and x A y £ F*(A X ) . Thus f(x V y, A 2) = f(y, A 2) and f(x A y, A x) = f(x, A x ) , and (2.2) is valid. Similarly, if F ^ A ^ y F * ^ ) , then (2.1) is valid. • The Totally Ordered Response Theorem bears some resemblance to the Monotone Response Theorem. However, the former theorem assumes a weaker condition, and it does not require A to be partially ordered. or (2.4) Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 21 L E M M A 2.4 Let C be a lattice, A be an arbitrary set, and f be a function defined on £ x A. Condition B holds if an only if for every Xx and X2 in A and every x £ F*(A 1 ) and y £ F*(X2), either x A y £ F*(X1) and x V y £ F* (A 2 ) , or x A y £ F*(A 2 ) and x V y £ F* (Ai ) . Since the proof of this lemma is similar to that of Theorem 2.3, it is omitted. L E M M A 2.5 Suppose Condition C holds for /(•, •) defined on a lattice C and an arbit-rary set A . Let Xx and A 2 be arbitrary elements in A. Then for an arbitrary x £ F*(X1), either there exists an m £ F*(A 2 ) such that m •< x, or there exists an M £ F*(A 2 ) such that x <M. P r o o f . Pick an arbitrary element y £ F*(A 2 ) . By Condition C, one can find u •< x A y and v y xV y such that either u £ F*(A 2 ) or v £ F*(A 2 ) . If the former holds, then let m = u, otherwise the latter holds and let M = v. • L E M M A 2.6 Let C be a lattice, let Ai and A 2 be arbitrary values in A, let x £ F*(Ai) be an arbitrary optimal solution, and let s(A2) and 5(A 2) be, respectively, the minimum element and the maximum element in F* (A 2 ) . If Condition C is valid, then either x ~< S(X2) or s(X2) di x. P r o o f . The lemma follows directly from Lemma 2.5, since M ~< S(X2) and s(A 2) ~< m. • T H E O R E M 2.7 ( S t r o n g T o t a l l y O r d e r e d S e l e c t i o n T h e o r e m ) Let £ be a lattice, let /(•,•) be defined on £ x A, and suppose Condition B is satisfied. Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 22 • Assume that A is a countable set, then a totally ordered sub-selection of optimal solutions {x(X) G F*(A)|A G A 0 } for a finite set Ao can be extended to a totally ordered selection on A . • Alternatively, if it is assumed that a minimum element s(X) (respectively, max-imum element S(X)J exists in every F*(X), then the collection {5 (A)} (respectively, {5(A)},) is totally ordered. Proof. I first prove the first half of the theorem. The mapping x(-) can be constructed by the following inductive procedure. Suppose that at a certain step, one has obtained a totally ordered sub-selection for A * , which consists of k elements and contains Ao as a subset. Since Ak is finite, the elements in A^ can be denoted by A l 5 A 2 , • • •, A .^ so that X\ d x2 d • • • ^ Xki where X{ = x(A;) for i = 1, 2, • • •, k. Choose an arbitrary Xk+\ in A\Afc. I wish to find = x(Xk+\) such that x\+i G F*(Xk+i) and the collection Cfc+i — {xi, x2->" ' ' ixkixk+i} is totally ordered. By Lemma 2.5, F*(X/C+1) either contains an element mi such that m 2 ^ xx or an element M\ such that x\ < M\. If the former is true, let Xk+i = mi and Ck+i = CfcU{xfc+i} is totally ordered. If the latter is true, let I be the largest index such that there exists an element M / in F* (A^ + 1 ) for which x\ -< M\. If / = k, let Xk+i = Mi and Ck+i = Ck^J{xk+i} is again totally ordered. If / < k, then there does not exist an element M/+i in F*(Xk+i) such that X[+i d Mi+i- Consider x / + 1 V Mi and xi+i A M ; . By Condition B , one of them must be in F*(Xk+i). The former cannot be in i ? *(Afc + 1 ) , since otherwise, there exists an element M ; + i = x;+i V M / in F*(Xk+i) satisfying ^ M / + i , contradicting the observation that no such M/+i exists. So xi+i A Mi is in F*(Xk+i). Let Xk+i = x;+i A M / . Clearly, Xfc + 1 < xi+i- Since x; < Mi and x\ -< £;+i> it follows from the definition of A that xi d £(+1 A M ; = Xk+\- Thus the collection Ck+i = Ck U {x^+i} is totally ordered. This completes the proof of the first half of the theorem. Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 23 To prove the second half of the theorem, consider two arbitrary instances of the para-meter Ai and A 2. Since s(X1) A s(A2) is either in F*(X1) or in F*(A 2), s(Xi) A s(A2) must be equal to either s(X1) or s(A2). In the former case, ^(A^ -< s(A2) and in the latter case, •s(A2) ~< s(Ai). Similarly, S(Xi) and 5(A2) must be ordered by ~<- • Figure 2.2: A n infinite lattice £ When a parametric optimization problem needs to be solved for many instances of the parameter, optimal solutions for a subset of parametric instances are obtained first. If one knows that an arbitrary totally ordered sub-selection of optimal solutions can be extended to a complete one, then the search for optimal solutions can be limited to the subset of feasible solutions that are totally ordered with the solutions already obtained. Since the parametric instances must be solved successively, they form a countable sequence. Therefore, the countability assumption for A is not restrictive. Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 24 C O R O L L A R Y 2.8 If C is finite, then the first claim in Theorem 2.7 still holds without requiring A to be countable. Proof. Observe that if for two values of the parameter, Xx and A 2 , F*(X1) = F*(X2), then one only has to select an optimal solution x(Xi) for Ai and let x(A2) = x(X\). Let n = |£| be the cardinality of £ . For each A € A, F*(A) must be one of the 2 n subsets of £ . Therefore, one has to consider at most 2™ representative instances in A. Since this set of representative instances is finite and thus countable, the first claim in Theorem 2.7 applies and the proof is complete. • The first half of Theorem 2.7 is not valid without assuming that Ao is finite. Indeed, consider the counter example illustrated in Figure 2.2. The figure illustrates an infinite lattice £ where i ~i j if there exists a directed path from j to i. Let A = {A0, Xx, A 2 , • • • }. Define a function /(•, •) on £ x A such that for i > 1 Clearly, F*(A;) = {1,2, • • •, i} for i = 1, 2, • • and F*(A 0 ) = {1', 2', • • • }. Condition B holds in this example. For instance, consider 5 6 F*(A 5 ) and 2' € F*(X0). 5' = 5 V 2' is in F*(X0) and 2 = 5 A 2' is in F*(A 5 ) . Suppose that initially one has a totally ordered sub-selection x(-) on the infinite set A 0 = {A 1 ; A 2 , • • •}, where x(X{) = i for i = 1, 2, • • •. Notice that A 0 is not in A 0 . It can be seen that for any x(X0) £ F* (A 0 ) , the collection {x(X{)\i = 0, 1, 2, - • • } cannot be totally ordered. On the other hand, consider a finite A 0 , say, {A l 5 A 2 , A 3 } , and again let a;(A,-) = i for i = 1,2,3. Now one can select x(A 0) = 3' 1 for other x G £ for x = 1, 2, • • -, i and for other x £ £. Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 25 and x(X) = 3 for A = A 4 , A 5 , - - - , and the collection {x(Xi)\i = 0, 1, 2, • • • } is totally ordered. The next theorem uses the weaker Condition C, and ensures that the mapping x(-) can be extended when A 0 contains a single element. T H E O R E M 2.9 (Weak Total ly Ordered Selection Theorem) Let C be a lattice, A be an arbitrary set, and let /(•,•) be defined on Cx A . Suppose Condition C holds, and a minimum element s(X) and a maximum element S(X) exist in every F*(X). Then the collections {s(X)} and {S(X)} are totally ordered. Furthermore, for an arbitrary A 0 G A and an arbitrary xQ G F*(X0), a mapping x(X) from A to C can be constructed such that x(X0) = x0, x(X) G F*(X), and the collection C = {x(A)|A G A} is totally ordered. Proof . To prove the first claim, let .s(Ai) and s(A2) be minimum elements in i ? * (A 1 ) and F*(X2), respectively. By Condition C, one can find u •< -s(Ai) A s(A 2) such that either u G F*(Xi) or u G F*(X2). If the former holds, then since u ~< s(Xi), it follows that u — s(X1) = s(Ai) A s(X2) and so s(Ax) d s(X2). Similarly, if u G F * ( A 2 ) , then •s(A2) -< -s(Ai). This argument shows that the collection {s(A)} is totally ordered, and one can similarly demonstrate that the collection {5"(A)} is totally ordered. I now prove the second claim in the theorem. For each A ^ A 0 , by Lemma 2.6, either s(X) ~< x0 or x0 ~< 5(A). If the former is valid, then let x(X) = s(X), otherwise, let x(X) — 5(A). The minimum elements precede x0 which in turn, precedes all the maximum elements with respect to the ~< order. From the first half of this theorem, all the minimum elements selected are ordered among themselves and the same is true for all the maximum elements. Thus the selection x(-) is totally ordered. • Condition C is not sufficient to ensure that a totally ordered sub-selection of optimal solutions on an arbitrary An can be extended to a complete one. Indeed, consider the Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 26 counter example stemming from Figure 2.3. Again, elements of £ are represented by the solid nodes, and if two elements satisfy i X j, then there is a directed path from j to i. C is clearly a lattice. Suppose that A = {1,2,3}, F*(l) = {x 1 ? x 3 } , F*(2) = {m, M } and F*(3) = {x2,x4}. It is not difficult to verify that Condition C is valid. For example, for xx £ F*(l) and m £ F*(2), one can let u = x3 = Xi A m and v = M >z x5 = x1 V m , thus u £ F* ( l ) and v £ F*(2), and either (2.3) or (2.4) is satisfied as an equality. Suppose initially one is given a mapping x(-) on A 0 = {1,3} where x(l) = x\ and x(3) — x2. No matter how one chooses x(2) (either m or M ) , the collection C = {x(A)|A = 1,2,3} cannot be totally ordered. x 4 x3 Figure 2.3: A n example for which a sub-selection cannot be extended Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 27 2.2 Ordered M i n i m u m Cuts in Parametr ic M a x i m u m F l o w Problems In this section, I apply the Totally Ordered Selection Theorems to derive a necessary and sufficient condition for the existence of a totally ordered selection of minimum cuts in a parametric maximum flow problem. 2.2.1 Monotone m i n i m u m cuts M y result is related to a parametric maximum flow problem studied by G G T (1989). Proir to the development of the G G T algorithm in this study, Stone (1978) observed that the sets of minimum cuts in this parametric maximum flow problem are ascending in the parameter. Theorem 2.10 below presents this result. Here I show that it follows easily from the Monotone Selection Theorem. T H E O R E M 2.10 Let G\(N,A) be a network in which the capacity, c(A; s,i), of each arc (s.i) leaving the source is a nonnegative, nondecreasing function of A £ IR, the capacity, c(X;j,t), of each arc (j,t) entering the sink is a nonnegative, nonincreasing function of X, and the capacities of all other arcs are constant. Let F*(X) be the set of minimum cuts for an instance of the parameter X. Then F*(X) is a sublattice that is ascending in A. M y alternative proof1 of Theorem 2.10 is based on the following two lemmas, where f(X,X) denotes the capacity of (X,X) under parameter A. Lemma 2.11 appears in Ore (1962). L E M M A 2.11 f(X, A) is submodular in X for a fixed X. XI suspect that this alternative proof is not new, but I do not have a reference for it. I present this proof because it is closely related to my study. Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 28 Proof . Let (X,X) and (Y,Y) be two cuts in G. I partition the set of nodes N as follows: Nj. = X n Y, N2 = X \ Y, N3 = Y \ X, N4 = X n Y. Then (X n Y, X n Y) = (Nu7h) and (A- U y , X T J Y ) = (A/4, AT4). Observe that / ( X , A) = c(A; A^, 7 V 3 ) + c(A; A^, iV 4) + c(A; W 2 , iV 3) + c(A; N2, N4), f(Y, A) = c(A; iVi , AT2) + c(A; A^ , iV4) + c(A; AT3, W2) + c(A; AT3, AT4), / ( X n y, A) = c(A; ATj, A 2 ) + c(A; i V l 5 A/3) + c(A; i V l 5 AT4), / ( X U Y , A) = c(A; A^, A^4) + c(A; W 2, W4) + c(A; A^3, W 4). Then, / ( X , A) + f(Y, A) - / ( X f)Y,X) — f(X U Y, A) = c(A; N2, N3) + c(A; i V 3 , 7 V 2 ) > 0, which implies the sub modularity of / ( • , A) for a fixed A. • L E M M A 2.12 f(X,\) has antitone differences. Proof . For two cuts (X,X) and (Y, Y) such that X C Y, f(Y, A) - f(X, A) = c(A; Y\X,Y) - c(A; X , y \ X ) . (2.5) In (X,Y\X), the only arcs with variable capacities are those incident to 5 which have nondecreasing capacities as functions of A. In (Y\X,Y), the only arcs with variable capacities are those incident to t which have nonincreasing capacities as functions of A. Thus (2.5) is nonincreasing in A. • P r o o f of Theorem 2.10. The conditions set forth in Theorem 2.1, namely the sub modularity and antitone differences conditions for f(X, A), are verified in Lemmas 2.11 and 2.12. n Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 29 2.2.2 Para l le l A r c s in M a x i m u m Flow Problems In this section, I introduce the notion of parallel arcs, which is independent of arc capa-cities and only depends on the network topology. M y study of ordered minimum cuts in the next subsection will depend on this relationship. D E F I N I T I O N 2.1 Two arcs (i, j ) and (k,l) are parallel if there exist simple paths px from s to i, p2 from s to fc, p3 from j to t, and p 4 from / to t such that P i H p 4 = 0 , p2 n P 3 = 0 , pi fl P3 = 0 and p2 fl p 4 = 0 . In this case, I call the subgraph of G spanned by (hj)i (k,l), Pi, Pi, P3 and p4 a bypass between (i,j) and (fc,/). Intuitively, if two arcs and (k,l) are parallel in C , then there exists a simple s-t path pa =< P i , ( i , i ) , P 3 > from s to t that bypasses ( fc , / ) and another simple s-t path pb =< p 2 , ( f c , / ) , p 4 > from s to £ that bypasses Parallel arcs are illustrated in Figure 2.4, where arcs and (fc,/) (shown in bold lines) are parallel. . v t > •=* ^ » 5 * - - " " PA k I Figure 2.4: Parallel arcs For an arbitrary directed network, verifying whether a pair of arcs are parallel is N P -hard. This is due to the fact that finding two vertex-disjoint paths between two pairs of nodes in directed graphs is NP-hard. See Fortune, Hopcroft and Wyllie (1980). P i , s u » •' P2 Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 30 D E F I N I T I O N 2.2 Let and (fc,/) be two parallel arcs in a directed network G. Arc (i,j) is called a front arc with respect to (k,l) if in every bypass between (i,j) and (A;,/), i is the last common node in pi and p2. Arc (fc,/) is called a back arc with respect to if in every bypass between and (fc,/), / is the first common node in p3 and Pi-Figure 2.5 illustrates the notion of front and back parallel arcs. In part (a), is a front arc with respect to (k,l) and (fc,/) is a back arc with respect to In part (b), is a front arc with respect (fc,/), but (fc,/) is not a back arc with respect to (i,j), since in a bypass spanned by the two arcs and p l 5 p2, p'3 and p4, / is not on p'3. In part (c), arc is both afront arc and a back arc with respect to (fc,/). L E M M A 2.13 Let G(N,A) be a directed network with positive arc capacities. If an arc (i,j) is in a minimum cut (X,X), then there exist simple paths p1 from s to i and p2 from j to t such that pi is contained in X and p2 is contained in X. Proof. In a maximum flow, all forward arcs in a minimum cut are saturated. Thus any arc i & X and j £ X, is saturated in a maximum flow. Since the capacities are strictly positive, the flow on arc (i, j) is positive. By the arc-chain representation of the flow, there must exist a simple path p from s to t containing (i, j), such that the flow h(p) on this path is strictly positive. Since in a maximum flow, the flow on every arc crossing a minimum cut backwards is zero, path p can only cross (X, X) exactly once. Let pi be the sub-path of p from s to i and p2 be the sub-path of p from j to t. Since p crosses (X,X) only once, p\ and p2 have the desired property. • Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 31 P3 S I • Pi t • 3 * I PA 7k P2 (a) P's P 3 5 Z Pi i p4 ."k P2 (b) Pi •••• 5 P2 4 PA k P3 (c) Figure 2.5: Front and back arcs Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 32 2.2.3 Totally Ordered Selections of Minimum Cuts In this subsection, I consider parametric maximum flow problems in a directed network G(N, A) with positive arc capacities. Each instance of the parametric maximum flow problem corresponds to a capacity function c(-; •) : A x A 4 M+ such that c(A ; e) is the capacity of arc e under parameter A. GGT (1989) showed that for any parametric maximum flow problem in which the capacities of arcs leaving the source node are increasing functions of A, and the capacities of arcs entering the sink node are decreasing functions of A, the sets of minimum cuts are ascending in A. Notice that this result does not pertain to any specific parametric capacity function c(-; •) on G. Rather, a class of parametric capacity functions is specified such that the aforementioned property holds for every capacity function in this class. My main concern in this subsection is to characterize classes of parametric capacity functions such that for every capacity function in these classes a totally ordered selection of minimum cuts exists. To this end, I use the following two ways to specify classes of parametric capacity functions. Type I. For a directed network G(N, A), a class of parametric capacity functions can be determined by specifying the set of arcs Av £ A , whose capacities may change. Formally, a Type I class of parametric functions is defined by: T-(AV) = {c(-; •) | c(-; e) is constant for each arc e £ A\AV}. Type I I . For a network G(N, A), a class of parametric capacity functions can be determ-ined by specifying the set of arcs Av £ A, whose capacities may change, the set of arcs A^ C A„, whose capacities may increase in A, and the set of arcs A~ C Av, whose capacities may decrease in A. Formally, a Type II class of parametric capacity Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 33 functions is defined as follows: Jr(Av, A+, Av ) = {c(-; •) | c(-; e) is constant for each arc e £ A\AV, c(A; e) is a nondecreasing function of A for each arc e £ A*, c(A; e) is a nonincreasing function of A for each arc e £ A~}, where A+ and A~ are both subsets of Ay, and A+ fl A ~ = 0 . For any c(-; •) £ .^(A,,, A+, A ~ ) , there is no restriction on the parametric changes on any arc e £ A„\(A+ U A ~ ) . Thus for an arc e £ AV\(A+ U A ~ ) , c(A;e) can be an arbitrary function of A. Although the Type I class is a special case of Type II class, I distinguish between them for clarity of presentation. Special cases of the class of parametric capacity functions T(AV, A+, A~) were considered in the literature. Indeed, G G T considered a class of parametric capacity functions F(AV, A+, A~), where A+ = {(s,i)\(s,i) £ A,Vz £ N}, A~ = {(i,t) | (i,t) £ 4 , V i £ N} and Av — A+ U A~. (I assume that arc (s,t) does not exist in the network.) They showed that for every capacity function in T{AV, .4+, A ~ ) , the sets of minimum cuts are ascending in A. A U K examined the class of capacity functions T{Av,At,A~), where A+ = {(v,i)\(v,i) £ A^i £ N} U {{i,v)\(i,v) £ A,Vz £ iV}, A~ = 0 and AV~A^ for a specific node v called the "center node". They showed that for every capacity function in T(AV, A+, A ~ ) , a totally ordered selection of minimum cuts exists. The classes of parametric capacity functions that I propose to study are broad enough. They subsume the classes of parametric capacity functions studied by G G T and A U K as special cases. Observe that in the above two types of classes, I only restrict the set of arcs whose capacities may change and the direction of such a change. Another possible way of defining a class of parametric functions is to further specify restrictions on the Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 34 magnitude of the changes2, which is not studied in this thesis. My goal is to characterize the sets Av, and A~ which will ensure the existence of a totally ordered selection of minimum cuts. Indeed, Theorem 2.14 below provides a necessary and sufficient condition for the existence of a totally ordered selection of minimum cuts for every capacity function in the class T{AV, A~). T H E O R E M 2.14 Let G(N, A) be a directed network and J7^, A+, A~) be a Type II class of parametric capacity functions. A totally ordered selection of minimum cuts exists for every capacity function c(-, •) in J-(AV, A 4 / , A~) if and only if for each pair of parallel arcs ei and e2 in Av> at least one of the following conditions is valid: (i) e\ and e2 are either both front arcs or both back arcs, and ex and e2 are either both in or both in A~. (ii) Either ex or e 2 is a front arc and the other is a back arc, and one of them is in A+ and the other is in A~. (iii) Either ex or e 2 is both a front arc and a back arc. Furthermore, if any of the above conditions are satisfied, any totally ordered sub-selection of minimum cuts can be extended to a totally ordered selection. P r o o f of the "on ly i f " P a r t . Suppose there exist a pair of parallel arcs ex = (i,j) and e2 = (k,l) in Av such that none of conditions (i), (ii) or (iii) is satisfied. It suffices to construct a capacity function c(-; •) £ J-(AV, A+, A~) for which a totally ordered selection of minimum cuts does not exist. Since ex and e2 do not satisfy condition (iii), neither of them is both a front arc and a back arc. Since neither condition (i) nor condition (ii) holds, at least one of the following three cases must be valid. 2See McCormick (1995) for an application of the G G T method to some parametric maximum flow problems where the magnitude of parametric capacity change is restricted. Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 35 s a •' 1 > 3 \ \ > 3 « J t (1) 2 ! 3 3 s a .-' •ip*. 3 2 \ • 3 * X j-1b / (2) Figure 2.6: G' for Case 1 Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 36 s a . * \ 3 4 2 > (1) / s > t 11 2 (2) Figure 2.7: G ' for Case 1 Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 37 s s Figure 2.9: G' for Case 3 Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 38 Case 1 At least one of the arcs ex and e2 is neither a front arc nor a back arc. Case 2 e\ and e2 are either both front arcs or both back arcs (i.e. i = j or k = /), and the capacities of c\ and e2 are allowed to change in opposite directions. Case 3 Either ey or e2 is a front arc and the other is a back arc, and their capacities are allowed to change in the same direction. I will now construct a parametric capacity function c(-; •) for each of the above three cases. Since ex = and e2 = (k,l) are parallel, I can find simple paths px from s to i, P2 from s to k, p 3 from j to t and p 4 from / to t such that pt fl p 4 = 0 , p\ fl p 3 = 0 , p 2 n p 3 = 0 and p2 Pi p 4 = 0 . Let G" be the subgraph of G spanned by arcs (i, j), (£;, /) and paths px, p2, p 3 and p 4 . Assign very small constant capacities to arcs not in G' so that the total capacity of these arcs is less than 1. Consider a minimum cut, (X,X), in G. It disconnects t from s in G' as well as in G. Thus (X, X) contains a subset of arcs, A', which forms a cut set of arcs for G'. In the capacity function that I will construct, each arc in G' will be assigned an integer capacity greater than or equal to 1. Therefore, A' must be a minimum cut set of arcs for G'. Otherwise, I can augment a minimum cut in G' with all arcs in G\G' to form a new cut in G , whose capacity is smaller than the capacity of (X,X). If for two instances of the parameter, A x < A 2 , the corresponding minimum cuts are unique and cannot be- ordered, then the minimum cuts in G for Ai and A 2 cannot be ordered. Thus it suffices to show that unique minimum cuts cannot be ordered in G' for two values, A x and A 2 in A. In the following counter example, I assign constant values to capacities of arcs other than ei and e2 in G'. G' corresponding to Case 1 is illustrated in Figures 2.6 and 2.7. G' corresponding to Cases 2 and 3 is illustrated in Figures 2.8 and 2.9, respectively. The dotted lines represent paths in G'. Each such path may be empty. Let c(A;e) = oo for Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 39 each arc e in the paths represented by the dotted lines and for each A G JR. Values of c(X1;-) and c(A2; •) for other arcs in G' are as follows. In Case 1, if the capacities of ex and e2 are allowed to change in the same direction, then the values of c(Ai;-) and c(A2;-) are shown in Figure 2.6. If the capacities of e\ and e2 are allowed to change in opposite directions, then the values of c(X1; •) and c(A2; •) are shown in Figure 2.7. In Case 2 and Case 3, the values of c(Xi,-) and c(A2;-) are illustrated, respectively, in Figures 2.8 and 2.9. In each figure, part (1) corresponds to Ai and part (2) corresponds to A2. It can be seen that the direction of change in capacities of ex and e2 is consistent with the one set forth in the corresponding case. The dashed lines represent the minimum cuts. In each case, the unique minimum cuts for Ai and A2 are not ordered. This completes the "only if" part of the proof. • Proof of the "if" Part. Suppose ^(Ay,A+,A~) satisfies the hypothesis in the theorem. Consider an arbitrary parametric capacity function c(- ; •) € J-(AV, A+, A~). I will show that Condition B holds for an arbitrary pair of minimum cuts (X, X) G F*(Ai) and (Y, Y) G F*(A2), and by Corollary 2.8, it would then follow that a totally ordered selection of minimum cuts can be obtained by extending an arbitrary totally ordered sub-selection of minimum cuts. Let Nx = X n Y , N2 = X \ Y, N3 = Y \ X, N4 = X n Y. It will be convenient to assume that for every node i in Ni, there exists a path from s to i that is contained in Ni; and similarly, for every node j in N4 there exists a path from j to t that is contained in A^. (The motivation will be clear later.) This assumption does not hold in general. However, sets A^ { and N'4 with the desired property can be constructed from Nx, • • •, N4 as follows. Let A'] be the set of nodes in A^ such that if i G A^ { then there exists a path from s to i which is contained in Nx. Similarly, let N'A be the set of nodes in A^4 such that if i £ N'A then there exists a path from i to t which is contained in A V Let Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 40 N'2 = N2 U (Ni\N[) and N£ = N3\J (N^Nfi. Let X' = N{ U A^ and Y' = N[ U iV 3 . Clearly, A ' = X and (X ' , X1) = (X,X). The sets Nx through N 4 and A^ through N'A are illustrated in Figure 2.10. Observe that N!2\N2 = Nx\N[ and N^\N3 = AT-AA^-Claim 2 .1 There does not exist an arc (i,j) such thati £ A/] and j £ (Ni\N[). Similarly, there does not exist an arc (i,j) such that i £ N4\N[ and j £ N'A. Proof. Consider the first half of the claim. If an arc exists such that i £ A^ and j £ (Ni\N[), then by the definition of A^, there exists a path p from 5 to i that is contained in A^. Then the path < p, (i,j) > is contained in Nx too, and node j should also be in A^ , leading to a contradiction. The second half of the claim can be proved analogously. • N^\N2 = N,\N[ N'\N3 Figure 2.10: Partition of the node set Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 41 Claim 2.2 For each node i G A V there exists a path from s to i that is contained in N[. Similarly, for each node j G N4, there exists a path from j to t that is contained in N4. Proof. By the construction of N[, there exists a path p from s to i that is contained in A V If p is not contained in N[, it must contain a forward arc in either (X',X') or (Y',Y'). Since p is contained in A V it cannot contain an arc in (X,X)=(X',X'). Suppose p contains an arc in (Y',Y'). Since p is contained in A V i and j are also in A V Since Nx n Y' = N[ and Nx n F 7 = A^\N[, it follows that i G N[ and j G NX\N[. However, this contradicts Claim 2.1 and the first half of Claim 2.2 is established. Proof of the second half of the Claim 2.2 is similar. • Let A\ = ( A V N3) U ( A V N'4) U ( A V N4) and let A'2 = (N[, N£ U (N{, N'4) U ( A V N'A). Similarly, let Ax = (NUN3) U (NUN4) U (N2,N4) and let A2 = (NX,N2) U (NUN4) U (N3,N4). Clearly, A\ = (X',JC) \ ( A V N3) and A'2 = (Y^Y1) \ (N3, N2). Similarly, A, = (X,X)\(N2,N3)and A2 = (Y,Y)\{N3, N2). Claim 2.3 (1) ( A V A V C ( A V i V 2 ) , (ii) (N[,N3)C(Nl,N3)U(N1,N4)J (in) ( A V A ^ ) C (N2,N4) U {NUN4), (iv) (N3lN4)C(N3,N4), (v) (N[,NfiC(NuN4), (vi) Ai C Ax, (vii) A'2 C A2, Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 42 (viii) (N[,N{) C (NUN2) U (NUN3) U (NUN4) and (N^Nl) C (NUN4) U ( /V 2 , iV 4 )U ( iV3 , iV4) . Proof. To prove (i), consider an arc (i,j) G (A '^, A^). If j G N2, then since i G N[ C A^i, G (NUN2). Otherwise, j G N2\N2 = NX\N[, but this is impossible since it violates Claim 2.1. To prove (ii), suppose arc G (N[,N^). Since i e N[ C Nu i G # 1 . If j G N 3 , then G {Ni,N3). Otherwise, j G N^\N3 = N4\N^ C /V 4 , and (i, j ) G (NUN4). (iii) and (iv) can be proved analogously, (v) follows from the fact that A^ C Nx and N4 C AT4. (vi), (vii) and (viii) follow directly from (i) through (v). This completes the proof of Claim 2.3. • Recall that for two arbitrary sets of nodes / and J, c(A; / , J) denotes the total capacity of arcs in (I,J) = {{i,'j)\i G I,j G J} under the parameter A. Now let c'(\:I,J) be the total capacity of arcs in (/, J)\(N1,N4) under the parameter A. For example, c^A^ A^, N~) would be the total capacity of arcs in (N[, N^)\(Ni, N4) under the parameter A x . C l a i m 2.4 C ( A I ; A ; ) <C(\1;A1), (2.6) c(A 2; A'2) < c ( A 2 ; A 2 ) , (2.7) c'^-A'jKc'iX^Ay), (2.8) c'(\2;A'2)<c'(X2-A2). (2.9) Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 43 Proof. The proof follows from the fact that A[ C Au A'2 C A2, A[ \ (Nu N4) C A.MNuN,) and A'2\{NU N4) C A2\(NUN4). D C l a i m 2.5 Consider the following inequalities: c(A i ; AT{, iV 7 ) + c(A2; A J , tf4) < c(A i ; A x ) + c(A2; A 2 ) < c(Xi;X,X) + c(A2; Y , F ) , (2.10) c(A 2; ^ , / V 7 ) + c(A i ; iVj, N'4) < c(Ai; A i ) + c(A2; A2) < c(A i ; X , X ) + c(A2; Y, F ) , (2.11) c ' (Ai;A{, iVT)+c ' (A 2 ; ]Vl,^) < c'(Ai; Ai)+c'(A 2 ; A 2 ) < c'(X1;X,X)+c'(X2;Y,Y), (2.12) ^ ( A a s A T ^ / v D + c ' C A ! ; ^ , ^ ) < c'(Ai; Ai)+c'(A 2 ; A 2 ) < c'(Xy, X,X)+c'(X2;Y,Y). (2.13) Either (2.10) and (2.12) are valid, or (2.11) and (2.13) are valid. Proof. The second half of each inequality follows from A i C (X, X) and A 2 C (Y, Y). Thus I only need to prove the first half of the inequalities. By the definition of A i and A 2 , the capacity of each arc in (Ni,N4) appears exactly once in c(Aj; A i ) and once in c(A2; A2). Thus by the definition of c', c'(A i ; A i ) + c'(A2; A 2 ) + c(A l 5 Nu N4) + c(A2; Nu N4) = c{X1;Al) + c(A2; A 2 ) . (2.14) By Claim 2.3 (viii), the capacity of each arc in (NX,N4) appears at most once in c(X1;N[, N[) and at most once in c(A2; NA, N'A). Thus c(Xp,Nl,N[) + c(X2]WA,N>) < c'(Ai; N[,W{) + c\X2-WA, N'A) + c(A i ; Nu N4) + c(A2; NUN4), and c(A2;X^7vT) + c(Ai;7vI,^) < c'(A2; N[,N~[) + c'iX^Nl, N4) + c(A2; Nu N4) + c ( A l 5 NUN4). Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 44 If (2.12) is valid, then the first half of (2.10) can be obtained by summing the first half of (2.12), (2.14) and (2.15). Similarly, if (2.13) is valid, then the first half of (2.11) can be obtained by summing the first half of (2.13), (2.14) and (2.16). Thus I only need to show that either (2.12) or (2.13) is valid. To show the first half of (2.12) it is sufficient to establish that c'(A i ; N[, W{) + c'(X2;Nl, Ni) < c'(A i ; A i ) + c'(A2; A'2), (2.17) since the first half of (2.12) can be obtained by summing (2.8), (2.9) and (2.17). Similarly, to prove the first half of (2.13), it is sufficient to show that c ' ( A 2 ; A ^ ) + C ' ( A i ; A ^ A ^ ) < c'(\i; A[) + c'(\2; A'2). (2.18) This is done by contradiction. If both (2.17) and (2.18) are invalid, then c^X^N^ + c'iX.-MK) >c ' (A 1 ;A' 1 ) + c ' (A 2 ;A 2 ) and c'(A2; N{,Ni)+ c'iX^Nl, N'4) > c'(A i ; A[) + c'(A2; Ai,). Expanding the terms in the above two inequalities yields c'(A i ; N{, N'2) + c'(A i ; N[, N3) + c '(A i ; N{, N£+ c'(A2; N[, N>) + c'(A2; N!>, N'A) + c'(A2; iV 3 , N'A) > c'(A i ; N[, N£ + c'(A i ; N[, Nfi + c'(A i ; N', N'4)+ c'(X2; N[, N'2) + c'(X2; N[, N>) + c'(X2; iV 3 , A^) and c'(A2; N{, Nfi + c'(A2; N{, N£ + c'(A2; N[, N>)+ c'(A i ; N{, N$ + c'(A i ; Ni, N>) + c'(Xi;N', N>4) > c'(A i ; N[, N3) + J(\uNl, NI) + c'(A i ; N'2, N'4)+ c'(A2; N[, Nfi + c'(A2; N[, JV4) + c'(A2; N', iV 4). Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 45 Eliminating common terms in the above inequalities results in: c'(A2; N'2, N'4) - c '(A i ; JV2, > c'(A2; N[, iV2) - c'(A l 5 A^', A^) (2.19) and c'(A2; A{, A^) - c'(A i ; A{, A^) > c'(A2; A^, 7Y4) - c'(A l 5 A^, N4). (2.20) From (2.20), either (i), c'(A2; A ^ ) - c ' ( A i ; ^ , ^ ) < 0, or (ii), c'(X2;N[,N^) -c'(A i ; A{ ,A^) > 0. From (2.19), either (iii), c ' ( A 2 ; ^ , A ^ 2 ) - c'(A i ; A{, A^) < 0, or (iv), c'(A2; A 2 , N'4) — c'(Xi, N2, N^) > 0. Combining them together, one of the following four cases must be valid. C a s e 1 (i) and (iii) hold. That is, c'(A2; A^, N'4) - c'(A i ; A^, N4) < 0 and c'(A2; N[, Nfi -c ' ( A 1 ; ^ , ^ ) < 0 . C a s e 2 (ii) and (iii) hold. That is, c'(A2; N{, A 3 ) - c'(A i ; N[, N3) > 0 and c'(A2; N[, NT) -c ' ( A 1 ; A 1 , i V 2 ) < 0 . C a s e 3 (i) and (iv) hold. That is, c'(A2; A 3 , A^) - c'(A i ; A 3 , A^) < 0 and c'(A2; A^ , N'4) -d(Xl;N^N4)>0. C a s e 4 (ii) and (iv) hold. That is, c'(A2; A^', A^) - c'(A i ; N[, N^) > 0 and c'(A2; N'2, N'4) -c'{X1-N'2,N'4)>0. In Case 1, there must exist at least one arc (i,j) in (N[, N2) \ ( A 1 ; N4) such that c'(X2;i,j) - c'(Xi;i,j) < 0 and one arc (fc,/) in (A^, Ni)\(Nu N4) such that c'(X2;k,l) -c'(A i ;fc,/) < 0. By (i) and (iv) of Claim 2.3, (i, j ) G {Nu N2), (fc,/) G (N3, N4) and thus are both forward arcs in the minimum cut (Y,Y). From Lemma 2.13, I can find paths p 2 from s to fc and p 3 from j to t such that p 2 is contained in Y and p 3 and is contained in Y. Since i G A{, there exists a path px from s to i that is contained in A V Similarly, since / G A^ , there exists a path p4 from / to t that is contained in N4. Since p i , p 2 are Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 46 contained in Y and p3, p4 are contained in Y, p\, p2, P3 and p4 form a bypass between (i,j) and (A;,/), and (i,j) and ( f c , / ) are parallel. By assumption, arcs (i,j) and (k,l) must satisfy at least one of the conditions (i), (ii) or (iii) in Theorem 2.14. In (i), the two arcs must share a common head or a common tail. This is impossible since i E N[, k E N3, j E N2 and I E N4. In (ii), the capacities of these two arcs must change in opposite directions, which is not satisfied in Case 1. Now suppose (iii) is satisfied. If is both a front arc and a back arc, then p4 must contain j, but this is impossible since j E N'2 and p4 is contained in N4, and N2f\ N4 = 0 . If (fc, I) is both a front arc and a back arc, then pi must contain k, but this is also impossible since k E N3 and p\ is contained in In Case 2, there exists at least one arc (i,j) E (N[, N2)\(Ni, N4) such that c'(A 2 ; i,j) — c ' (Ai ;z , j ) < 0 and there exists at least one arc (fc,/) E (N[, N3)\(Ni, N4) such that c'(A 2;fc,/) — c'(A x;fc,/) > 0. Since i and fc are in N[, by Claim 2.2 there exist a path px from s to i and a path p2 from s to fc that are contained in N[ C Nx. By Claim 2.1, j cannot be in Ni\N{. Thus j E N2. If / E {N4\N'4), then (fc,/) E (NUN4), which is impossible. Thus by part (ii) of Claim 2.3, / E N3. Then E (Y,Y) and (fc,/) E (X,X). By Lemma 2.13, there exists a path p3 from j to t that is contained in Y, and similarly, there exists a path p4 from / to t that is contained in X. Since p\ and p2 are contained in JVi, p1f)p3 = 0 , p 2 H p 4 = 0 , pi f l p 4 = 0 and p 2 f l p 3 = 0 . Thus (i, j) and (fc, / ) are in parallel. By assumption, arcs (i,j) and ( f c , / ) must satisfy at least one of conditions (i), (ii) or (iii) in Theorem 2.14. Since the capacities on the two arcs change in opposite directions, (i) cannot be satisfied. In (ii), it is required that one of the arcs and (fc,/) be a front arc and the other be a back arc. If (i,j) is a front arc and (fc,/) is a back arc, then in the bypass pi, p2, p3 and p4, p3 must contain /. But this is impossible since p3 is contained in Y and / E N3 C Y. If is back arc and (fc,/) is a front arc, then p 4 must pass through j. This is also impossible since p4 is contained in X and j' E N2 C X. Condition Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 47 (iii) is not satisfied either. Indeed, if on the contrary (i,j) is both a front arc and a back arc, p4 must pass through node j, otherwise (k,l) must be both a front arc and a back arc and p3 must contain /. Neither case is possible. Case 3 is similar to Case 2 and Case 4 is similar to Case 1. This can be seen by exchanging the roles of Ajwith A 2 , X' with Y', and/or by letting the flow go from the sink node to the source node. Thus I have established a contradiction for each case, and either (2.17) or (2.18) must hold. This completes the proof of Claim 2.5. • Note that if I let x = (X,X), y = ( K , F ) , u = (N[,N[) and v = (W4,N'4), then the extreme parts of inequalities (2.10) and (2.11) coincide with (2.3) and (2.4) in Condition C. Furthermore, notice that u<c{X fl Y,X DY) and (X U Y,XU K ) ^ c u , thus Condition C holds. Since the lattice of cuts in the network G is finite, and a minimal and maximal minimum cut exist for each instance of A, it follows from the Weak Totally Ordered Selection Theorem that a totally ordered selection of minimum cuts can be obtained by extending a single minimum cut. To extend a finite totally ordered sub-selection of minimum cuts, I need the following claim. C l a i m 2.6 Either c(\1;Xr)Y,XnY) + c(\2;XUY,XUY) < c(A l 5 X,X) + c(A2; Y,Y) (2.21) or c(\l-XuY,X~lJY) + c(X2;XnY,XrTY) < c ( A i ; X , X ) + c ( A 2 ; y , F ) . (2.22) Proof. By the definition of c'(-; •), c ( A i ; (N[,N[) U ( M , N4)) < c'(A i ; Ni,Ni) + c (A i ; Nu N4), (2.23) c(A2; (Nl, U (iV 1 ; N4)) < c'(A2; 7v ,^ N4) + c(A2; NUN4), (2.24) Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 48 c'(A i ; X,X) + c(A i ; Nu N4) = c(A i ; X, X), (2.25) c'(\2;Y,Y) + c(\2;N1,N4) = c(\2;Y,Y). (2.26) From Claim 2.5, either (2.12) or (2.13) is valid. Suppose (2.12) is valid. Adding the inequality consisting of the two extreme parts of (2.12) and (2.23) through (2.26) yields c(A i ; (N[,N[) U (NUN4)) + c(A2; (N*, N'4) U (NUN4)) < c ( A i ; X , X ) + c (A 2 ;y ,F) . Thus the set of arcs (N[, N[) U (Ni,N4) is a minimum cut for Ai and the set of arcs (N4, NA) U (Ni,N4) is a minimum cut for A 2 , and (2.27) must be satisfied as an equation. Since (X,X) and (Y,Y) are minimum cuts for Ai and A 2 , respectively, (2.10) must be satisfied as an equation. Since the first half of (2.10) can be obtained by summing (2.8), (2.9), (2.14), (2.15) and (2.17), all of them must be satisfied as equations. Then (2.8) and (2.9) can be rewritten as: ' c(X1;A[\(NuN4)) = c(Xl;Al\(N1,N4)) (2.28) and c(A2; A'2\(NU N4)) = c(A2; A2\(NU N4)). (2.29) By parts (vi) and (vii) of Claim 2.3, A[\(NUNA) C A^N^N*) and A2\(NUN4) C A2\{NUN4). For (2.28) and (2.29) to hold, A[\(NUN4) = A1\(NUN4) (2.30) and A'2\(N1,N4) = A2\(N1,N4) (2.31) must be valid. We further claim that (Nu A Q \ (A^, N4) C (N[, W[) \ (Nu N4). Indeed, if, on the contrary, (Nu ~N^)\(NU N4) % (N[, W[)\(NU N4), then there exists an arc (i, j) £ {N^Jh) Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 49 such that, (i,j) i (NUN4) and £ (N[,N[). Since j G Nx C N[, i G (N^Ni). But then, i £ N'2 because (NX\N[) C N2. Since j £ 7V7, and (i, j ) £ ( A 1 ? A 4 ) , j must be either in A 2 or in A 3 . Therefore, there are only two possible cases: Case 1 j G N2 C A ^ . ' Then (ij) G (ATi, A 2 ) C A2 and G (N^NT). Thus £" A' 2 , contradicting (2.31). Case 2 j G N3 C A ^ . Then G (NUN3) C A x and («",?) G ( A 2 , A 3 ) . Thus (z,j) £ A i , contradicting (2.30). In both contradiction results; thus (A1,7V7)\(A1, N4) C (N[,N[)\{NUN4) and {N^WjCtNiNfiUiNuNt). (2.32) Similarly, one can show that ( A 4 , A 4 ) C ( A 7 ! , A i ) U (Nu N4). (2.33) By (2.27), (2.32) and (2.33), c(A1;A1,7vT) + c ( A 2 ; / v 4 , A 4 ) < c(Xx; X,X) + c(X2;Y,Y) and (2.21) is valid. By an analogous argument, if (2.13) in Claim 2.5 holds, then (2.22) in Claim 2.6 holds. This completes the proof for Claim 2.6. • I now return to the "if" part of the proof of Theorem 2.14. I have been assuming that A is countable. By Claim 2.6, Condition B is satisfied. Thus by Corollary 2.8, a finite Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 50 totally ordered sub-selection of minimum cuts can be extended into a complete one and the proof of Theorem 2.14 is complete. • The following corollary presents a necessary and sufficient condition for the existence of a totally ordered selection of minimum cuts for every capacity function in J-(AV). C O R O L L A R Y 2.15 Let Av be a set of arcs in a directed network G(N,A). Then a totally ordered selection of minimum cuts exists for any parametric capacity function c(-; •) in T(AV), if and only if for each pair of parallel arcs in Av, one arc must be both a front arc and a back arc. Proof. For any c(-; •) € F(Av), only arcs in Av can change in A, but the direction of change is unrestricted. Thus Jr(Av)=Jr(Av, A+, A~) where A+ = A~ — 0 . By The-orem 2.14, a totally ordered selection of minimum cuts exists for every c(-; •) in T(AV), if and only if each pair of parallel arcs in Av satisfy at least one of the conditions (i), (ii) or (iii) in Theorem 2.14. (i) and (ii) require the pair of parallel arcs to be in A+ or A~, which are empty sets in this setting. Thus (i) and (ii) cannot be satisfied and (iii) must hold. This completes the proof. • Next, I present some special cases of the class of parametric flow problems presented in Theorem 2.14. C O R O L L A R Y 2.16 Let Gx{N,A) be a capacitated network and let vx and v2 be two arbitrary nodes therein. Suppose capacities of all arcs terminating at v\ are either all nondecreasing functions of A or all nonincreasing functions of X, and similarly, capa-cities of all arcs originating from v2 are either all nondecreasing functions of X or all nonincreasing functions of X. Further, the capacities of the arcs on a directed path p Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 51 from vi to v2 are arbitrary positive functions of X, and capacities of all other arcs are constant. Let Av be the set of all variable arcs. If each pair of parallel arcs in Av either both originate from v2 or both terminate at v 1 ; then there exists a totally ordered selection of minimum cuts when X changes. Proof. From the assumptions, each pair of parallel arcs must share the same head or the same tail, and their capacities change in the same direction. By Theorem 2.14, a totally ordered selection of minimum cuts exists. • For the parametric flow problem studied by A U K (1993), if the capacities of arcs incident to a single node v are all nondecreasing functions of A, then a totally ordered selection of minimum cuts exists. This result is a special case of Corollary 2.16 as can be seen by identifying nodes vx and v2 and letting the path p from vx to v2 to be empty. For the same problem, if node v is allowed to have a capacity which changes in A, a totally ordered selection of minimum cuts still exists. Indeed, one can transform this node-and-arc capacitated network into an arc capacitated network by splitting node v into nodes vi and v2. A l l arcs terminating at v will now terminate at vx and all arcs originating from v will now originate from v2. A directed arc (v\,v2) is added which has the capacity of node v. This arc capacitated network is a special case of Corollary 2.16, since in this case the path p is the single arc (vi,v2). In the problem considered by A U K , a totally ordered selection of minimum cuts does not exist if we further allow capacities on nodes adjacent to v to change. A counter example is given in Figure 2.11. Therein, the capacities of nodes v2l u 3 , v4, v5 and v6 in a network G are paramefrically changed. Part (a) of Figure 2.11 shows the original node-and-arc capacitated network. Parts (b) and (c) of Figure 2.11 present the arc-capacitated equivalent of G, with two sets of capacities. The unique minimum cut in each case is Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 52 shown with dashed lines. Clearly, the minimum cuts under the two values of the parameter are not totally ordered. This is not surprising in light of Theorem 2.14, since arcs (u 3 , v'3) and (i>5, v'5) in Figure 2.11 are parallel to each other and the conditions in Theorem 2.14 are not satisfied. Carstensen (1983) constructed an example where an exponential number of minimum cuts exist which are not totally ordered when the capacities are parametrically changed. In Corollary 2.16, if one let v± be s and v2 be t, then the set of arcs terminating at v\ or originating from v2 will be empty, and the following result can be obtained. C O R O L L A R Y 2.17 Let p be a path from the source s to the sink t in a network G(N,A). Suppose no two arcs in p are parallel to each other. Then, when the capa-cities of arcs on p are parametrically changed, a totally ordered selection of minimum cuts exists In an s-t series-parallel network, no pairs of arcs on a path from 5 to f are parallel. Thus by Corollary 2.17, when the capacities on an s-t path are arbitrarily changed in such a network, a totally ordered selection of minimum cuts exists. 2.3 O r d e r i n g of M i n i m u m C u t s i n S o m e P a r a m e t r i c F l o w P r o b l e m s As a natural continuation of the study on ordered minimum cuts, the ordering of minimum cuts in some parametric maximum flow problems is studied in this section. M y study is motivated by the following observation. If minimum cuts are monotone increasing in the parameter, then an increasing sequence of minimum cuts can be identified which contains a minimum cut for each value of the parameter and, as the parameter increases, the minimum cut will move to the next cut in the sequence. As shown in the last section, in general, minimum cuts are not monotone with respect to the natural order of cuts induced by set inclusion. Can one, then, construct a partial order, other than the natural Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 53 v3 v6 (a) The original network (b) One set of capacities i (c) Another set of capacities Figure 2.11: A n example where totally ordered selections of minimum cuts does not exist Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 54 set inclusion order, with respect to which the minimum cut will be monotone increasing? I will address this question when the capacities of arcs are afflne functions of a single parameter A. Suppose that in a directed network G(N,A), the capacity of arc (i,j) is c(i,j) = co(i,j) + Ad(i , j ) , where A > 0 is a parameter. For simplicity of notation, let c = {c(i,j) : («, j ) G A) be the vector of arc capacities for G(N,A), let c 0 denote the vector (co(z, j) : G A), and let d denote the vector (d(i,j) : (i,j) G A). Then c = c 0 + Ad, and clearly the vectors of arc capacities form a ray. In the sequel, we assume that all vectors are columnar unless transposed. Therefore, for two vectors a and b, a r b denotes the inner product of a and b. For each cut (X,X) in G(N,A), let C(X) be the set of capacity vectors for which (X,X) is a minimum cut. I call each such set C(X) a region in the space of capacity vectors. Regions corresponding to different cuts may overlap, since more than one cut may be minimum for a fixed capacity vector. The region C(X) is defined by the following constraints: C(X) = { c I E (,-, j ) e(x,X) C(^J) ^ £(i,j)e(y,F) c(*>i) f o r a 1 1 c u t s ( r > F ) >• Since each constraint in the above definition is linear, C(X) is a polyhedron. The ray c = c 0 + Ad can be partitioned into non-overlapping intervals in, h, • • •, Ir such that an interval is farther away from the origin of the ray than /,-, and that each interval is contained in C(Xi). Then (X,-, Xi) is a minimum cut for capacity vectors in The ray thus induces a sequence of minimum cuts (X0,Xo), (Xi,Xi), • • •, (Xr,Xr). The next lemma shows that no two cuts in a sequence induced by a ray can be the same; i.e., if the ray leaves a region, it will never return to it. The validity of the lemma is due to the fact that each region C(X) is convex. If two points on a ray are in the same region, then the segment between these two points must also be in this region. Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 55 L E M M A 2.18 In an arbitrary sequence induced by a ray, no two cuts are the same. Since the cuts in the sequence of cuts generated by a ray do not repeat, one can define a partial order among the cuts that totally orders the cuts in this sequence. My next question then is, suppose there are many rays of capacity vectors, can one find a sequence of minimum cuts which "works" for all these rays? In other words, are the partial orders induced by different rays consistent with one another? To this end, I first introduce the notion of consistent sequences. Consider two sequences of cuts. I say that the two sequences are consistent if there do not exist two cuts (X{,X{) and (Xj.Xj) contained in both sequences, such that the former precedes the latter in one sequence whereas the opposite is true in the other sequence. The next theorem states that, if two rays are parallel to each other or if they share the same origin, then the sequences induced by the two rays are always consistent. T H E O R E M 2.19 Consider the following two rays: c = C i + A d i and c = c 2 + A d 2 . If Ci = c 2 or di = d2, then the sequences of cuts induced by these two rays are consistent. P r o o f . For each cut (X,X), I define an index vector e x in IR)A\ where A is the set of arcs in the network. A n element in ex is 1 if the corresponding arc is a forward arc in [X,X). A l l other elements in ex are 0. Thus e x T c is the capacity of (X, X). I will prove the theorem first for the case where C i = c 2 . Let c 0 — Ci = c 2 . Consider the two rays originating from c 0 with directions d i and d 2 . If the sequences induced by the two rays are inconsistent, then there exist A i < A 2 and A 3 < A 4 such that Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 56 • (X, X) is a minimum cut for Co + X\d\ and C o + A 4 d 2 but not for C o + A 2 d i or c 0 + A 3 d 2 , whereas • (Y,Y) is a minimum cut for C o + A 2 d i and c 0 + A 3 d 2 but not for C o + A i d ! or c 0 + A 4 d 2 . Then: . e x T ( c o + A 1 d 1 ) < e Y T ( c 0 + A 1 d 1 ) , (2.34) e x T ( c 0 + A 2 d 0 > e Y T ( c 0 + X2d1), (2.35) e x T ( c 0 + A 3 d 2 ) > e Y T ( c 0 + A 3 d 2 ) , (2.36) e x T ( c 0 + A 4 d 2 ) < e Y T ( c 0 + A 4 d 2 ) . (2.37) Subtracting Ai times (2.35) from A 2 times (2.34) yields: (A2 - A ! ) ( e x T - e Y r ) c 0 < 0. Since (A2 — A J > 0, ( e x T - e Y T ) c o < 0 . (2.38) Similarly, subtracting A 3 times (2.37) from A 4 times (2.36) yields: ( A 4 - A 3 ) ( e x T - e Y T ) c o > 0 . Since (A4 — A 3) > 0, ( e x T - e Y T ) c 0 > 0. (2.39) However, (2.38) and (2.39) lead to a contradiction. Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 57 Now I prove the theorem when d i = d 2 . I denote the common direction by d. If two inconsistent sequences exist, then there exist two cuts (X, X) and (Y,Y) such that (X, X) is minimum for c x + A ^ and c 2 + A 4 d but not for c x + A 2 d and c 2 + A 3 d , whereas the opposite is true for (Y,Y). Therefore, . e x T ( C l + A t d) < e Y T ( C l + A ^ ) , (2.40) e x T ( C l + A 2d) > e Y r ( C l + A 2 d) , (2.41) e x T ( c 2 + A 3d) > e Y T ( c 2 + A 3 d), (2.42) e x T ( c 2 + A 4d) < e Y r ( c 2 + A 4 d). (2.43) Subtracting inequality (2.41) from (2.40) yields: ( A 1 - A 2 ) ( e x r - e Y T ) d < 0 . Since Xi — A 2 < 0, ( e x T - e Y T ) d > 0. (2.44) Similarly, subtracting (2.43) from (2.42) yields: (A3 - A 4 ) ( e x T - e Y T ) d > 0; and since A 3 — A 4 < 0, ( e x T - e Y T ) d < 0. (2.45) Again, (2.44) and (2.45) lead to a contradiction. • Thus each ray in a collection of rays which share the same origin or direction, induces a sub-sequence of some fixed sequence of minimum cuts. However, if I allow both the Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 58 Figure 2.12: Two rays in opposite directions origin and the direction of a ray to change, the induced sequences will not be consistent. To see this, consider two rays in opposite directions, as illustrated in Figure 2.12, which induce two sequences that are reversed in order. Generally, in a sequence of cuts induced by a ray, the cuts are not totally ordered by the natural ordering of cuts. However, if one places some restrictions on the ray, then a sequence of minimum cuts can be found which are totally ordered. This is exactly the case when a ray satisfies Theorem 2.14. Formally, C O R O L L A R Y 2.20 Suppose c = C o + Ad is a ray in the space of the capacity vectors. Let Av be the set of arcs that correspond to non-zero elements in d. If no pairs of arcs in Av are parallel, then the ray will induce a sequence of minimum cuts that are totally ordered by the natural ordering of cuts. I further note that the collection of minimum cuts derived from merging the two totally ordered sequences of minimum cuts induced by two rays is in general, not totally ordered. Indeed, suppose that in one ray, capacities of arcs in Av change and in another ray, capacities of arcs in another set A'v change. Suppose that no parallel arcs exist in either Av or A'v, thus each ray induces a totally ordered sequence of minimum cuts. However, there may be a pair of parallel arcs in Av U A'v. So when the capacities change Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 59 from a point in one ray to a point in the other, capacities on a pair of parallel arcs may change. The minimum cuts corresponding to these two points may not be ordered. However, suppose that for each ray in a collection of rays, the set of arcs whose capacities change is a subset of Av, which does not contain any parallel arcs. Then, when the sequences induced by the different rays are merged, the resultant sequence is still totally ordered. When a ray induces a totally ordered sequence of cuts, there are at most n — 1 minimum cuts in the sequence, where n is the number of nodes in the network. Further recall that if one only changes the direction of a ray and not its point of origin, the sequences of minimum cuts induced are consistent. Thus the following theorem is valid: T H E O R E M 2.21 Let Av be a subset of arcs that does not contain parallel arcs and let 7Z be a collection of rays. Suppose among all points on the rays, only capacities of arcs in Av vary. If all the rays in 7Z share a common origin, then there exists a sequence of at most n — 1 totally ordered minimum cuts and each ray in 71 induces a consistent subsequence of it. Similarly, if all the rays have the same direction, I have T H E O R E M 2.22 Let Av be a subset of arcs that does not contain parallel arcs and let 71 be a collection of rays. Suppose among all points on the rays, only capacities of arcs in Av vary. If all the rays in 71 have the same direction, then there exists a sequence of at most n — 1 totally ordered minimum cuts and each ray in 7Z induces a consistent subsequence of it. If I allow both the origin and the direction of the rays to differ, then even when the change of capacities is restricted to arcs in Av, which does not contain parallel arcs, the rays will not induce consistent sequences. In fact, in the next example, I demonstrate that (n — 1)! inconsistent sequences may exist. Chapter 2. Totally Ordered Optimal Solutions and Parametric Maximum Flows 60 Let the network G(N, A) be a single path from s to t where A = {ei , e 2 , • • •, eq} and Av — A. Evidently, Av does not contain parallel arcs. Since each minimum cut in this network is composed of a single arc, a sequence of minimum cuts corresponds to a se-quence of arcs in the network. I wish to construct q\ rays such that the sequence induced by each ray corresponds to a different permutation of the q arcs in the network. Consider an arbitrary permutation of arcs (e^, en2, • • •, en ). I construct the ray that induces this sequence by letting c 0 = (TTI, TT2, • • • , 7r,) T and d = (4 1 _ , r i , , 4 1 - * 3 , •••, 4 1 - ^ ) T . In-stead of a formal proof, I use the following example to show that this ray indeed induces the sequence evi, e„2, • • •, eVq. Consider the permutation (e9, e 9 _ i , • • •, e2, ei). The ray corresponding to this permuta-tion has an origin c 0 = (<?, q — 1, • • • , 2 , 1 ) T and a direction d = (^7^7' 4 ^ 2 ' ' ' ' ' 4 ' When A is 0, the minimum cut is at eg, since the capacities at this point are c 0 = (q, q — 1, • • •, 2,1) T and eq has the smallest capacity. When A increases to 4, eq_i becomes 1 1 1 the new minimum cut, since the capacities are now (q + ^ ^ j , q—l + ^ T J , • • •, 3 - , 3, 5) . 1 1 . 1 . When A = 4*, the capacities are (q + -———, • • •, i + 3 + —, i + 2 - , i + 2, i + 4, • • •, 3 + 4 1 - 2 , 2 + 4 J _ 1 , 1 + Al)T and the minimum cut is at e 9 _j . Thus the sequence of minimum cuts induced by the ray is e9, e 9 _ i , • • •, e2, ex. C h a p t e r 3 A n E x t e n d e d S e l e c t i o n P r o b l e m 3.1 T h e E x t e n d e d S e l e c t i o n M o d e l In this chapter, I consider a problem faced by a decision maker, who has to choose a collection of facilities to acquire in order to undertake a subset of jobs. Each job requires a set of tasks, and each facility can perform a set of tasks. A job can be performed if the tasks it requires can be performed by the facilities that were acquired. I assume that the facilities are non-perishable. Thus a facility can be used by more than one job. A revenue is associated with each job and a cost is associated with each facility. The net return obtained by the decision maker is the total revenue from the jobs performed minus the total cost of the facilities acquired. The objective is to maximize the net return. Without loss of generality, I will assume that all job revenues and all facility costs are positive. I now present the notation used in the model. • T = {/l5 / 2 , • • •, / „ } is the set of possible facilities. • J = { j i , j 2 , • • • ,jm} is the set of potential jobs. • T = {^ i, t2, • • •, tk} is the set of tasks. • T(j) is the set of tasks required in order to perform job j, and for a subset of jobs J , T(J) is the set of tasks required to perform all jobs in J, where T(J) = U j G j T ( j ) . • T(f) is the set of tasks that can be performed by facility / , and for a subset of 61 Chapter 3. An Extended Selection Problem 62 facilities F, T(F) is the set of tasks that can be performed by the collection F , where T(F) = \JfeFT(f). • c(/) is the cost of facility / , and for a collection of facilities F , c(F) = YlfeFc(f) is the total cost of this collection. • r(j) is the revenue from a job j, and for a set of jobs J, r(J) = Y^jeJrU) 1 S the total revenue from jobs in J . I refer to (F , J) as a selection plan, where F is the collection of facilities acquired and J is the set of jobs performed. A selection plan (F , J) is feasible if the tasks required by J can be performed by the facilities in F . I will refer to this feasibility constraint as the sufficient tasks constraint. Similar to the original selection model, the objective in the ES model is to maximize the net return from a feasible selection plan. In an application of the original selection model, Eisner and Severance (1976) introduced a relative weight between the revenue and the cost terms, which reflects the conversion factor between a unit of storage and a unit of user value. Brumelle and Granot (1993) presented some monotonicity results with respect to this relative weight. Sometimes the facility costs may increase by roughly the same factor due to inflation, whereas the job revenues can only increase by a smaller factor due to competition. In such a case, a relative weight between the revenue and the cost terms is also helpful. To take account of situations like this, to be consistent with earlier papers mentioned above and for the sake of flexibility, I retain the relative weight between costs and revenues in the ES model. Thus the net return associated with a selection plan (F, J) is defined as g(F,J;X) = Ar(J) — c(F), where A is the relative weight on the revenue, and the extended selection (ES) model can be formally presented Chapter 3. An Extended Selection Problem 63 as ES : max JCJ,FCF subject to 9(F,J;X) T{J) C T{F). The original selection problem proposed by Rhys (1970) is a special case of the ES problem. That is, any instance of the original selection model can be formulated as an ES model. Indeed, for an arbitrary instance of the original selection model, let the set of facilities and the set of jobs in the ES model be the same as in the original model. Each facility / in the ES model performs a single task, which is / itself. A job j in the ES model requires a certain task if and only if it requires the corresponding facility in the original selection problem. Clearly, the original model coincides with this instance of the ES problem. The ES problem is generally NP-hard. Indeed, I claim that the set covering problem, which is known to be NP-hard, can be formulated as a special case of the ES problem. To show that, recall that the set covering problem is concerned with a finite ground set S, and a collection of subsets, C = {Di, D2, • • •, Dn}, of 5 , where C S for k — 1,2, • • •, n. The objective is to find a sub-collection, C , of C with minimum total cost, such that the union of subsets in C covers S. Formally, the set covering problem can be stated as where c(D) is the cost associated with subset D £ C. The above set covering problem can be formulated as a special case of the ES problem. Indeed, let the set of jobs in the ES problem be S, and assign a very large revenue LT to each job in S. Each job j £ S requires a single task, which is also denoted by j. Thus the ground set of tasks in the ES problem is also 5". The ground set of facilities is C. For minc-cc E D G C C(D) subject to I W D = S, Chapter 3. An Extended Selection Problem 64 each facility D £ C, the tasks performed by D are precisely the elements contained in D. The cost of facility D is c(D). Because the common revenue IT is very large, every job will be performed in any optimal selection plan. The set of tasks required is then the ground set S. The minimal cost collection of facilities that can perform S will be a minimum cost cover in the set covering problem. The ES problem is thus NP-hard. 3.2 S o m e V a r i a n t s of the E S M o d e l Even though the ES problem is NP-hard, under some natural assumptions it can be solved efficiently. Indeed, in some cases, the tasks performed by different facilities are nested. That is, a higher level facility can perform all the tasks that can be performed by a lower level one. For example, a 486 C P U performs all the tasks performed by a 386 C P U and a 387 co-processor. Such a nested structure also exists in a forest harvest scheduling problem, which will be formally presented in the next section. To further motivate the analysis for the rest of this section, let us briefly consider this problem. Therein, a network of roads is predetermined which forms a tree. The root of the tree is a saw mill and each other node is a block of forest to be harvested. In order to harvest a block, the road leading from the saw mill to the block must be ready. The value of a block varies over time, due to the growth of trees and the discount of value over time. Similarly, the cost of roads also varies in time. In order to maximize the present value of the net income, the decision maker must find an optimal schedule to build the roads and to harvest the blocks. In this problem, the availability of a leg of road / at a time period p can be considered as a task. The construction of a leg of road / at a period p can be considered as a facility which can be viewed as performing the tasks that correspond to the availability of leg I in time periods since p. If a leg of road is built earlier, then it is available in more periods and can perform more tasks. Thus a nested structure exists among the facilities. Chapter 3. An Extended Selection Problem 65 For the rest of this section, I will analyze two models in which facilities and jobs are nested, and in the next section, I will elaborate on the application of these models. 3.2.1 The E S M o d e l wi th Nested Facilities In the first model, I assume that the tasks performed by different facilities are either nested or disjoint. Formally, I make the following assumption: A S S U M P T I O N 3.1 (The Nested or Dis joint Facilities Assumpt ion) The sets of tasks, T(fi) and T(f2), performed by an arbitrary pair of facilities, fx and f2 in T, are either disjoint or contained in one another. By Assumption 3.1, the sets of tasks performed by an arbitrary pair of facilities fx and / 2 in T satisfy T(/ i ) D T(f2) = 0, or T{fx) C T( / 2 ) , or T(f2) C T{h). When the sets of tasks performed by an. arbitrary pair of facilities are either nested or disjoint, I say that the facilities are nested. I will refer to the ES model in which Assumption 3.1 holds as the Nested Facilities (NF) model. Observe that the original selection problem introduced by Rhys can still be viewed as a special case of the N F model. Indeed in the original selection problem, each facility performs a single task which is identical to itself. Thus the sets of tasks performed by different facilities are disjoint, and the Nested or Disjoint Facilities Assumption is satisfied. I define the following partial order among the facilities. For fx and f2 in J7, / i ^ / / 2 if T{fi) C T ( / 2 ) , i.e. f2 performs all the tasks performed by fx. If / i ^ / / 2 , then I say that f2 is a super-facility of / 1 ? and that / x is a sub-facility of f2. I say that a facility f\ is a parent of facility f2 if f2d/fi and there does not exist another facility / 3 such that i 2 Z ^ / / 3 ^ / / i - Since the tasks performed by the facilities are either disjoint or nested, the parent of a facility / , denoted by 7r(/), is unique. I add an artificial facility, / , which is a Chapter 3. An Extended Selection Problem 66 super-facility of every real facility. I assume that the cost of / is infinitely large and refer to this facility as the root facility. With the introduction of / , a unique parent exists for every real facility. A collection of facilities F is redundant if there exist a pair of facilities f\ and / 2 in F such that fiziffz- In an optimal selection plan, one would never select redundant facilities. Indeed, if fi and / 2 are both in the collection of facilities to be acquired, then f\ can be deleted without affecting the set of tasks that can be performed by the collection. A network, GF(T, Ap), in which the nodes are facilities in J7, can be constructed to represent the relationship among the facilities in an N F model. For ease of presentation, I will use the same notation to denote the facility and the corresponding node. A directed arc ( / 2 , / i ) is in Ap if and only if fi is the parent of f2. Clearly, Gp is a directed tree with / as its root and all the arcs directed towards the root. The following is an example of an N F model: E X A M P L E 3.1 Let J = {ji,J2,J3,ji} be the set of possible jobs, and let T = { / i , / 2 , /3,/4,/5,/6} be the set of possible facilities. Table 3.1 presents the revenues associated with the jobs and the tasks required by the jobs, and Table 3.2 presents the costs of the facilities and the tasks performed by them. Jobs Revenues Tasks Required Ji 12 ti, i-2 32 6 ^2 5 ^ 4 ; 1-5 is 9 8 tr Table 3.1: Jobs in Example 3.1 The tree Gp(J-, Ap) representing the facilities in the above example is shown in Fig-ure 3.13. Chapter 3. An Extended Selection Problem 67 Facilities Costs Tasks Performed fi 4 ti, t2 h 3 t3 fs 11 ti, t2, t3, t4 U 2 ^5) t§ h 14 ti, t2, t3, t4, t5, t6 h 13 ti f 0 all tasks Table 3.2: Facilities in Example 3.1 For each task t, r(t) denotes the least sophisticated facility that can perform task t. Formally, T{r(t)) C T( / ) for any facility / such that t £ T(f). For instance, in Example 3.1, T(£ 4 ) = f3, r(ti) = fi and r(t6) = f4. Without loss of generality, I assume that any task t performed by / can be performed by at least a real facility in J-. Therefore, there does not exist a task t such that.r(i) = / . I now show that the N F model can be solved by finding a minimum cut in a capacitated network G(V, A) constructed as follows. G(V, A) contains G F ( ^ 7 , Ap) as a subgraph, and can be constructed from Gp(J-,Ap) by adding the following nodes and arcs. For each job j in J, add a node to V, and denote it also by j. Further add a source node s to V. Thus V = TVJ J U {s}. For each job j , add a directed arc (s,j) with capacity Ar(j'), and for each job j and each task t required by j, add a directed arc (j , r(t)) with an infinite capacity. Recall that for each real facility / , arc ( / ,7r( / ) ) is already in Ap and is thus contained in A. Assign capacity c(f) to arc (/, 7r(/)). Finally, identify node / as the sink node of the network and for convenience, denote it by t. The network G(V, A) for Example 3.1 is shown in Figure 3.14 for A = 1. The capacities of the arcs are shown beside the arcs, and the dotted arcs have infinite capacities. Chapter 3. An Extended Selection Problem 68 fe Figure 3.13: The facility tree for Example 3.1 For a cut (X,X~) in G , let J(X) = X V\ J be the set of jobs in X, and let F(X) = { / G x n r\ M e x n .F such that That is, F(X) contains the undominated facilities in X. T H E O R E M 3.1 Let (X*,X~*) be a minimum cut in G{V,A) separating t from s. Then (F(X*),J(X*)) is an optimal selection plan for the NF model. Proof. The proof is done in two steps. In Step 1, I show that a cut in G(V,A) is associated with every feasible selection plan in which the collection of facilities is non-redundant, and the capacity of the cut is a constant minus the return associated with the selection plan. A collection of cuts is thus identified such that each cut in this collection is associated with a feasible (and non-redundant) selection plan. In Step 2, I show that if a cut is of minimum capacity, then it belongs to this collection of cuts. Thus a minimum cut will surely yield an optimal selection plan. Chapter 3. An Extended Selection Problem 69 s Figure 3.14: Network G for Example 3.1 Step 1 . Suppose (F,J) is a feasible selection plan. Assume that the collection F is non-redundant, and let F i = F U {/ e 7 I 3 / i € F such that fdjh}. That is, Fi consists of facilities in F and their sub-facilities. Let X = JU F\ U {s}. Since F is non-redundant, none of the super-facilities of any facility / G F is also in F, and by the construction of X, a facility / in F is not dominated by other facilities in X. Thus F(X) = F. The total capacity of forward arcs of the form (/, 7 r ( / ) ) in (X, X), where / is a facility, is the total cost of F. If a job j is not in J , then j £ I and (s, j) is a forward arc in (X, X). The total capacity of these arcs is Jljgj ^r(j) = X1Z — J2jej ^r(j), where IZ is the total revenue for all the jobs in J and is a constant. The only arcs not considered so far are those with infinite capacities, and I claim that no such arc can be Chapter 3. An Extended Selection Problem 70 a forward arc in (X, X). Indeed, suppose, on the contrary, that such an arc (j,f) is a forward arc in (X,X). Then / G X and there must exist a task t required by job j such that f=r(t). Since j € J and (F, J) is a feasible selection plan, there exists a facility fi € F such that / i can perform t. By the definition of r(-), fdffi- Since / i G F and fdffi, it follows from the definition of Fi and X, that / is contained in X, leading to a contradiction. Thus arcs with infinite capacities cannot be forward arcs in (X,X). The capacity of (X, X) is then equal to \1Z — g(F, J; A). Step 2. Consider a minimum cut (X*,X*). I first show that (F{X*),J(X*)) is a feasible selection plan. Let j be an arbitrary job in J(X*). Since (X, X) has a finite capacity, r(t) must also be in X* for each task t required by job j. Because Gp is a tree, there is a unique directed path from r(t) to the sink node t, and this path must cross (X*,X*) at least once. Let (/i,7r(/i)) be the last arc that crosses (X*,X*). fi is then undominated by any other facility in X*. By the definition of F(-), fx is in F(X*). fi is a super-facility of r(t) and can also perform t. Thus (F(X*), J(X*)) is a feasible selection plan. If a job j is not in X*, then arc (s, j) is a forward arc in (X*,X*), which has capacity Xr(j). For each facility / in F(X*), there is a forward arc ( / ,7r(/)) in (X*,X*) with capacity c(/). The above two types of arcs are the only forward arcs in (X*,X*). Thus the capacity of (X*,X*) is A7c - g(F, J; A). • For Example 3.1, the minimum cut is shown with a dashed line in Figure 3.14. The optimal collection of facilities is F(X*)={f3J4} and the optimal set of jobs is J{X*)={Juj2,33}. As previously discussed, the set covering problem can be viewed as a special instance of the ES problem. The fact that the N F model can be solved in polynomial time suggests that if the subsets in a set covering problem are either nested or disjoint, then the set Chapter 3. An Extended Selection Problem 71 covering problem can be solved easily. Indeed, as illustrated in the last section, one can transform such a set covering problem into an ES problem with nested facilities, which can then be solved as a minimum cut problem. 3.2.2 An ES Model with Nested Facilities and Jobs In the previous section, I assume that the facilities can be ordered in some sense. In many real world problems, jobs can also be naturally ordered. For example, an automobile service package may include a tune-up and an oil change. In this case, the service package is a super-job of either the oil change or the tune-up. In the forest harvest scheduling problem, jobs also appear to be naturally ordered. Therein, a job is the harvesting of a block b in time period p. Therefore, such a job requires the availability of all legs of road in the tree network from the saw mill to this block in time period p. However, a leg of road available at period p is also available at time periods after p. Therefore, I can view the job of harvesting block b in period p as if it requires the availability of all legs of road leading to it from period p and beyond. Thus harvesting a block earlier is a super-job of harvesting the same block later. Based on this observation, I present another model in this subsection, which incor-porates the additional assumption that a partial order -<j exists on the set of jobs J. If ji~5\jJ2, I call j 2 a super-job of j i , and j\ a sub-job of j2- If ji is an immediate super-job of j i , then j2 is called the parent of jx and be denoted by 7r(ji). In addition to the sufficient tasks constraint introduced earlier, I will assume that feasible selection plans satisfy the non-redundant jobs constraint. The non-redundant jobs constraint stipulates that in a feasible selection plan (F, J) , the set of jobs J cannot contain a pair of jobs that are ordered by -<j- This assumption is realistic because if a super-job provides all the utilities of a sub-job, one does not need to perform both of them. With the introduction of the non-redundant jobs constraint, the model can be Chapter 3. An Extended Selection Problem 72 formulated as follows. maxjcj,FCF g{F,J;X) ' subject to T(J) C T(F) ji iiidi for arbitrary jx,j2 6 J I retain the Nested or Disjoint Facilities Assumption introduced for the N F model and introduce the following additional assumptions. A S S U M P T I O N 3.2 ( T h e I n c r e a s i n g R e q u i r e m e n t s A s s u m p t i o n ) A super-job re-quires all the tasks required by its sub-jobs. That is, ifjidjJ2> then T(ji) C T(j2). A S S U M P T I O N 3.3 ( T h e N e s t e d or D i s j o i n t J o b s A s s u m p t i o n ) Let ji and j2 be an arbitrary pair of jobs. Then either ji and j2 are ordered by -<j, or they do not have a common sub-job. In view of the fact that a nested structure exists among both facilities and jobs, I will refer to this model as the Nested Facilities and Jobs (NFJ) model. The N F model can be viewed as a sub-class of the N F J model, since any instance of the N F model can be formulated as an instance of the N F J model. Indeed, for any instance of the N F model, one can assume that an empty partial order ~<j exists among the potential jobs, and under this empty partial order, no pairs of jobs are ordered. Thus the non-redundant jobs constraint and Assumptions 3.2 and 3.3 are all trivially satisfied. Although the N F model is a special case of the N F J model, I still present them separately since the two models can be solved using different techniques, which in themselves are interesting. Similar to the representation of nested facilities in the N F model, the partially ordered jobs can also be represented by a tree, denoted by Gj(J, Aj). I assume that a dummy Chapter 3. An Extended Selection Problem 73 job, denoted by j , exists which is a super-job of all other jobs. Job j is the root of Gj(J, Aj) and is referred to as the root job. With the introduction of this dummy job, a parent job ir(j) exists for each job j. Let Aj = {(j,7i(j)) | for each job j ^ j}. Since the Nested or Disjoint Facilities Assumption still holds in the N F J model, the facilities in this model can still be represented by the tree G F ^ , Ap), introduced in the last subsection. The following is an example of an N F J model. E X A M P L E 3.2 The facilities in this example are identical to those in Example 3.1 and are shown in Table 3.2. The jobs in this example are shown in Table 3.3. The partial order -<j among the jobs is shown in Figure 3.15, where two jobs j\ and j2 satisfy jidijJ2 if there exists a directed path from jy to j2. Jobs Revenues Tasks Required J i 12 ti, t2 32 24 ti, t2, t4, t5 33 6 u 34 9 t3, ^5 35 8 t5, ty 3 0 all tasks Table 3.3: Jobs in Example 3.2 Although the Nested or Disjoint Facilities Assumption and the Nested or Disjoint Jobs Assumption are very similar in appearance, they are quite different in nature. In the Nested or Disjoint Facilities Assumption, the nested or disjoint restriction is on the set of tasks performed by the facilities. That is, if the sets of tasks performed by two facilities are not contained in one another, then they must be disjoint. In the Nested or Disjoint Jobs Assumption however, the restriction is on the set of sub-jobs. That is, if two jobs are not ordered by dj, then they cannot share a common sub-job, but they can Chapter 3. An Extended Selection Problem 74 i i is J4 is . Figure 3.15: Tree of jobs in Example 3.2 require a common task. Consider for example, jobs j2 and j 4 in Example 3.2. They are not ordered by dj-, but they both require a common task t$. Notice that in Example 3.2 the revenue from j 4 is higher than that from j5. That is, the revenues are not necessarily monotone in jobs ordered by dj-If a job does not have any sub-jobs, then I call it an elementary job. We define the span, V ' ( i ) : °f a job 3 a s follows: If j is an elementary job, then ib(j) = 1. If j is the parent of other jobs, then tp{j) = J2jl-Tr(j1)=j ^ ( i i ) - Intuitively, ib(j) is the number of elementary sub-jobs of j , or, the number of leaf nodes in the subtree of Gj rooted at j. In Example 3.2, j\ is an elementary job, thus ip(ji)=l. 32 has two immediate sub-jobs, ji and j3. Thus ^(j2)=V'(ii)+V'(i3)=2. Similar to the N F model, the N F J model can also be solved as a minimum cut problem in a directed network G(V,A), constructed as follows. G(V,A) contains the trees of jobs and facilities, GF{7, Ap) and Gj(J~, Aj), as subgraphs. A l l the nodes and arcs in Gp and Gj remain in G, except that node j in Gj and node / in Gp are identified as a single node, which is denoted by t. A l l arcs terminating at either j or / will now terminate at t. Chapter 3. An Extended Selection Problem 75 Add a source node s to V, and for each elementary job j in J, add a directed arc (s, j). For each job j in J~, add a directed arc (j, r(t)) if j requires task t which, in turn, is not required by any of the sub-jobs of j. Let II be a large constant, whose magnitude will be clarified later. Assign capacity LT to arc (s, j) for each elementary job j, and for each job j 7^ j , assign capacity ip(j)H — Xr(j) to arc (j , 7r(j)). For each facility / ^ / , I assign the capacity c(/) to arc (/, 7 r ( / ) ) . Finally, I assign an infinite capacity to each arc (j,r(t)). The network G(V,A) for Example 3.2 with A=l is shown in Figure 3.16. Similar to Figure 3.14, the capacities in G are shown beside the arcs, and the arcs in dotted lines have infinite capacities. 211-24 s n-8 Figure 3.16: Network G for Example 3.2 For the N F J model, J(X) for a cut (X, X) in G is redefined to consist of the set of Chapter 3. An Extended Selection Problem 76 undominated jobs in X . That is, J ( X ) = {j e X f]J\ jBjx e X 0 J such that jdjji}-The definition for F(X) is the same as that for the N F model, i.e., F(X) = { / G x n F\ fifx G x n T such that /^//i}-T H E O R E M 3.2 Suppose (X*, X*) is a minimum cut separating t from s in the network G(V,A). Then, (F(X*), J(X*)) is an optimal selection plan. To prove the theorem, I need the following lemma. L E M M A 3.3 Let (X-, X) be a cut in G(V,A) with finite capacity. If for each job j in X, all the sub-jobs of j are also in X, and for each facility f in X, all the sub-facilities of f are also in X, then the capacity o / ( X , X ) is equal to KH — Ar( J (X) ) + c(F(X)), where K is the total number of elementary jobs in J. Proof. Since the capacity of (X, X) is finite, no arcs of the form (j',r(i)) can be forward arcs in ( X , X ) . Each job j G J(X) is not dominated by any other job in X. Thus ir(j) is in X, and is a forward arc in.(X,X) for every job j G J(X). On the other hand, consider an arbitrary forward arc of the form (j, n(j)) in (X,X). Clearly, 7r(j) G X. If j is dominated by another job j\ in X , then either or ir(j) is dominated by j j . By assumption, all sub-jobs of j\ are also in X , implying that TT(J) must also be in X , which leads to a contradiction. Thus j is not dominated by any other job in X and j G J(X). I have just shown that there is a one to one correspondence between forward arcs of the form (j,7r(j)) in (X , X ) and jobs in J(X). Similarly, there is a one to one correspondence between forward arcs of the form (/, 7 r ( / ) ) in (X , X ) and Chapter 3. An Extended Selection Problem 77 facilities in F(X). Finally, for each elementary job j G X, (s , j ) is a forward arc in (X, X). Thus the set of forward arcs in (X, X) is {(j^tiW € J(X)} U {(/,TT(/))|/ G F(X)} U {(s, j ) G A|j G X } . Let K~i be the number of elementary jobs that are either in J(X) or dominated by a job in J(X). I now show that the total capacity of arcs in G J(X)} is KiU — Ar( J (X)) . Recall that the capacity of an arc (j ,7r(j)) is ^>(j)II — Ar(j) , and is the number of elementary sub-jobs of j. Thus it suffices to show that those Kx elementary jobs are counted exactly once in J2j£j(x) ^(i) 1^- Clearly, each such elementary job is counted at least once. For two arbitrary jobs ji and j2 in J(X), by the definition of «/(•), ji and j2 do not dominate each another. The sets of elementary sub-jobs of j\ and j2 are then disjoint. Thus these elementary sub-jobs are never double counted. Next, consider the set of arcs {(s, j) G A\j G X}. For each arc (s, j) in this set, j is clearly an elementary job. The total capacity of arcs in this set is K2Tl, where K2 is the number of elementary jobs that are not in X. Since all sub-jobs of a job in X are also in X, these elementary jobs cannot be dominated by jobs in X. Thus K\ + K2 = K. Finally, the total capacity of arcs in {(/, 7r(/))|/ G F(X)} is c(F(X)). This completes the proof of Lemma 3.3. • I now return to the proof of Theorem 3.2. Proof of Theorem 3.2. The proof is in two steps, similar to those used in the proof of Theorem 3.1. The reader is referred to Theorem 3.1 for an outline of the proof. Step 1. In this step, I wish to show that for each feasible selection plan (F , J ) , a cut (X, X) in G can be constructed such that F = F ( X ) , J = J(X) and the capacity of (X,X) is ATI — g(F, J; A). Suppose (F, J) is a feasible selection plan with no redundant facilities or redundant jobs. Let J\ = {j G G J such that jdjji}, i-e-> J\ is the set Chapter 3. An Extended Selection Problem 78 of jobs in J and their sub-jobs. Similarly, let F i = { / G T \ 3fx £ F such that fdffi}, i.e., F i is the set of facilities in F and their sub-facilities. Let X = Fx U J\. From the construction of F\ and J\ and by the definition of F(-) and J(-), F — F(X) and J = J(X). Next I show that the capacity of (X,X) is finite. Consider an arc (j,r(t)), which has an infinite capacity. If j' £ X, then either j £ J , or j is dominated by some other job j\ in J. In the latter case, t is required by j\ due to the Increasing Requirements Assumption. Thus in either case, task t is required by jobs in J. Since (F, J) is feasible, either r(t) is in F or a super-facility of r(t) is in F , and in either case r(t) is in X. Thus (j,r(t)) cannot be a forward arc in (X, X) and the capacity of (X,X) is finite. By Lemma 3.3, the capacity of (X,X) is ATI - Xr(J(X)) + c(F(X)), or ATI - g(F, J ; A). Step 2. In this step, I wish to show that if (X*,X*) is a minimum cut, then (F(X*), J(X*)) is a feasible selection plan, and the capacity of (X*,X*) is ATI — g(F(X*),J(X*);\). First I show that if job j is in X*, then all its sub-jobs must also be in X*. Suppose otherwise, then I can find a minimal sub-job j\ of j such that j\ £ X* and if j\ has a sub-job j2, then j2 £ X* and (j2,ji) £ (X*,X*). If j i does not have such a sub-job, then ( s > i i ) G I only consider the first case, as the second case is similar. Let Ao = {(/,t) G A\f G F}, and let A = ( X * ,X* ) U A0 \ {(j 2 ,Ji)}. That is, ^ is the set of forward arcs in (X*,X*), with (j2,ji) therein being replaced by arcs in AQ. We will show that A is a cut set of arcs separating s and t, thought not necessarily a node partition cut. Moreover, observe that the capacity of arc (j2,ji) is ip(j2)Tl — \r(j2). For a large enough II, the capacity of (j2,ji) is strictly larger than the total capacity of arcs in AQ. For such a II, the total capacity of arcs in A is then strictly smaller than the capacity of (X*,X*). If the removal of arcs in A instead of those in (X*,X*) results with s and t being connected, then it must be due to the fact that arc (j2,ji) is not in A. Let p be a directed Chapter 3. An Extended Selection Problem 79 path from s to t that contains arc (J2,ji)- If the last arc in the path p is (/,t) for some facility / , then p is disconnected with the removal of arcs in A. Otherwise, the last arc in p is ( j3 , t ) for some job j3. Since there does not exist a task t such that r(t) = / , (j3 , t) must be an arc in the tree of jobs. Thus j3 is a super-job of j\ and must be on path p. Since j G X*, j is disconnected from t when arcs in (X* , X*) are removed. When arcs in A are removed instead of those in (X*,X*), ( j 2 , i i ) remains. But ( j 2 , J i ) i s n ° t o n a n Y path leading from j to t. Thus j is still not connected to t when arcs in A are removed, and p is still disconnected. Thus A is a cut set of arcs, which contradicts the fact that (X*,X*) is a minimum cut, since for a large enough II, the total capacity of arcs in A is strictly smaller than the capacity of (X*,X*). I can assume that all the sub-facilities of an arbitrary facility / G X* are also in X*. This can be shown as follows. Suppose there exists a sub-facility /j of / that is in X*. Since every path from fi to t must contain / , fi is already disconnected from t after the removal of forward arcs in (X*,X*). So if all nodes corresponding to sub-facilities of / are moved into X*, no new forward arc will be introduced into (X*,X*). Since all arc capacities are positive, and the original [X*,X*) is a minimum cut, this move cannot have eliminated any forward arc either. Since the facilities that are moved into X* are all dominated by other facilities in the original X*, F(X*) is not affected by this move either. So, as far as the facility selection problem is concerned, the original (X*,X*) is equivalent to the new one. Thus I can assume that in the original (X*,X*) all sub-facilities of any facility / in X* are also in X*. By Lemma 3.3, the capacity of (X*,X*) iSKIl-g(F(X*),J(X*);\). Next, I show that the collection F(X*) of facilities is sufficient to perform jobs in J(X*). Let j be an arbitrary job in J(X*). Suppose j requires a task t. I can find the smallest sub-job j\ of j that requires t. As I have shown before, jx must be in X*. By the construction of G, there exists an arc (ji,T(t)) in G which has an infinite capacity. Chapter 3. An Extended Selection Problem 80 Therefore, r{t) must also be in X*. Let / be the largest super-facility of r(i) that is in X*. Since / is undominated in X\ f £ F(X*). Thus F(X*) can perform t. Finally, because J(X*) is composed of undominated jobs in X*, two jobs that are ordered by dj cannot be both in J(X*). Thus the non-redundant jobs constraint is satisfied, and (F(X*), J(X*)) is a feasible selection plan. This completes Step 2. • It can be seen from the proof that I can choose If to be a number that is larger than the total cost of the facilities plus A times the largest revenue of a job. In Example 3.2, let 11=100. (Observe that LT is larger than 71, the sum of all facility costs, 47, plus the largest revenue, 24.) The minimum cut (X*,X*) is represented by the dashed line in Figure 3.16, and J(X*)={j2,j4}, F(X*)={f3,f4}. By Theorem 3.2, (F(X*),J(X*)) is an optimal selection plan for this example. 3.3 A p p l i c a t i o n s of the N F J m o d e l In this section, I first present an application of the N F J model to a network scheduling problem, which may arise in telecommunication, forest harvesting, and open pit mining. 3.3.1 A N e t w o r k S c h e d u l i n g P r o b l e m The network scheduling problem studied in this section is concerned with a forest struc-tured network. The root of each tree in the network represents a supplier of a single commodity, for example, cable T V programs. Other nodes represent potential consumers who may need the commodity, for example, townships that may need cable T V . Each arc in the network represents a potential link between two nodes, for example, a T V cable, and will be referred to as a leg. In order to make the commodity available to a client at a certain time period, all the legs on the unique path from the supplier to the client must be Chapter 3. An Extended Selection Problem 81 built by this time period. A cost is incurred from constructing a leg, which, due to time discounting, depends on the time period in which it is constructed. A one-time lump-sum revenue is associated with the initiation of service to a client at a certain time, which also varies over time. For example, this one-time revenue may be the present value of the total revenue from cable T V consumers in a township ever since it is made available. In order to maximize the net income, one needs an optimal schedule specifying the time periods in which to build the legs and to make the commodity available to the clients. I assume that the planning horizon consists of a finite number of discrete time periods, and I ignore the capacities of the links. For the cable T V example, since all viewers receive the same signals, the capacity of a T V cable does not depend on the number of users linked to it. Figure 3.17 illustrates an example where there are three clients, C\, C2 and C 3 , and a supplier S. Figure 3.17: Possible links from the suppliers to the consumers The network scheduling problem can be formulated as an N F J model constructed as follows. I associate a task t(l,p) with each leg / and each time period p. Such a task indicates that leg / is available at time period p. Further, I associate a facility f(l,p) with each leg / and each time period p, and such a facility indicates that leg / is constructed in time period p. The cost of f(l,p) is the present value of building / in period p. A facility f(l,p) can perform tasks i(/ ,p x) for px — p, p + 1, p + 2, • • •. Clearly, the collections of tasks performed by facilities corresponding to the same leg are nested, whereas the Chapter 3. An Extended Selection Problem 82 collections of tasks performed by facilities corresponding to different legs are disjoint. Thus the Nested or Disjoint Facilities Assumption is satisfied. Consider the network shown in Figure 3.17. For simplicity, I only consider two periods, i.e., p= l or 2. Table 3.4 presents the facilities in the model and the tasks performed by the facilities. Facilities Tasks Performed t(lul),t(lu2) * ( / i , 2 ) t ( / 2 , l ) , t(l2,2) f(k,2) t(k,2) / ( M ) t(l3,l),t(l3,2) /(/s,2) t(l3,2) Table 3.4: Facilities and tasks performed by them I associate a job j(b,p) with each consumer b and each time period p. If j(b,p) is performed, then the service is opened to b in time period p. The revenue from this job is the present value, v(b,p), of making the commodity available to b in time period p. Job j(b,p) requires task t(/,p 1) for each leg / on the path from the supplier to b, and for each Pi > P- That is, in order to make the commodity available to b in time p, each leg on the path from the supplier must be available at time p. Of course, if the leg is available at time p, it will be available in each period thereafter. The jobs in the above example are presented in Table 3.5. I define the following partial order among the jobs. For each consumer 6, j(b,Pi)dj j(b,p2) if p2 < Pi- Clearly, a job corresponding to making the commodity available earlier requires more tasks. Jobs associated with the same consumer are totally ordered, whereas jobs associated with different consumers are never ordered by dj- Thus two jobs that are not ordered by dj can never share a common sub-job and the Nested or Disjoint Jobs Chapter 3. An Extended Selection Problem 83 Jobs Tasks Required i (Ci , i ) * ( Z i , l ) , i ( / i , 2 ) r(Z l s2) J(C 2 ,1) i (Z 2 , l ) , t(/ 2,2), ^(^,2) i ( C 2 , 2 ) t(l2,2), t(lu2) i(c3,i) t(l3,l),t{lul),t(l3,2),t(k,2) J(C 3 ,2) t{l3,2),t(lu2) Table 3.5: Jobs and tasks required Assumption holds. Note that jobs associated with the same client are totally ordered, and two ordered jobs are never contained in the same feasible selection plan. This prevents opening service to the same client twice. It is not hard to see that a feasible selection plan in the above N F J model corresponds to a feasible schedule, and thus the network scheduling problem can be solved as a minimum cut problem in a directed network. This network contains 0(nt) nodes and O(Dnt) arcs, where n is the number of consumers, t is the number of periods in the planning horizon and D is the maximum depth of the tree of links. I can slightly modify the network and reduce the number of arcs therein to 0(nt). The modified network is the same as the original network except that the arcs with infinite capacities are different. Therein, the set of arcs with infinite capacities consists of the following arcs: For each job j(b,p), there is an arc from node j(b,p) to node f(l,p), where I is the leg terminating at b. For each pair of nodes f(l,p) and f(l',p), there is an arc from f(l,p) to f(l',p) if leg /' immediately precedes /. The modified network has (2nt + 2) nodes and (Ant + n) arcs and is smaller than the original one. The original and the modified networks for the example displayed in Figure 3.17 are shown in Figures 3.18 and 3.19, respectively. The modified network is equivalent to the original one as far as maximum flow and minimum cut are concerned, since from the original network Chapter 3. An Extended Selection Problem 84 Jobs Tools p = 2 p = 1 p = 2 p = 1 Figure 3.18: The original network Jobs Tools p = 2 p = l p = 2 p = I Figure 3.19: The modified network Chapter 3. An Extended Selection Problem 85 to the modified network, I merely replace some arcs of infinite capacities with paths of infinite capacities. For example, arc (u,v) in Figure 3.18 is replaced by path < u,w,v > in Figure 3.19. 3.3.2 A F o r e s t H a r v e s t S c h e d u l i n g P r o b l e m In logging operations, a watershed is usually divided into smaller blocks, which are con-tiguous areas and in which the tree species and their maturity are similar. In order to harvest a block, roads must be built from a saw mill to this block. The set of possible routes are predetermined, mainly by the landscape of the area. The possible routes can be represented by a network in which each node is either a saw mill or a block of forest, and each arc is a segment of road between the two nodes. These segments of road are called legs. I assume that capacities of the roads and of the saw mills are large enough so that these capacities can be ignored. With this assumption, it is unnecessary to deliver logs from a block to more than one saw mill or to build multiple roads from a block to a saw mill . Thus I can assume that the network of roads is a forest, with a saw mill as the root of each tree of roads therein. Schedules must be made to determine which blocks should be cut and if so, at which time period. Each time period is usually 10 years, and the planning time horizon can be as long as 12 periods, or 120 years. A good harvest schedule must take into account the growth of trees, the cost of building the roads, and environmental factors. Naturally, it would be unwise to cut a block of trees when it is still in a rapidly growing stage. Further, due to the lengthy planning horizon, the value of harvested wood and the cost of constructing the roads must be discounted to their present values. I assume that the present value of revenue from harvesting each block of forest in each time period is known, and so is the cost in present value of building each leg of road in each time period. The problem is to find a forest-harvest and road-construction schedule Chapter 3. An Extended Selection Problem 86 that yields the maximum net present income. A schedule is feasible if the roads from a saw mill to each block is available by the time the block is to be harvested. Since the planning horizon is usually no longer than the growth cycle of a tree, a block cannot be harvested twice within the planning horizon. The above scheduling problem is a special case of the network scheduling problem discussed in Subsection 3.3.1. Indeed, harvesting a block in a certain time period in the former problem corresponds to making the commodity available to a consumer in this period in the latter problem. Thus this scheduling problem can be formulated as a minimum cut problem in the modified network presented in Subsection 3.3.1. In real world logging operations, usually additional constraints must be considered. For example, adjacency constraints have been introduced recently in forestry legislations. They require that after a block is harvested, its neighboring blocks cannot be harvested until a certain green-up period has elapsed. With the introduction of these constraints, the problem becomes NP-hard. Indeed, any instance of the stable set problem can be formulated as a forest harvest scheduling problem with adjacency constraints in which the planning horizon is only one period. 3 . 3 . 3 A n O p e n P i t M i n i n g S c h e d u l i n g P r o b l e m In open pit mining, a body of ore deposit and waste is divided into blocks. Due to the difference in mineral concentration (grade), each block has a different value, which may change over time due to time discount and variations in ore price. Let Cf,p be the present value of the cost to remove block b in period p, and let rbp be the present value of the revenue from processing and selling block b in period p. To limit the slope of the pit, blocks in a cone above b must be excavated no later than the time period in which block b is excavated. I call the blocks in the cone above b the predecessors of b. For example, in Figure 3.20, blocks 1, 2 and 3 must be excavated no later than block 5, as indicated by the Chapter 3. An Extended Selection Problem 87 arrows. Due to the lengthy planning horizon, excavation of the blocks must be properly scheduled in order to maximize the net present value. In real mining operations, such a schedule must take account of excavation capacity, proper mix of ore grades, and so on. With the introduction of these constraints, the problem is NP-hard. However, when the latter constraints are ignored, the problem can be formulated as an N F J problem. Indeed, for each block b and each time period p, job j(b,p) corresponds to processing and selling block b in time period p, facility f(b,p) corresponds to excavating block b in time period p, and task t(b,p) means that block b is already excavated in period p. Job j(b,p) yields a revenue r^p and requires tasks t(bi,px) for each pr > p and for each predecessor 61 of b. Facility f(b,p) costs Q , p and can perform tasks t(b,px) for px > p. Thus, the open pit mining scheduling problem is a special case of the N F J model. In the above problem, I assume that a mining company can remove a block of material in one period and process it in a later period. If a block must be processed in the same period it is excavated, then the problem cannot be formulated as an N F J model. Dagdelen (1979) proposed a method to solve this latter version of the open pit mining scheduling problem by finding a minimum cut in a directed network. (See also Dagdelen 1992.) Based on similar ideas used in solving the N F J model, I construct an alternative network to solve this version of the problem. My alternative network contains the same number of nodes but fewer arcs compared to Dagdelen's network. I now briefly describe the method proposed by Dagdelen. Since excavation and pro-cessing must occur in the same period, I denote by Ubp = r^v — Cbp the present value of the profit from excavating block b in period p. For each block b and each time period p, let Xbp = 1 if block b is excavated in period p and 0 if it is not, let tojp = Xb\ + Xb2 + • • • + Xbp, Ubp — Ubp — Ub,p+i for p = 1,2, • • •, L — 1 and let un = UbL, where L is the last period. Dagdelen's network contains a node for each block b and each period p, a source node s and a sink node t. For each period p, if block bx is an immediate predecessor of b, then Chapter 3. An Extended Selection Problem 88 there is an arc (v%,vl) in G with an infinite capacity. For each block b and each period p = 1,2, • • •, L — 1, there is an arc (u^, v%+1) in G with an infinite capacity. For each node vl, if U(,p > 0, then there is an arc (s, vl) in G with capacity U(,p, otherwise, there is an arc {yl, t) with capacity \u~hp\- A n optimal schedule for the open pit mining problem is derived from a minimum cut (X, X) in G by letting Wf,p = 0 for each vl £ X and wbp — 1 for each vl £ X. To illustrate this network, consider a body of ore deposit shown in Figure 3.21, which is divided into three blocks. Suppose that the planning horizon consists of three time periods. The corresponding network G is shown in Figure 3.22. <rfc> <) • 4 5 6 Figure 3.20: Predecessors in open pit mining 1 2 3 Figure 3.21: A n example of ore body My sparser network G' contains a node vl for each block b and each time period p, a source node s and a sink node t. For each time period p, if 61 is an immediate predecessor of 6, then G' contains an arc (vl,vl) with an infinite capacity. For each block b and each Chapter 3. An Extended Selection Problem 89 Chapter 3. An Extended Selection Problem 90 period p = 1, • • •, L — 1, G' contains an arc {vbl v b + 1 ) with capacity LT — ubjn where FI is a constant that is larger than maxbiP{ubp}. Further for each block b, G' contains arc (vb,t) with capacity LT — ubL and arc (s,vb) with capacity IT. The network G' corresponding to the example shown in Figure 3.21, again with three time periods, is given in Figure 3.23. A n optimal schedule for the open pit mining problem is derived from a minimum cut, (X,X), in G' as follows. If arc (vb,vb+1) (or when p = L, arc (vb,t)) is a forward arc in (X,X), then block b should be excavated in time period p. If arc (s,vb) is a forward arc in (X,X), then block b should never be excavated. I will not formally prove that the schedule thus obtained is optimal, but the validity of this result can be seen to follow from the following two arguments. (1) For each block b, let P(b) be the path (s, v\, u 2 , • • •, vb , t). If a cut (X, X) is a minimum cut, then it contains exactly one forward arc from each P(b). Thus the capacity of any cut (X,X) with a finite capacity is n i l minus the payoff from the schedule, where n is the number of blocks in the ore deposit. (2) For any cut (X,X) with a finite capacity, if node vb is in X, then vbi must also be in X for any predecessor bx of b. This is because there is a path from vb to with an infinite capacity. Therefore, if a block b is excavated in time period p, its predecessors must be excavated no later than p. For a problem with n blocks r precedence relations1 and t periods, my network has nt — 2n fewer arcs than in the original network, which contains rt + 2nt — n arcs. 3.4 Some Qualitative Properties In this section, I derive some qualitative properties of optimal solutions in parametric N F and N F J models. As shown in Subsection 3.2.2, the N F model is a special case of 1 A precedence relation is a pair of blocks such that one immediately preceeds the other. Chapter 3. An Extended Selection Problem 91 the N F J model. Therefore, whenever a result in this section holds for both the N F and N F J models, I only prove it for the latter model. My study in this section uses lattice programming methodology. The reader is referred to Section 1.2 and Subsection 2.1.1 for a detailed discussion on related research in lattice programming. In the parametric optimization problems considered in this section, C will be the set of all selection plans and g(x, A) will be the net return function. Thus in all these problems, C is compact and g(x,X) is lower semi-continuous, although I will not verify this point to avoid unnecessary mathematical details. Therefore, in the sequel, whenever the set of optimal solutions is ascending (respectively, descending), an increasing (respectively, decreasing) selection of optimal solutions exists. To present my monotonicity results, I first introduce the following partial orders. In the N F J model, for two subsets of jobs Ji and J2, JidjJi if f ° r every job jx G J 1 ; there exists a job j2 G </2 such that jidijjv- In both the N F J and N F models, for two subsets of facilities F i and F 2 , F i ^ p F 2 if for every facility fiE.Fi, there exists a facility / 2 G F 2 such that / i ^ / / 2 . In the N F J model, for each elementary job j, an artificial null job j(j) is added, which has no utility to the customer and yields no revenue. I assume that j_(j)dijj is valid. If an elementary job j is not in a collection of jobs J, and neither are super-jobs of j , then I assume that j(j) is in J. When an N F model is viewed as a special case of the N F J model, J i ^ j J 2 if and only if Jx C J2. Similarly, an artificial null facility / ( / ) can be added which performs no tasks and has zero cost. I assume that f(f)diff is valid. If an elementary facility / is not in a collection of facilities F , and neither are super-facilities of / , then I assume that / ( / ) is in F . The following propositions are needed to prove the main results in this section. P R O P O S I T I O N 3.4 In the NF or NFJ models, let f be an arbitrary facility in T, Chapter 3. An Extended Selection Problem 92 and let F be an arbitrary non-redundant collection of facilities. Then, F must contain at least one facility that is totally ordered with f. Proof. If F does not contain a real facility that is totally ordered with / , then all the null sub-facilities of / will be contained in F. Each such null facility is totally ordered with / . • P R O P O S I T I O N 3.5 In the NF or NFJ models, let j be an arbitrary job in J, and let J be an arbitrary non-redundant collection of facilities. Then, J must contain at least one job that is totally ordered with j. Proof. Similar to the proof of Proposition 3.4 and thus omitted. • The following proposition considers the union and intersection of two sets of facilities. Recall that a chain in a partially ordered set is a totally ordered subset thereof. P R O P O S I T I O N 3.6 In the NF or NFJ models, let Fx and F 2 be two non-redundant collections of facilities. Then the following hold. (i) A chain in F\ U F2 contains at most two facilities, one from F\ and the other from F2. (ii) A chain in Fx U F2 contains a single facility fx, if and only if fx is in both Fx and F2. Proof. Since the collections Fx and F2 are non-redundant, no two facilities in Fx can be totally ordered, and the same is valid for F 2 . Thus (i) holds. To show (ii), suppose fx is the unique facility in a maximal chain in Fx U F 2 and, without loss of generality, assume fx G Fx. By Proposition 3.4, F 2 contains a facility f2 that is totally ordered with Chapter 3. An Extended Selection Problem 93 fi- If / 2 / / i , then fi eannot be a maximal chain in F\ U F2. Thus fi £ F2. On the other hand, if f\ £ Fx fl F2, then by the non-redundancy of Fi and F2, fi must be the unique element in a chain containing fx. pj Similarly, the following proposition is valid. P R O P O S I T I O N 3.7 In the NF or NFJ models, let Jx and J2 be two non-redundant collections of jobs. Then the following hold. (i) A chain of jobs in Jx U J2 contains at most two jobs, one from Jx and the other from J2. (ii) A maximal chain in Jx U J2 contains a single job jx, if and only if ji is in both Jx and J2. Let Fx A F2 and Fx V F2 be, respectively, the supremum and infimum of two collections of facilities Fx and F2 with respect to the -<F order among the collections of facilities. Similarly, let Ji A J2 and J\ V J2 be, respectively, the supremum and infimum of two collections of jobs Ji and J2 with respect to the -<J order among the collections of jobs. In view of Proposition 3.6, Fi A F2 can be constructed by picking the lower facility in each maximal chain in Fi U F2. If a maximal chain contains only one facility, then Fi A F2 contains this facility. Similarly, Fi V F2 can be constructed by picking the higher facility in each maximal chain in Fi U F2. Again, if a maximal chain contains only one facility, then Fi V F2 contains this facility. Similarly, J i A J2 can be constructed by picking the lower job in each maximal chain in Ji U J2 and Ji V J2 can be constructed by picking the higher job in each maximal chain. P R O P O S I T I O N 3.8 In the NF or NFJ models, let Fx and F2 be two non-redundant collections of facilities. Then, Chapter 3. An Extended Selection Problem 94 (i) FlUF2 = (Fx V F2) U (Fx A F2), and Fx n F2 = (Fx V F2) n (Fi A F 2), fnj c(Fi) + c(F 2) = c(Fi A F2) + c(Fi V F 2 ) , i.e., the cost is modular in the collection of facilities, (iii) T(F1) U T(F2) = T(FX V F2) and T(FX) n T(F 2 ) = T{FX A F 2 ) . Proof. Part (i) of the proposition follows from the construction of Fx A F 2 and F i V F 2 . In constructing Fi A F 2 or Fx V F 2 , one only need to use facilities in Fx U F 2 . Furthermore, any facility in F i U F 2 will either go into Fx A F 2 , if it is the lower facility in a maximal chain, or go into Fx V F 2 , if it is the higher facility in a maximal chain. Thus Fx U F 2 = (Fi V F 2 ) U (Fi A F 2 ) . If / is a maximal chain by itself in Fx U F 2 , then / is in both F x fl F 2 and (Fi V F 2 ) D (Fx A F 2 ) , otherwise it is in neither of them. Thus Fx n F 2 = (F x V F 2 ) n (Fx A F 2 ) . Part (ii) of the proposition follows directly from part (i). To prove part (iii), consider t in T(FX) U T(F2). Without loss of generality, assume that t e T(F1). Since T(FX) C T(Fi V F 2 ) , < G T(FX V F 2 ) . On the other hand, if t G T(FX V F 2 ) , then there exists a facility / in Fx V F 2 that can perform t. From the construction of Fi V F 2 , / is either in Fx or in F 2 . Thus t G T(Fi) U F ( F 2 ) . The second half of part (iii) can be proved similarly. • P R O P O S I T I O N 3.9 In the NF or NFJ models, let Jx and J2 be two non-redundant collections of jobs. Then (i) J i U J2 = (Ji V J2) U (Ji A J2), and JXC\J2 = (Jx V J2) D (Ji A J 2 ) , CnJ r(J i) + r(J2) = r ( J x A J 2) + r ( J i V J 2 ) , i.e., the revenue is modular in the collection of jobs, (iii) T(Ji) U T(J2) = T( J i V J 2) and T(Ji) n T{J2) D T(JX A J 2 ) . Chapter 3. An Extended Selection Problem 95 Proof. The proof of part (i) is similar to that of part (i) in Proposition 3.8 and is thus omitted. Part (ii) follows directly from part (i). To show the first half of part (iii), consider a task t £ T(JX) U T(J2). Without loss of generality, assume t £ T(J\). Suppose t is required by a job j in Jx. By the construction of J\ V J 2 , either j is in J i V J 2 , or there exists another job ji such that jdjji and ji is in Ji V J2. Since j\ also requires t, in either case, t £ T ( J i V J2). On the other hand, suppose t £ T(J\ V J2). Then it is required by a job j £ J\ V J2. Since each job in J i V J 2 is either in J\ or in «/2, without loss of generality, I can assume that j is in Jx. Then t is in T(Jx), and the first half of part (iii) is established. To prove the second half of part (iii), consider a task t £ T(J\ A J 2 ) . Then there exists a j °b j £ «/i A J 2 such that i is required by j . By the construction of J\ A J 2 , j belongs to either or J 2 . Without loss of generality, assume that j £ Jx. Then there exists a job ji £ ^2 such that jdjji, and therefore, both j and j\ require t. Thus t £ T(J i ) fl T(J2). • In general, D T(J2) C T ( J i A J2) does not hold. Indeed, consider the example where J i = { j i , j 4 } , J"2 = {J2, J3}, jidjJ2, J 3 ^ i j 4 , T(ji) = T( j 3 ) = 0, and T(j2) = T(j4) = {t}. Clearly, J i A J 2 = { j i , j3} and T(Jj A J2) = 0. However, r ( J i ) D T(J2) = {*}• For a given collection of facilities F, let J*(F) be the (unique) set of jobs that can be performed by F and which yields the largest revenue. Similarly, the least expensive collection of facilities that can perform a set of jobs J is denoted by F*(J). In the N F J model, J*(F) and F*(J) can be obtained easily. P R O P O S I T I O N 3.10 In the NF or NFJ models, c(F*(J)) is submodular in J with respect to the -<j order. Chapter 3. An Extended Selection Problem 96 Proof. Consider two sets of jobs J\ and J 2 . T(Ji A J2) C T(J i ) n T(J 2 ) by Proposition 3.9(iii) C T(F*(J i ) ) fi T(F*(J2)) by the feasibility of the selection plans = T(F*( J i ) A F*(J 2)) by Proposition 3.8(iii), and T(JX V J 2) = T(J i) U T(J 2 ) by Proposition 3.9(iii) C T(F*(Ji)) U T(F*(J2)) by the feasibility of the selection plans = T(F*(J i ) V F*(J 2)) by Proposition 3.8(iii). Thus F*(Ji) A F*(J2) can perform J x A J 2 , and since F*(Jx A J 2) is the least expensive collection of facilities that can perform J i A J 2 , c(F*(J1 A J 2)) < c(F*(Ji) A F*(J2)). Similarly, c(F*(Jl V J2)) < c(F*(J1) V F*(J2)). The last two inequalities imply: c{F*(Ji A J 2)) + c(F*(Ji V J 2)) < c ( F * ( J 1 ) A F * ( J 2 ) ) + C (F*(J 1 ) V F * ( J 2 ) ) = c(F*(Ji)) + c(F*(J 2)) by Proposition 3.8(ii). P R O P O S I T I O N 3.11 In the NF or NFJ models, r(J*(F)) is supermodular in F with respect to the order. Proof. Consider two collections of facilities Fx and F2. T(Fx A F2) = T(Fx) fi T(F2) by Proposition 3.8(iii) D T(J*(Fi)) n T(J*(F2)) by the feasibility of the selection plans D T(J*(Fi) A J*{F2)) by Proposition 3.9(iii), and T(Fx V F2) = T(F1) U T(F 2 ) by Proposition 3.8(iii) D T(J*(Fi)) n T{J*(F2)) by the feasibility of the selection plans = T(J*(F!) A J*(F 2)) by Proposition 3.9(iii). Chapter 3. An Extended Selection Problem 97 Thus J*{Fi) A J*(F2) can be performed by Fx A F2 and by the definition of r{r(Fx A F2)) > r{J*{Fx) A J\F2)). Similarly, r ( J * ( F 1 V F 2)) > r{J*{Fy) V J*(F 2 ) ) . The last two inequalities imply: r ( J * ( F i AF2)) + r{J*(F1 V F 2)) > r(J*(Fi) A J*(F 2)) + r ( J * ( i ? 1 ) V J*(F2)) = r(J*(F 1)) + r(J*(F 2 )) by Proposition 3.9(ii). • With the introduction of F*(J) and J*(F), the N F J model can be rewritten as maxs (F , J * (F ) ;A) , or, m a x 5 ( F * ( J ) , J ; A ) . For convenience, in the rest of the chapter, the objective function g may have different arguments. For example, g(J; A) or g(J) is the return of a selection plan (F*(J), J) under parameter A, g(F; c) is the return of collection (J*(F), F ) when the costs of the facilities are given by a function c(-). L E M M A 3.12 In the NF or NFJ models, g{J) and g(F) are supermodular in J and F, respectively. Proof . g(J) = Ar(J) — c(F*(J)). By Proposition 3.9(h), r(J) is modular, and by Proposition 3.10, c(F*(J)) is submodular in J , implying that —c(F*(J)) is supermodular. As the sum of supermodular functions is supermodular, the result follows. One can similarly prove that g(F) is supermodular. • Chapter 3. An Extended Selection Problem 98 L E M M A 3.13 In the NF or NFJ models, g(F; A) has isotone differences in F and A. Proof . Consider Ai < A 2 and g(F; X2)—g(F; Aj) = (X2-X1)r(J*(F)). Since r(J*(F)) is nondecreasing in F, g(F; A) has isotone differences in F and A. rj Suppose g(F;X) is parameterized on A. Let JF*(A) = {F\(F,J*(F)) is optimal for <?(F;A)}, and let J*(X) = {J\(F*(J),J) is optimal for g(J;X)}. Similarly, if g(F;c) is parameterized on the functional c(-), then let J-*(c) = {F\(F, J*(F)) is optimal for g(F; c)}, and so on. T H E O R E M 3.14 In the NF or NFJ models, T* (X) and J* (X) are both sublattices that are ascending in A. Proof . By Lemmas 3.12 and 3.13, g(F;X) is supermodular in F and has isotone differences in F and A. By Theorem 2.1, .F*(A) is an ascending sublattice in A. To prove that J*(X) is an ascending sublattice in A, consider Xx < X2 and let J i and J2 be optimal collections of jobs for Ai and X2, respectively. Let i * i = F*(Ji) and F2 = F*(J2). Then, Fi € . P ( A i ) and F2 e .F*(A 2). By the first half of the proof, T*(X) is ascending in A, and it follows that Fi V F2 € ^ * ( A 2 ) and Fx A F2 € ^ ( A j ) . By Propositions 3.8(iii), 3.9(iii) and the fact that T(J i ) C T(Fi ) and T(J2) C T(F2), T{Jx A J 2) C T ( J i ) f l T ( J 2 ) C r ( F 0 n r (F 2 ) = T ( F x A F2). Thus, F i A F 2 is sufficient to perform Jx A J2. Since (J i ,F x ) is optimal for A l 5 Xxr^ A J2) - c(F1 A F 2 ) < Air( J i ) - c(Fi), or, Ai(r(Ji) - r ( J i A J 2)) - (c(Fi) - c(Fx A F 2)) > 0. (3.46) On the other hand, both (J i ,Fi) and (Ji A J 2 ,F i ) are feasible selection plans, and the former is optimal for A i . Therefore, r(J i) — r ( J i A J2) > 0. Since A 2 > Ai > 0, (3.46) Chapter 3. An Extended Selection Problem 99 still holds if Ai therein is replaced with A 2 . Therefore, A 2 (r(Ji) - r ( J i A J2)) - c(Fi) + c(Fx A F2) > 0. (3.47) By adding A 2 r ( J 2 ) — c(F 2) to both sides of (3.47), it follows from the modularity of r(-) and c(-) that, A 2 (r(J i) + r(J2) - r ( J i A J2)) - c(Fx) - c{F2) + c(Fi A F 2 ) = A 2 r ( J i V J 2) - c(Fi V F 2 ) (3.48) > A 2 r( J 2 ) - c(F 2). Thus (Jx V J 2 , F i V F 2 ) is also an optimal selection plan for A 2 and A 2 r ( J i V J2) - c(Fi V F2) = A 2 r ( J 2 ) - c(F2). Substituting the latter equality back to the equality part of (3.48) yields A 2 (r(J i) - r ( J i A J2)) - c(Fx) + c{Fx A F 2 ) = 0. (3.49) Since r(J i ) — r(Jx A J 2) > 0 and A 2 > Ai > 0, replacing A 2 with Ai in (3.49) yields Ai(r(Ji) - r ( J i A J2)) - c(Fx) + c{Fx A F2) < 0, (3.50) or Air( J i ) - c(Fi) < Air ( J i A J2) - c{Fx A F2). It follows that (Ji A J 2 , F i A F 2 ) is an optimal selection plan for A i , which completes the proof. • Now I introduce a partial order among the revenue functions. For two revenue func-tions rx and r 2 , rx •< r 2 if rx(j) < r2(j) for every j £ J. Similarly, I define a partial order among the cost functions. For two cost functions cx and c 2, C i ~< c2 if cx(f) < c 2(/) for every / £ J-. Chapter 3. An Extended Selection Problem 100 L E M M A 3.15 In the NF model, g(F; r) has isotone differences in F and r, and g(J; r) has isotone differences in J and r. Proof . I first prove the first half of the lemma. Consider two revenue functions ri( ') and r2(-) such that rx(j) < r2(j) for every j 6 J. Consider the following difference: g(F; r2) - g(F; rx) = r2(r(F))-c(F)-ri(J*(F)) + c(F) = Ejej'(F)(r2(j) -ri(j)). Since the revenues are positive, J*(F) is increasing in F with respect to the partial order ^F- By assumption, r2(j) — ri(j') is nonnegative for each j. Thus g(F; r2) — g(F; rx) is nondecreasing in F. To prove the second half of the lemma, consider the following difference. g(J;r2) - flf(J;ri) = r 2 ( J ) - c ( F * ( J ) ) - r 1 ( J ) + c(F*(J)) Since r2(j)—r1(j) is nonnegative, g(J; r2)—g(J; rx) is nondecreasing in J, which completes the proof. • T H E O R E M 3.16 In the NF model, both T* (r) and J* (r) are ascending sublattices in r. Proof . Proof of the theorem follows from Lemmas 3.12 and 3.15. Indeed, g(F;r) is supermodular in F and has isotone differences in F and r. Thus by Theorem 2.1, T*{r) is an ascending sublattice in r. Similarly, since g( J; r) is supermodular in J and has isotone differences in J and r, J*(r) is an ascending sublattice in r. • Chapter 3. An Extended Selection Problem 101 The above theorem does not hold for the N F J model. Indeed, consider an example with three jobs, {j'x, j 2 , J 3 } , and three facilities {/l5 / 2 , f3}. Each facility performs a single task, which is identical to the facility itself; ji requires fx, j2 requires {fi,f2}, and j3 requires f3; jidjJ2, and only one of these two jobs may appear in a feasible selection plan due to the Non-Redundant Jobs Assumption. The costs of facilities / l 5 f2 and f3 are 1, 2 and 2, respectively. Initially, the revenues for jx, j2 and j3 are 1, 4 and 1, respectively, and the unique optimal selection plan is to perform job j2 and to acquire facilities fi, f2. Now increase the revenues for jobs ji, j2 and j3 to 4, 4, 3, respectively. The unique optimal selection plan under the new revenue function is to perform jobs jy and j3 and to acquire facilities fi and / 3 . It was shown by Brumelle and Granot (1993) that for the original selection problem, T*(c) and J*(c) are ascending sublattices in c, the facility cost function. This, however, is not valid for the N F or N F J models. Indeed, consider an N F model which contains three facilities and three jobs. The three facilities, fi, f2 and f3 perform tasks {ti}, {ti,t2} and {t3}, respectively. The three jobs, ji, j2 and j3 require tasks {ti}, {t2} and {t3}, and their revenues are 10, 2 and 2, respectively. Note that facilities fi and f2 are nested. Initially, the three facilities cost 1, 10 and 1, respectively, and the unique optimal selection plan is to acquire facilities fi and f3, and to perform jobs j i and j3. Now increase the costs °f fi-, f2 a n d f3 to 10, 10 and 10, respectively. Then the unique optimal selection plan is to acquire facility / 2 , and to perform jobs ji and j2. Clearly, the two optimal selection plans are neither monotone nor totally ordered. When the sets of tasks performed by the facilities increase, the optimal selection plan is neither monotone nor totally ordered for either the N F model or the N F J model. This is illustrated in the following example of an N F model, in which the potential jobs are ji, j2 and j 3 , with corresponding revenues 1, 10 and 2, respectively. The jobs require the sets of tasks { £ 1 } , {t2} and { £ 3 } , respectively. There are three facilities, / 1 ? f2 and / 3 , Chapter 3. An Extended Selection Problem 102 which cost 0.5, 10 and 1, respectively. Facilities / i and f2 are nested and perform the sets of tasks 0 and {t l 5 t 2 } , respectively. Facility / 3 performs { £ 4 } . One can verify that the unique optimal selection plan is to acquire facility f2, and to perform jobs j\ a n d j2-The profit from the selection plan is 1. Now increase the set of tasks performed by the facilities so that fi performs {t2}, f2 still performs {tx,t2}, a n d / 3 performs {t3,t4}. Then the unique optimal selection plan is to acquire facilities / i and / 3 and to perform jobs j2 and J 3 , with an associated profit of 10.5. It can be seen that the two optimal selection plans are not ordered. Now I construct an example to show that when the tasks required by the jobs increase, the optimal selection plans are neither monotone nor totally ordered for either the N F or the N F J model. In the following N F problem, there are three jobs, ji, j2, j 3 , with revenues 20, 1, and 10, respectively. They require tasks { £ 1 } , {t2} a n d { £ 3 } , respectively. There are four potential facilities, / 1 ; / 2 , / 3 and / 4 , with costs 1, 2, 1 and 20, respectively, and they perform tasks {^i}, {ti,t2}, {t3} and {t3,t4}, respectively. Note that facilities / i j f2 a r e nested and facilities / 3 , / 4 are nested. The optimal selection plan is to acquire facilities fi and / 3 and to perform jobs jx and j3. Now increase the sets of tasks required by the jobs so that ji requires {ti,t2} and j 3 requires {t3,t4}. The tasks required by the other jobs remain the same. The new optimal selection plan is to acquire facility f2 and to perform jobs jx and j2. Clearly, the two optimal selection plans are not totally ordered. Table 3.6 summarizes the monotone results for the N F , N F J and the original selection model 2. In Table 3.6, the monotonicity results are listed by different parameterizations. For example, "Ti(j') C T2(j), Vj G means that the parameterization is on the tasks required by the facilities and that for two instances, Ti and T2, of the parameter T(-), the set of tasks required by an arbitrary facility for the latter instance includes that for 2See Brumelle and Granot (1993) for details of the monotonicity results for the original selection problem. Chapter 3. An Extended Selection Problem 103 Parameterization N F N F J Original Xi < x2 ascending ascending ascending Ci(f)<Ca(f),Vfer no no descending ri(j) < r2(j), V j G J ascending no ascending Ti C T2 no no ascending Ji c J2 ascending no ascending W) c r2(j), Vj G J no no N A W) C T 2 ( / ) , V / G no no N A Table 3.6: Summary of monotone results the former instance. "Ascending" in the table means that the optimal set J-* and J* are ascending sublattices in the parameter. "No" indicates that monotonicity results do not exist for this parameterization. " N A " indicates that the parameterization is not applicable for this model. Note that the parameterization represented by "~T\ C in the table is a special case of "c2 < c\ \ and the parameterization represented by "J7i C J2n is a special case of 'V i < r2\ Other sensitivity analysis results can be derived. For example, it often occurs that the costs of facilities in a nested collection change together. This may be caused by a price change for a common component used in all the nested facilities. In Chapter 2,1 have shown that if in a capacitated network, a path from the source node to the sink node contains no parallel arcs, then there exists a totally ordered selection of minimum cuts when the capacities on the path are parametrically changed. Consider two nested facilities f\djfi- Since the unique path from fi to t must pass f2, the unique arcs originating from fi and f2 cannot be parallel. Recall that these two arcs have capacities equal to the facility costs, thus when the costs of a collection of nested facilities change, a totally ordered selection of optimal selection plans exists. Finally, McCormick (1995) showed that when the costs or revenues in the N F or N F J problems are parameterized Chapter 3. An Extended Selection Problem 104 subject to some magnitude restrictions, the parametric optimization problem can be solved efficiently by the G G T algorithm (Gallo, Grigoriadis and Tarjan, 1989). C h a p t e r 4 F o r e s t H a r v e s t a n d R o a d C o n s t r u c t i o n S c h e d u l i n g 4.1 T h e M o d e l In forest resource management, a watershed is divided into blocks (also referred to as cut blocks, forest management units, or units in other literature), each of which is a geographically contiguous area in which the topography, forest composition, etc. are consistent. A planning horizon is divided into a finite number of periods. For example, in solving a scheduling problem for the Tangier watershed in British Columbia, either 6 periods or 12 periods are used with each period being 10 years. In order to harvest a block, a road must be available from a saw mill or a transportation center to the block. Roads are constructed from a network of potential legs, which are assumed to form a graphical tree or a forest. The root of each tree in the network is a saw mill or a transportation center, and all other nodes in the network are cut blocks. A n edge in the network is called a leg of road. A forest harvest and road construction scheduling problem is an assignment of a time period to each block in which it is to be harvested and to each leg of road in which it is to be built. Two blocks are neighbors of each other if they are geographically adjacent. The adjacency constraints (also referred to as green-up constraint, spatial constraint, etc. in other literature) require that, if a block is harvested in a period p, then its neighbors can only be harvested after period p + g or before p — g, where g is a constant and is referred to as the green-up time. In solving the scheduling problem for the Tangier watershed, a 105 Chapter 4. Forest Harvest and Road Construction Scheduling 106 green-up time of 2 periods is used. In order to maintain a steady level of employment, it is desirable for a schedule to yield about the same volume of timber in different periods. Indeed, the government of British Columbia requires that the volume harvested in each period by a logging company does not deviate more than 10% from a licensed amount, which is usually the same for all the periods. The following is some notation used in the harvesting scheduling model: • B denotes the set of blocks in the forest. • P denotes the set of time periods, which includes period oo. If the harvest time of block of forest is oo, then it is never harvested in the planning horizon. • L denotes the set of legs of roads. • v(b,p) denotes the volume of timber on block b if it is harvested in time period p. Clearly, v(b, oo) = 0. • c(/,p) denotes the cost in present value for building a leg of road / in time period p. Similarly, c(/,oo) = 0. • m(b,p) denotes the present value of the contribution margin for harvesting a block b in time period p. The contribution margin of a block harvested in a time period is the difference between the revenue from the timber in the block and the harvesting cost (arising from felling, hauling, etc.). The revenue is calculated by first multiplying the volume of timber in the block in time period p and an average price of timber of the corresponding species and quality, then discounting to the present value. Due to the growth of trees, both the volume and price may change in time. Since a leg of road is on the path leading to various blocks, Chapter 4. Forest Harvest and Road Construction Scheduling 107 its cost cannot be attributed to any single block and thus the above mentioned harvesting cost does not include road cost. A harvest schedule is a function h(-) from B to P. For a block 6, h(b) is the time period in which the block is to be harvested. Thus it is assumed that the harvesting of a block starts and is completed within a single time period. Associated with a harvest schedule /i(-), there is a minimum cost road construction schedule allowing the scheduled harvest activities to take place. This road construction schedule is represented by a function rh(-) from L to P. Since each period in this model is 10 years, it can be assumed that a leg of road is available in the same time period as it is built. To ensure that the roads are ready when they are needed, a constraint rh{l) < h(b) (4.51) is introduced for each block b and each leg / on the road leading to b. It is assumed that if the cost for building a leg of road in period 0 is C 0 , then the cost (in present value) for building the leg in period p is Co/?p, where /3 is a discount factor. Thus road cost is decreasing in time, and for a given harvest schedule h, a leg of road should be built at the latest period without violating (4.51). It then follows that for each leg /, rh{l) = mm{h(b) : I is on the road leading to &.}. The function r/j(-) is then uniquely determined by A, and the minimum road cost associ-ated with a harvesting schedule h is C{h) = YJc(iMi))-leL For a harvesting schedule h, the total volume of timber harvested during period p is v(h,P) = ^v(b,h(b)), beB Chapter 4. Forest Harvest and Road Construction Scheduling 108 and the total volume of timber harvested during the whole planning horizon is peP The present value of income associated with a schedule h(-) is M * ) = £ ™ ( M ( & ) ) - £ c ( Z , r f c ( Z ) ) . The unevenness of flow for a schedule h is defined as u(h) = max V(h,p) — mmV(h,p). PGP p£P Recall that I assume that harvesting of a block must start and finish in a single time period, however, a logging company can take a schedule generated by my heuristic and further reduce unevenness by shifting the harvesting time of a block by a fraction of the time period and thus allocating the volume of this block to two consecutive time periods. The adjacency constraint requires that I M M ~ M M I > 2 (4-52) for all pairs (6i, b2) such that b\ and b2 are adjacent to each other. In some cases, slight violations of the adjacency constraints are allowed. Therefore, for a schedule h, the number of adjacency violations is defined as <h)=l-\\{(blM) • bub2eBA~b2, \h{b1)-h(b2)\<2}\\, where by ~ b2 means that b\ and b2 are adjacent to each other and || • || denotes the cardinality of a set. The cardinality of the set is divided by 2 in the above definition to avoid double counting of (bi,b2) and (b2,bi). A schedule is feasible if the number of violations is no larger than a bound A. If adjacency violations are not allowed, then A is set to 0. Chapter 4. Forest Harvest and Road Construction Scheduling 109 The harvesting scheduling problem is a multi-criteria optimization problem in which the present value of net income is maximized and the unevenness in harvest volumes is minimized. Let wu be the weight on unevenness, and without loss of generality, let the weight on the net income be 1. Then the two criteria can be combined into a single objective function and the problem can be formulated as follows: HP1: maxN(h) - wuu(h) subject to a(h) < A. The number of adjacency violations could also be incorporated as an additional cri-terion in the objective function. However, since this number is a small integer1 whereas the net income is usually in the magnitude of millions, the weight on the number of ad-jacency violations must be a very large number, otherwise the change in the number of adjacency violations will have little effect on the objective value. Then the algorithm would be very sensitive to the weight on the number of adjacency violations. Indeed in my computational experiments, I have observed that the heuristic is much more robust when the number of adjacency violations is incorporated in a constraint. 4.2 T h e T a b u S e a r c h H e u r i s t i c I first briefly describe some of the characteristics of the tabu search method. Since tabu search is a general methodology and heuristic algorithms that fall within this scope may vary significantly, the following introduction is not intended to be a thorough review of this methodology. Rather, it merely covers some of the features used in my heuristic. The reader is referred to Glover and Laguna (1993) for a detailed review of tabu search. 1 In my experiments on the Tangier watershed example, no more than 10 adjacency violations are allowed. Chapter 4. Forest Harvest and Road Construction Scheduling 110 Tabu search is a neighborhood search method that solves combinatorial optimization problems to near optimality. In each iteration, a current solution is identified, which is usually feasible to the optimization problem. The heuristic compares a collection of neighboring solutions in each iteration and chooses the best one to be used as the current solution of the next iteration. Neighboring solutions differ from the current solution only slightly. For example, if the current solution is a vector, then one may define its neighbors to be the vectors that differ from the current one in at most one element. The transition from a current solution to the next one is called a move. To encourage the heuristic to search through a diverse collection of solutions, and to avoid being trapped at or near a local optima, when the current solution leaves a neighborhood, an early return to the same neighborhood should be discouraged. Thus after a move is made, a number of iterations is specified which is known as the tabu tenure. During this tabu tenure, moves which are likely to cause the current solution to return to the old neighborhood are prohibited, and these moves are said to be tabu. If however, a tabu move will generate a solution that is better than all the currently known ones, then an exception is made to allow this move to happen, and such a move is called aspiration. In the heuristic presented in this chapter, each current solution is a harvest schedule h satisfying the bound on the number of adjacency violations. Since the minimum cost road construction schedule is uniquely determined by the harvest schedule, a harvest and road construction schedule is identified only by the harvest schedule component. A neighbor of a schedule is obtained by changing the harvest time of one block. Once a move is made that changes the harvesting time of a block b, the harvest time of b cannot be changed during the tabu tenure, which consists of a constant number of iterations specified by a parameter to the whole heuristic. In solving a forest harvest and scheduling problem without considering road construc-tion, Brumelle, Granot, Halme and Vertinsky (1996) implemented a simple aspiration Chapter 4. Forest Harvest and Road Construction Scheduling 111 criterion. They observed that the introduction of this aspiration criterion did not im-prove the solution by much. Thus in my heuristic, aspiration is not used, and yet the solutions generated appears to be very satisfactory. In each iteration, the change in objective value for each feasible move is calculated and is then multiplied by a uniform random number between 0.8 and 1.2 to yield a score for this move. Among all the non-tabu moves that do not cause the number of adjacency violations to exceed the limit A, a move with the best score is chosen and the current solution for the next iteration is generated. This process is repeated until a certain number of iterations is completed. A solution dominates another if the former is not inferior in any criterion and superior in at least one criterion. In each iteration, the newly generated schedule is compared with a collection of undominated solutions. If it is not dominated by any schedule in the collection, then it is introduced to the collection, and if it dominates existing solutions in the collection, the dominated ones will be removed. During the search, the parameters are systematically changed, which include the weight on unevenness and the upper bound on the number of adjacency violations. By this means, a reasonably diverse collection of undominated solutions can be obtained. In forest resource management, a decision maker may wish to know the trade off between the net income and the number of adjacency violations. For example, he may ask, how much net income must be sacrificed in order to reduce the number of adjacency violations by 1. Although the collection of undominated solutions does not provide a precise answer to such a question, it does provide a useful estimate. In calculating the change of unevenness, a surrogate measure is used to speed up computation. This surrogate measure focuses on periods with the largest and the smallest harvest volumes. Intuitively, if harvesting of a block is moved away from the period with the largest volume, then the unevenness should probably decrease by the volume of the Chapter 4. Forest Harvest and Road Construction Scheduling 112 block. See Appendix A for a detailed description of this surrogate measure. 4.3 S c h e d u l i n g P r o b l e m s i n the T a n g i e r W a t e r s h e d The Tangier watershed is located just north of the Trans-Canada highway between Mount Revelstoke and Glacier National Park. It is a part of the British Columbia Revelstoke Timber Supply Area. The watershed has a total area of about 28,000 hectares, of which slightly over 10,000 hectares are covered by forests. Half of this forested area is suitable for commercial forestry. While the primary land use has been commercial logging, poten-tial conflicts are apparent between logging and other land uses, such as wildlife habitat, recreation and old growth or biodiversity preservation (Thompson et al. 1993). A variety of species are growing in the Tangier watershed forest, including fir, cedar, hemlock, bal-sam and spruce. A significant number of the blocks are old growth. Some blocks consist of juvenile trees which will be ready for harvesting only in the last periods of the planning horizon. Based on a detailed set of harvest guidelines, Blake and Price (1993) identified 491 blocks suitable for harvesting. They specified the method to be used to harvest each block, but did not provide any harvest schedules. Among the 491 blocks suitable for harvesting, 272 blocks lie in a proposed provincial park2 and cannot be used for harvesting if the park eventuates. Thus two areas are considered, one contains all the 491 blocks and the other contains the 219 blocks outside the proposed provincial park. For each area, a planning horizon of either 6 periods or 12 periods is considered. Thus a total of four instances need to be solved. The legislation in British Columbia requires that the trees reach an average height of 3 meters before any adjacent blocks can be harvested, which corresponds to roughly 20 2The Serenity Peaks Wilderness Area. Chapter 4. Forest Harvest and Road Construction Scheduling 113 years of seedling growth. Thus a green-up time of 2 periods is used. The volume v(b,p) of timber obtained from harvesting block b at time period p is cal-culated using the British Columbia Ministry of Forests growth model TIPSY v.2 (Mitchell et a/.1992). The volume of timber available in a block is a function of species, site quality, age of trees and size of the block. The harvesting cost of a block depends on the choice of harvesting systems3 and volume of timber. Based on the assignment of harvesting system by Blake and Price (1993), the contribution margin for each block and each period is calculated, and discounted using a factor of 0.676 per 10 year period, which is equivalent to a 4.0% annual interest rate. A potential road network is predetermined and the road cost for each leg in the first period is calculated based on the length of the leg and the harvest system to be used where the leg traverses. The costs of a leg in later periods are obtained by discounting its cost in the first period. Table 4.7 presents the total volumes of timber available in the two areas in the sixth period or in the twelfth period. For example, the total volume of timber for the 219 blocks in the sixth period is 606,082 cubic meters. Since in the Tangier watershed, the timber volume does not decrease in time during the planning horizon, these volumes reflect the highest volume of timber that can ever exist in the planning horizons, and are upper-bounds of the total harvest volumes generated by the harvest schedules. 219 blocks problem 491 blocks problem 6th period 12th period 6th period 12th period Total Vol. (m3) 606,082 668,995 1,881,862 1,984,539 Table 4.7: Total volumes at the ends of the planning horizons For the small area, the total contribution margin is 9.825 million dollars if all the 3Harvesting system refers to the method of harvesting. Possible choices include crawler tractor, low pressure ground skidding, short distance cable, mid-distance cable, standing skyline and helicopter. Chapter 4. Forest Harvest and Road Construction Scheduling 114 profitable blocks (those with positive contribution margins) are cut in the first period, 10.766 million dollars (or 1.515 million dollars in present value) if harvested in the sixth period and 13.062 million dollars (or 0.175 million dollars in present value) if harvested in the twelfth period. For the large area, the total contribution margin is 35.847 million dollars if all the profitable blocks are cut in the first period, 37.694 million dollars (or 5.304 million dollars in present value) if harvested in the sixth period and 40.527 million dollars (or 0.542 million dollars in present value) if harvested in the twelfth period. The total road cost for the small area in the first period is 2.96 million dollars and 8.99 million dollars for the large area. To solve the scheduling problems, I implemented the tabu search heuristic in C++ on a HP9000/735 workstation. Tables 4.8 to 4.11 present the undominated solutions for the four problems. For each schedule, the number of adjacency violations, the net income, the total harvest volume, the unevenness, and the road cost are reported. The time lag from the moment the heuristic is started till the moment the solution is generated is also attached. As discussed in Chapter 3, if evenness of flow and adjacency constraints are ignored, the scheduling problem can be solved as a minimum cut problem, which yields an upper-bound for the unrelaxed problem. I generated directed networks corresponding to these relaxed problems and used the preflow algorithm (Goldberg and Tarjan, 1988) to obtain the minimum cuts. The net income for the two areas and two planning horizons are shown in Table 4.12. Unfortunately, this upper bound is not tight for the scheduling problems in the Tangier watershed. This is mainly due to the fact that the trees in the majority of the blocks have past the rapid growing stage and therefore, the present value of contribution margins decrease rapidly in time. Thus there is a strong incentive to harvest the blocks as early as possible. For example, when the even flow objective and adjacency constraints are Chapter 4. Forest Harvest and Road Construction Scheduling 115 Number of Adj . Viola-tions Net (in 3 Income ; io 6 ) Total Har-vest Volume Unevenness (m3) Road Cost ($106) Time Gen-erated (sec.) 0 2.3561 453249 921 1.5977 890.4 0 2.6454 428247 2465 1.4937 889.7 1 2.5752 442859 1098 1.6393 814.1 1 2.6174 436818 1482 1.5404 824.3 1 2.6712 436955 3795 1.5257 824.5 2 2.3453 466650 834 1.6703 350.2 3 2.6319 453276 2344 1.5701 276.0 3 2.7303 448029 4332 1.6153 718.0 4 2.3003 460406 619 1.7260 686.7 4 2.6363 449803 1648 1.5822 699.2 4 2.7354 466937 3962 1.6034 717.8 5 2.5611 451942 829 1.5065 216.2 5 2.8213 495498 2922 1.6145 212.7 6 2.7770 469430 2595 1.6177 591.3 7 2.6788 440779 1058 1.5849 581.8 7 2.7075 440779 1170 1.5888 581.7 8 2.5651 457270 874 1.6251 474.8 8 2.7111 464886 1063 1.6047 518.8 Table 4.8: Solutions for 219 blocks with 6 periods Chapter 4. Forest Harvest and Road Construction Scheduling 116 Number of Adj . Viola-tions Net Income (in $106) Total Har-vest Volume (m 3) Unevenness (m3) Road Cost ($106) Time Gen-erated (sec.) 0 2.1105 639064 3968 1.4492 1865.2 0 2.1186 635229 4294 1.3736 922.9 1 2.1536 621669 2534 1.4423 758.6 1 2.1592 629127 3952 1.4462 758.8 2 1.9486 628039 1992 1.3962 1648.9 3 2.1925 640165 1915 1.5140 1593.0 3 2.1957 640165 2633 1.4940 1592.8 3 2.2446 641571 3858 1.4184 1591.2 4 2.2518 622732 3706 1.3815 1508.8 4 2.3202 625872 4992 1.3735 1328.3 5 2.0228 631268 1890 1.2503 401.8 5 2.3540 616079 4500 1.3423 1325.9 6 2.0894 624749 1621 1.3360 1315.5 8 2.3443 645016 2775 1.3068 1085.1 8 2.3731 638872 3638 1.3397 1086.4 8 2.4165 638245 4957 1.3417 1086.3 10 1.4400 669478 1527 1.3724 136.1 Table 4.9: Solutions for 219 blocks with 12 periods Chapter 4. Forest Harvest and Road Construction Scheduling 117 Number of Adj . Viola-tions Net (in I Income UO6) Total Har-vest Volume (m3) Unevenness (m3) Road Cost ($106) Time Gen-erated (sec.) 0 10.1929 1475590 924 5.4151 1676.0 0 10.5249 1484150 2862 5.5118 1664.6 0 10.5364 1469030 4447 5.3871 1715.9 1 10.1493 1474340 561 5.5285 3473.4 1 10.5496 1482950 1413 5.4129 1547.4 1 10.6139 1522130 3923 5.4450 3322.9 1 10.6695 1523240 4249 5.5281 3341.7 2 10.3448 1476950 679 5.3483 1403.2 2 10.6270 1511760 779 5.4244 1256.2 3 10.7303 1527410 2524 5.3856 2862.6 4 10.6542 1523180 1462 5.4869 2827.3 4 10.7415 1498890 2478 5.3976 2783.4 4 10.7706 1498890 4262 5.3872 2783.2 5 10.4276 1530960 589 5.4416 761.5 5 10.8477 1542070 2212 5.4634 774.2 5 10.8503 1542070 4850 5.4634 774.4 6 10.5706 1567160 520 5.4370 2465.8 6 10.8188 1551840 1923 5.4976 2501.4 6 10.8938 1567630 3511 5.4724 2491.3 7 10.6199 1490620 751 5.4196 2218.3 8 10.8353 1520240 2041 5.5157 2131.5 8 10.9743 1520190 4762 5.4182 2007.1 Table 4.10: Solutions for 491 blocks with 6 periods Chapter 4. Forest Harvest and Road Construction Scheduling 118 Number of Adj . Viola-tions Net Income (in $106) Total Har-vest Volume (m3) Unevenness Road Cost ($106) Time Gen-erated (sec.) 0 7.5030 1956420 1821 4.5722 7934.3 0 7.6425 1946670 2117 4.5516 7982.8 0 7.9859 1969320 2867 4.5325 7822.4 0 7.9893 1971520 4987 4.5271 7826.4 1 7.7691 1956460 2650 4.5533 7711.8 2 7.0591 1898470 936 4.4286 2975.9 2 7.6720 1935570 2482 4.4824 2948.9 2 7.6988 1916860 2630 4.6320 7288.5 3 7.6523 1942940 1288 4.5841 6577.4 6 7.8413 1936510 2337 4.5834 5335.1 6 7.8650 1936510 2478 4.5824 5334.7 6 7.8886 1947060 2613 4.5959 5305.8 8 7.4807 1927840 916 4.5381 4722.9 8 7.7580 1939320 2239 4.5376 4805.1 Table 4.11: Solutions for 491 blocks with 12 periods 219 blocks 491 blocks 6 periods 12 periods 6 periods 12 periods Net Income (in $106) 8.707 8.729 31.467 31.489 Table 4.12: Optimal net income for the relaxed problems Chapter 4. Forest Harvest and Road Construction Scheduling 119 ignored, one of the feasible schedules is to harvest all the blocks and build all the roads in the first period. For the area with 219 blocks, this schedule yields a net income of 6.87 million dollars, which is much larger than the net income values for the unrelaxed problem. Since the above schedule is a feasible solution to the relaxed problem, the optimal net income value for the relaxed problem should be even larger than 6.87 million dollars. Since in some blocks the trees are still young in the early periods, the contribution margins for these blocks are negative throughout the first 6 periods. Thus in the schedules for the six-period problems, these blocks are not harvested at all in the planning horizon, and the harvest volumes are significantly less than the highest volume of timber in the planning horizon. Trees in most of these blocks will mature in later periods, making the contribution margins positive later on. Thus the harvest volumes for the twelve period problems are very close to the highest volume of timber that can ever exist in the area. For example, the highest volume of timber for the 491 blocks in the 12 periods planning horizon is 1.984 million cubic meters, and the total harvest volume for the first schedule in Table 4.11 is 1.956 million cubic meters, 1.6% less than the largest total volume. Brumelle, Granot, Halme and Vertinsky (1996) used a tabu search heuristic to solve the forest harvest scheduling problem for the same set of data but without considering road scheduling. Rather than maximizing the net income, their objective is to maximize total harvest volume. Therefore, in their solutions, the total harvest volumes are higher, especially for the 6 period problems. However, the net income associated with their schedules are much lower. For example, for the 219 blocks and 6 period problem, the total harvest volumes in their solutions range from 568,160 cubic meters to 579,752 cubic meters with an average of 575,733 cubic meters. The total volumes in my study for the same problem range from 428,247 to 495,498 cubic meters with an average of 453,545 cubic meters. The net incomes in their solutions range from 1.48 million dollars to 1.88 million dollars, with an average of 1.62 million dollars. The net incomes in my solutions Chapter 4. Forest Harvest and Road Construction Scheduling 120 range from 2.30 to 2.82 million dollars with an average of 2.61 million dollars. Their results are inferior in terms of net income because (1) they did not consider the road cost and (2) their focus is on the harvest volume instead of net income, and in some blocks the trees are so young that the contribution margins for these blocks are negative even though the volumes are positive. It can be seen that the net incomes does not change significantly in the number of adjacency violations. For example, in Table 4.11, the first solution has no adjacency violation and the net income is 5.55 million dollars. The last solution has 9 adjacency violations and the net income is 5.98 million dollars, which is only 7.7% higher than that of the first solution. This suggests that with proper scheduling, steady and profitable production can be sustained while at the same time, the damage to the environment can be significantly reduced. Bib l iography [1] T. Arai , S. Ueno, and Y . Kajitani. Generalization of a theorem on the parametric maximum flow problem. Discrete Applied Mathematics, 41:69-74, September 1993. [2] M . L. Balinski. On a selection problem. Management Science, 17(13):230—231, 1970. [3] B. B. Bare and G. A . Mendoza. Timber harvest scheduling in a fuzzy decision environment. Canadian Journal of Forest Research, 22:423-428, 1992. [4] J . Blake and L. Price. Revelstoke timber supply area gis-based multi-resource ana-lysis. The 7th annual symposium on geographic information system in forestry, en-vironment and natural resources management, Vancouver, B.C., 1:227-240, 1993. [5] Shelby Brumelle and Daniel Granot. The repair kit problem revisited. Operations Research, 41:994-1006, 1993. [6] Shelby Brumelle, Daniel Granot, Mirja Halme, and Ilan Vertinsky. A tabu search algorithm for finding a good forest harvest schedule satisfying green-up constraints. Working Paper, Faculty of Commerce, The University of British Columbia, 1996. [7] Shelby Brumelle, Daniel Granot, and Li Liu. An extended selection problem. Work-ing Paper 96-MSC-003, Faculty of Commerce, The University of British Columbia, 1996. [8] Shelby Brumelle, Daniel Granot, and L i Liu. Totally ordered optimal solutions and parametric maximum flows. Working Paper 96-MSC-002, Faculty of Commerce, The University of British Columbia, 1996. [9] P. J . Carstensen. Complexity of some parametric integer and network programming problems. Mathematical Programming, 26:64-75, 1983. [10] S.E. Clements, P. L. Dallein, and M . S. Jamnick. A n operational spatially con-strained harvest scheduling model. Canadian journal of Forest Research, 20:1438-1447, 1990. [11] Y . Crama. Combinatorial optimization models for production scheduling in auto-mated manufacturing systems. In Semi-plenary papers of EURO XIV conference, pages 237-259, Jerusalem, 1995. 121 Bibliography 122 [12] Y . Crama and J . Mazzola. Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and FMS part selection problems. Annals of Operations Research, 1995. [13] Kadri Dagdelen. Optimum multi period open pit mine production scheduling. PhD thesis, Colorado School of Mines, 1979. [14] Kadri Dagdelen. Cutoff grade optimization. In 23 r d Application of Computers and Operations Research in the Mineral Industry, page 157. Richardson, T X , USA Soc. of Petroleum Engineers of A I M E , 1992. [15] D. K . Daust and J. D. Nelson. Spatial reduction factors for strata-based harvest schedules. Forest Science, 39:152-165, 1993. [16] Renato de Matta, Vernon Ning Hsu, and Timothy J. Lowe. The capacitated selection problem. Technical report, Department of Management Science, College of Business Administration, University of Iowa, Iowa City, IA 52242, 1995. [17] E. V . Denardo, G. Huberman, and U . G. Rothblum. Optimal locations on a line are interleaved. Operations Research, 30(4):745-759, 1982. [18] Mark J. Eisner and Dennis G. Severance. Mathematical techniques for efficient record segmentation in large shared databases. J. Association for Computing Machinery, 23(4):619-635, 1976. [19] L. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, Princeton, N.J . , 1962. [20] S. Fortune, J . Hopcroft, and J . Wyllie. The directed subgraph homeomorphism problem. Theoretical Computer Science, 10:111-121, 1980. [21] G. Gallo, H . Grigoriadis, and R. E. Tarjan. A fast parametric network flow al-gorithm. SIAM Journal on Computing, 18(l):30-35, 1989. [22] F. Glover. Tabu search: Part i . ORSA Journal on Computing, l(3):190-206, 1989. [23] F. Glover and M . Laguna. Tabu search. In Colin R. Reeves, editor, Modern Heuristic Techniques for Combinatorial Problems, pages 70-150. 1993. [24] Andrew V . Goldberg and Robert E. Tarjan. A new approach to the maximum flow problem. J. Association for Computing Machinery, 35:4:921-940, October 1988. [25] F. Granot and Jr A . F. Veinott. Substitutes, complements and ripples in network flows. Mathematics of Operations Research, 10(3):471-497, 1985. Bibliography 123 T. E. Gross and D. 0 . Dykstra. Harvest scheduling with non-adjacency constraints. Proceedings of the Society of American Foresters National Convention, pages 310— 315, 1988. Dan Gusfield and Eva Tardos. A fast parametric minimum-cut algorithm. Algorith-mica, ll(3):278-290, 1994. Dan Gusfield and Charles Martel. A fast algorithm for the generalized parametric minimum cut problem and applications. Algorithmica, 7:499-519, 1992. H . M . Hoganson and D. W. Rose. A simulation approach for optimal timber man-agement scheduling. Forest Science, 30:220-238, 1984. A. F. Howard. A critical look at multiple criteria decision making techniques with reference to forestry applications. Canadian Journal of Forest Research, 21:1649-1659, 1991. A. F. Howard and J . D. Nelson. Area-based harvest scheduling and allocation of forest land using methods for multiple-criteria decision making. Canadian Journal of Forest Research, 23:151-158, 1993. M . S. Jamnick and K. R. Walters. Spatial and temporal allocation of stratum-based harvest schedules. Canadian Journal of Forest Research, 23:402-413, 1993. K . N . Johnson and H . L. Scheurman. Techniques for prescribing optimal timber harvest and investment under different objectives - discussion and synthesis. Forest Science Monograph, 18, 1977. M . W. Kirby, P. Wong, W. A . Hager, and M . E. Huddleston. A guide to the integ-rated resources planning model. Technical report, USDA Forest Service, Berkeley, C A , 1980. C. Lockwood and T. Moore. Harvest scheduling with spatial constraints: A simu-lated annealing approach. Canadian Journal of Forest Research, 23:468-478, 1993. William S. Lovejoy. Some monotonicity results for partially observed markov de-cision processes. Operations Research, 35(5):736-743, 1987. D. Ludwig. Forest management strategies that account for short-term and long-term consequences. Canadian Journal of Forest Research, 23:563-572, 1993. John W. Mamer and Stephen A. Smith. Optimizing field repair kits based on job completion rate. Management Science, 28(11): 1328—1333, 1982. Bibliography 124 S.T. McCormick. Fast algorithms for parametric scheduling come from extensions to parametric maximum flow. Working Paper 95-MSC-005, Division of Management Science, Faculty of Commerce, University of British Columbia, 1995. B. J . Meneghin, M . W. Kirby, and J. G. Jones. A n algorithm for writing adjacency constraints efficiently in linear programming models. Technical report, USDA Forest Service General Technical Report RM-161, Fort Collins, C O , 1988. Paul Milgrom and John Roberts. The economics of modern manufacturing techno-logy, strategy, and organization. American Economic Review, 80(3):511-528, June 1990. Paul Milgrom and Chris Shannon. Monotone comparative statics. Econometrica, 62(1):157-180, January 1994. K . J . Mitchell, S. E. Grout, R. N . MacDonald, and D. A . Watmough. User's guide for tipsy: A table interpolation program for stand yields. Technical report, B. C. Ministry of Forests, Victoria., 1992. J . D. Nelson and S. T. Finn. The influence of cut-block size and adjacency rules on harvest levels and road networks. Canadian Journal of Forest Research, 21:595-600, 1991. J . D. Nelson and A. F. Howard. A three-stage heuristic procedure for allocating spatially and temporally feasible cutting rights on public lands. Canadian Journal of Forest Research, 21:762-768, 1991. B .C . Ministry of Forests. Revelstoke tsa timber supply analysis. Technical report, Integrated Resource Branch, B .C. Ministry of Forests, Victoria, 1993. 0. Ore. Theory of Graphs, volume 38. American Mathematical Society Colloquium Publications, Providence, Rhode Island, 1962. A. J . Q'Hara, B. H . Faaland, and B. B. Bare. Spatially constrained timber harvest scheduling. Canadian Journal of Forest Research, 19:715-724, 1989. J. M . W. Rhys. A selection problem of shared fixed costs and network flows. Man-agement Science, 17(3):200-207, November 1970. J . Sessions and J. B. Sessions. Scheduling and network analysis program (snap ii), user guide version 1.0. Technical report, Oregon State University, Corvallis, OR, 1990. Bibliography 125 [51] Stephen A. Smith, John C. Chambers, and El i Shlifer. Optimal inventories based on job completion rate for repairs requiring multiple items. Management Science, 26(8):849-852, 1980. [52] H . S. Stone, Critical load factors in two-processor distributed systems, IEEE Trans. Software Engineering, 4:254-258, 1978. [53] W. A . Thompson, G. C. van Kooten, I. Vertinsky, S. Brown, and H . Schreier. A preliminary economic model for evaluation of forest management in a geo-referenced framework. The 7th Annual Symposium on Geographic Information Systems in Forestry Environment and Natural Resources Management, Vancouver, B.C., 1:209-220, 1993. [54] D. M . Topkis and Jr. A . F. Veinott. Monotone solutions of extremal problems on lattices. In Abstracts of talks, VIII International Symposium on Mathematical Programming, page 131, Stanford University, 1973. [55] Donald M . Topkis. Ordered optimal solutions. PhD thesis, Department of Operations Research, Stanford University, 1968. [56] Donald M . Topkis. Minimizing a submodular function on a lattice. Operations Research, 26(2):305-321, 1978. [57] Donald M . Topkis. Comparative statics of the firm. Journal of Economic Theory, 67:370-401, 1995. [58] J . M . Torres and J . D. Brodie. Adjacency constraints in harvest scheduling: A n aggregation heuristic. Canadian Journal of Forest Research, 20:978-986, 1990. [59] A . F. Jr Veinott. Lattice programming. Forthcoming. [60] A . F. Jr. Veinott. Class notes, course on inventory theory. Operations Research Department, Stanford University, 1974. [61] U . Zimmerman. Linear and combinatorial optimization in ordered algebraic struc-tures. North Holland, 1981. A p p e n d i x A P s e u d o - C o d e f o r the T a b u H e u r i s t i c T H E T A B U S E A R C H H E U R I S T I C Construct an i n i t i a l schedule h. FDR each record i n a parameter f i l e { Read a set of parameters: adj_violation_bound, uneven_weight, road_cost_weight, i t e r a t i o n s ; FOR i t e r a t i o n s TIMES REPEAT: { FOR ALL p a i r s (6,p) G B X P SUCH THAT ( (block b i s not tabu) AND (h(b) ^ p) AND (changing h(b) to p w i l l not cause the number of v i o l a t i o n to be more than adj_viol_bound) ) { 126 Appendix A. Pseudo-Code for the Tabu Heuristic /* Compute the change i n ob j e c t i v e value i f harvesting time of b i s changed to p */ A(6,p)=Delta( / i , b, p) ; / * Perturb the change: */ A(&,p) = A(6,p) * Random(l-e, 1+e, Uniform); } Among the above (b, p) p a i r s , f i n d one with the best A(b,p) and change the harvesting time of b to p by-c a l l i n g Move(/i, b, p) . } /* End of the tabu search h e u r i s t i c . */ Appendix A. Pseudo-Code for the Tabu Heuristic F U N C T I O N S U S E D IN T H E T A B U S E A R C H H E U R I S T I C : / * Compute the change i n ob j e c t i v e value i f harvesting time of b i s changed to p: */ FUNCTION D e l t a ( / i , b, p) { RETURN_VALUE =. Delta_contribution(n, b, p) -Delta_ j road_cost (h, b, p) -uneven_weight*Delta_uneven ( / i , b, p) -} /* Change i n c o n t r i b u t i o n margin i s simply the d i f f e r e n c e between the c o n t r i b u t i o n margins i n two time periods: */ FUNCTION Delta_volume(/i,&,p) { RETURN_VALUE = m(b,p) - m(6, h(b)); } Appendix A. Pseudo-Code for the Tabu Heuristic /* A f u n c t i o n t o c a l c u l a t e changes i n unevenness p r e c i s e l y : */ FUNCTION Delta_uneven ( / i ,6,p) { /* F i r s t d e l e t e the volume v(b,h(p)) */ IF (A(6)==period_with_max_volume) { max_volume_af ter_delete= MAX( (max_volume_of _ a l l _ p e r i o d s - u ( 6 , h(b))) , second_largest_volume_of _ a l l _ p e r i o d s ) ; } ELSE max_volume_af ter_delete=max_volume_of _ a l l _ p e r i o d s ; temp=volume_of _period [ / i (6) ] -v (b, h(b) ) ; IF (min_volume_of_all_periods <= temp) { min_volume_af ter_delete=min_volume_of _ a l l _ p e r i o d s ; min_period_af ter_delete=period_with_min_volume; second_smallest_volume_after_delete= Appendix A. Pseudo-Code for the Tabu Heuristic 130 MIN(temp, • second_smallest_volume_of _all_periods) ; } ELSE { min_volume_after_delete=temp; min_period_after_delete=/2(6) ; IF (h(b) != period_with_smallest_volume) second_smallest_volume_after_delete= min_volume_of _all_periods; ELSE second_smallest_volume_after_delete= second_smallest_volume_of_all_periods; } /* Then add volume v(b,p) */ new_max_volume= MAX(max_volume_af ter_delete, (volume_in_period[p] + v(b,p)) IF (p==min_period_after_delete) new_min_volume= Appendix A. Pseudo-Code for the Tabu Heuristic 131 MIN((min_volume_after_delete + v(b,p)), second_smallest_volume_after_delete) ; ELSE new_min_volume=min_volume_af ter_delete; new_uneven=new_max_volume-new_min_volume; /* A f u n c t i o n to c a l c u l a t e a surrogate of changes i n unevenness: */ FUNCTION Delta_uneven ( / i , 6,p) { d=0; IF (/i(6)==period_with_max_volume) d=d - v(b,h(b)); IF (/i(6)==period_with_min_volume) d=d + v(b,h(b)); IF (p)==period_with_max_volume) d = d + v(b,p); IF (p==period_with_min_volume) d = d - v(b,p); RETURN_VALUE=d; Appendix A. Pseudo-Code for the Tabu Heuristic 132 /* Change i n road c o s t . In the f u n c t i o n , a l e g i s i d e n t i f i e d by the b l o c k i t goes i n t o . For example, i f a l e g goes from the saw m i l l t o a b l o c k 3, then the l e g i s r e f e r r e d t o as 3. I f th e r e i s another l e g from b l o c k 3 t o b l o c k 5 (note t h a t b l o c k 3 i s c l o s e r t o the saw m i l l than 5), then t h i s l e g w i l l be r e f e r r e d t o as 5. S i b l i n g l e g s are those going i n t o s i b l i n g nodes, and o f f s p r i n g l e g s are those going i n t o o f f s p r i n g nodes of a node. */ FUNCTION Delta_road_cost ( / i , b, p) { old_construction_time=construction_time [ 6 ] ; IF (p< old_construction_time) new_construction_time=p ; ELSE /* c o n s t r u c t i o n of t h i s l e g can be delayed */ { f i n d the minimum c o n s t r u c t i o n time t l f o r a l l o f f s p r i n g l e g s ; new_construction_time=tl; } endix A. Pseudo-Code for the Tabu Heuristic FIND the e a r l i e s t period t2 among the f o l l o w i n g : new_construction_time, periods i n which s i b l i n g legs of b are constructed, harvesting time of Parent ( 6 ) , RETURN_VALUE= Leg_cost(b,t)-Leg_cost(b,tO) + Deltajroad_cost(/i, Parent(fr), t 2 ) ;
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Ordered optimal solutions and applications
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Ordered optimal solutions and applications Liu, Li 1996
pdf
Page Metadata
Item Metadata
Title | Ordered optimal solutions and applications |
Creator |
Liu, Li |
Date Issued | 1996 |
Description | The Monotone Response and Selection (MRS) Theorems in lattice programming provide a sufficient condition under which the optimal solutions of a parametric optimization problem are monotone in the parameter. The MRS Theorems have many applications. In particular, they explain the monotonicity of minimum cuts in parametric maximum flow problems in certain networks. However, in some parametric optimization problems, monotonicity does not hold. Rather, a totally ordered selection of optimal solutions exists. In Chapter 2, I present some conditions under which there exists a selection of optimal solutions that are totally ordered, but not necessarily monotone. Based on this result, I present necessary and sufficient conditions for some natural classes of parametric maximum flow problems to ensure the existence of a totally ordered selection of minimum cuts. In Chapter 3, I extend the original selection problem studied by Rhys (1970) and Balinski (1970). I introduce the notion of tasks and assume that, facilities are capable of performing multi-tasks. A job then, instead of requiring a fixed set of facilities, requires a set of tasks, which can be performed by different facilities. The objective is to maximize the net return. Although this extended model is NP-hard, by introducing some natural restrictions in the extended selection problem, I obtain two variants thereof, which can be solved as minimum cut problems. A forest-harvest and road-construction scheduling problem can be formulated as one of the two variants and solved as a minimum cut problem. Recently, new legislations have been introduced which require that a logging company cannot harvest a block of forest if an adjacent block has been harvested within the past 20 years. In order to harvest a block of forest, a road must be ready leading from a saw mill to the block. Roads must be constructed from a tree structured network of potential links. Due to the long planning horizon, forest-harvesting and road-construction must be scheduled together in order to maximize the present value of net income. In Chapter 4, I present a tabu search heuristic to generate schedules which compare favorably with previous studies. |
Extent | 5856822 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-03-17 |
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.0087853 |
URI | http://hdl.handle.net/2429/6161 |
Degree |
Doctor of Philosophy - PhD |
Program |
Business Administration - Management Science |
Affiliation |
Business, Sauder School of Operations and Logistics (OPLOG), Division of |
Degree Grantor | University of British Columbia |
GraduationDate | 1996-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_1996-147835.pdf [ 5.59MB ]
- Metadata
- JSON: 831-1.0087853.json
- JSON-LD: 831-1.0087853-ld.json
- RDF/XML (Pretty): 831-1.0087853-rdf.xml
- RDF/JSON: 831-1.0087853-rdf.json
- Turtle: 831-1.0087853-turtle.txt
- N-Triples: 831-1.0087853-rdf-ntriples.txt
- Original Record: 831-1.0087853-source.json
- Full Text
- 831-1.0087853-fulltext.txt
- Citation
- 831-1.0087853.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0087853/manifest