A GOAL PROGRAMMING ALGORITHM TO INCORPORATE THE COLUMBIA RIVER NON-POWER FLOW REQUIREMENTS IN THE COLUMBIA RIVER TREATY MODEL by ABDULLAH AL MAMUN B.Sc., Bangladesh University of Engineering and Technology (BUET), 2008 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENT FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES (Civil Engineering) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) January, 2012 © Abdullah Al Mamun, 2012 ABSTRACT Canada built and operates three large dams and the U.S. built and operates one dam in the Columbia River based on the Columbia River Treaty (CRT) which was signed in 1961 and ratified in 1964. Annual Operating Plan developed by two Entities does not include non-power requirements, unless they are mutually agreed upon by both Entities. Supplemental Operating Agreements (SOA) have been negotiated and implemented since the 1990s to meet the U.S. and the Canadian power, fish, wildlife and/or recreation needs. The objective of this research was to develop a multi-objective optimization model to deal with multiple and conflicting objectives. The Columbia River Treaty Model (CRTM) developed by BC Hydro was modified by this research to incorporate three non-power requirements that are agreed upon by both Entities. The new model, which utilized the Goal Programming technique to solve the multi-objective reservoir optimization problem, was used to perform a number of case studies in order to investigate the impacts of incorporating different non-power requirements onto the BC Hydro system. Specific minimum outflow at the border in January affects the level of fulfillment of three non-power requirements. The first requirement is the Flow Augmentation requirement to aid in the downstream migration of Salmon in the U.S. The second requirement is the flow requirements below the Arrow reservoir to protect Whitefish eggs during the spawning and hatching periods. The third requirement is the specific flow requirement to provide enough water cover for the Trout spawning downstream of Arrow. The model uses three prioritized objectives of which the Flow Augmentation and Whitefish are of highest priority followed by the Trout Spawning and the maximization of BC Hydro revenues. Four Arrow minimum flow scenarios were compared with the Treaty operation. The study results show that lowering the minimum Arrow flow limit in January increases the satisfaction level of the Flow Augmentation and Whitefish non-power ii requirements. However, it may be in conflict with the power requirement of meeting Pacific North-west winter peak loads. Unless additional flow is required for Flow Augmentation during April, it has no effect on Trout spawning. iii TABLE OF CONTENTS ABSTRACT .................................................................................................................... ii TABLE OF CONTENTS ................................................................................................ iv LIST OF TABLES ......................................................................................................... vii LIST OF FIGURES ...................................................................................................... viii LIST OF ABBREVIATIONS ........................................................................................... x ACKNOWLEDGEMENTS ........................................................................................... xiii DEDICATION............................................................................................................... xiv CHAPTER 1: INTRODUCTION ..................................................................................... 1 1.1 BACKGROUND .......................................................................................................... 1 1.2 PROBLEM STATEMENT ............................................................................................ 5 1.3 GOALS AND OBJECTIVES ........................................................................................ 7 1.4 ORGANIZATION OF THE THESIS ............................................................................. 8 CHAPTER 2: SURVEY OF THE LITERATURE ............................................................ 9 2.1 BACKGROUND .......................................................................................................... 9 2.2 OPTIMIZATION TECHNIQUES ................................................................................ 10 2.2.1 LINEAR PROGRAMMING................................................................................................ 10 2.2.2 INTEGER AND MIXED-INTEGER PROGRAMMING ...................................................... 11 2.2.3 DYNAMIC PROGRAMMING ............................................................................................ 12 2.2.4 NON-LINEAR PROGRAMMING ...................................................................................... 13 2.2.5 EVOLUTIONARY AND HEURISTIC ALGORITHMS ....................................................... 13 2.2.6 MULTI-OBJECTIVE OPTIMIZATION ............................................................................... 14 2.3 GOAL PROGRAMMING (GP) MODELS ................................................................... 19 2.4 SUMMARY ............................................................................................................... 22 CHAPTER 3: THE COLUMBIA RIVER TREATY (CRT) ............................................. 24 iv 3.1 COLUMBIA RIVER ................................................................................................... 24 3.2 HISTORY OF THE COLUMBIA RIVER TREATY ...................................................... 27 3.3 MAIN FEATURES OF THE TREATY ........................................................................ 28 3.4 THE COLUMBIA RIVER TREATY PROJECTS ........................................................ 30 3.5 THE CRT BENEFITS ................................................................................................ 31 3.6 THE CRT OPERATING PLANS ................................................................................ 32 3.7 SUPPLEMENTAL OPERATING AGREEMENTS (SOP) ........................................... 34 3.7.1 FALL STORAGE AGREEMENT ...................................................................................... 35 3.7.2 SUMMER STORAGE AGREEMENT ............................................................................... 35 3.7.3 ARROW FLOW SHAPING AGREEMENT ....................................................................... 36 3.7.4 NON-POWER USES AGREEMENT ................................................................................ 36 3.8 SUMMARY ............................................................................................................... 38 CHAPTER 4: MODELING METHODOLOGY .............................................................. 39 4.1 INTRODUCTION ...................................................................................................... 39 4.2 PHILOSOPHY OF GOAL PROGRAMMING ............................................................. 40 4.3 GOAL PROGRAMMING TECHNIQUES ................................................................... 42 4.3.1 WEIGHTED GOAL PROGRAMMING (WGP) .................................................................. 42 4.3.2 LEXICOGRAPHIC GOAL PROGRAMMING (LGP) ......................................................... 43 4.3.3 MINMAX GOAL PROGRAMMING ................................................................................... 45 4.3.4 OTHER GOAL PROGRAMMING TECHNIQUES ............................................................ 46 4.4 ISSUES WITH THE USE OF GOAL PROGRAMMING ............................................. 47 4.4.1 INCOMMENSURABILITY................................................................................................. 47 4.4.2 PARETO EFFICIENT SOLUTIONS ................................................................................. 48 4.4.3 NAIVE PRIORITIZATION AND REDUNDANCY IN LEXICOGRAPHIC GP .................... 50 4.4.4 TRADE-OFFS ACROSS PREEMPTIVE PRIORITY LEVELS ......................................... 50 4.5 GOOD AND POOR MODELING PRACTICES IN GOAL PROGRAMMING .............. 50 4.6 SUMMARY ............................................................................................................... 51 CHAPTER 5: MULTI-OBJECTIVE GOAL PROGRAMMING MODEL DEVELOPMENT FOR THE COLUMBIA RIVER RESERVOIR OPERATIONS ....................................... 52 5.1 INTRODUCTION ...................................................................................................... 52 v 5.2 COMPONENTS OF CRT MODEL ............................................................................ 53 5.2.1 DECISION VARIABLES ................................................................................................... 53 5.2.2 BASIC CONSTRAINTS .................................................................................................... 54 5.2.3 CRT RELATED CONSTRAINTS ...................................................................................... 59 5.3 COMPONENTS OF THE CRT-GP MODEL .............................................................. 61 5.4 OBJECTIVE FUNCTION........................................................................................... 64 5.5 SOLUTION ALGORITHM ......................................................................................... 65 5.6 SUMMARY ............................................................................................................... 68 CHAPTER 6: MODEL APPLICATIONS AND RESULTS ANALYSIS ........................ 69 6.1 INTRODUCTION ...................................................................................................... 69 6.2 BASE TREATY CASE .............................................................................................. 69 6.3 CASE STUDIES USING PRIORITIZED OBJECTIVES ............................................. 74 6.3.1 BC HYDRO IDEAL CASE ................................................................................................ 74 6.3.2 TRADE-OFF CASES ........................................................................................................ 77 6.4 IMPACTS ON GENERATION ................................................................................... 81 CHAPTER 7: CONCLUSIONS AND RECOMMENDATIONS ..................................... 83 7.1 SUMMARY ............................................................................................................... 83 7.2 CONCLUSION .......................................................................................................... 84 7.3 FUTURE WORK ....................................................................................................... 86 BIBLIOGRAPHY .......................................................................................................... 87 APPENDICES............................................................................................................... 92 vi LIST OF TABLES Table 3-1: Characteristics of the Treaty Projects (Hyde, 2010) .................................... 31 vii LIST OF FIGURES Figure 1-1: The BC Hydro Electric System (http://www.knowbc.com) ............................ 2 Figure 3-1: Columbia River Basin and Existing Hydropower Plants (USACE) .............. 25 Figure 3-2: Columbia River Streamflows (System, 2001) ............................................. 26 Figure 4-1: Algorithm for Solving GP Models Avoiding Non-efficient Solutions (Adopted from Romero, 1991) ...................................................................................................... 49 Figure 5-1: GOM Model Algorithm with GP Formulation ............................................... 67 Figure 6-1: Flow Duration Curve for Arrow Flow in January (Base Treaty Case) ......... 70 Figure 6-2: Flow Duration Curves for (January Flow-February Flow) and (January Flow – March Flow) (Base Treaty Case) ............................................................................... 71 Figure 6-3: Flow Duration Curve for Arrow Flow in April with TS target flow (Base Treaty Case) ............................................................................................................................ 72 Figure 6-4: Flow Duration Curves for (April Flow-May Flow) and (May Flow – June Flow) (Base Treaty Case) ....................................................................................................... 73 Figure 6-5: Annual April, May and June Flow Graphs (Base Case) .............................. 73 Figure 6-6: Flow Duration Curve for Arrow Flow in January (BCH Ideal Case) ............ 75 Figure 6-7: Flow Duration Curves for (January Flow-February Flow) and (January Flow – March Flow) (BCH Ideal Case) .................................................................................. 75 Figure 6-8: Flow Duration Curve for April Flow with TS target flow (BCH Ideal Case) .. 76 viii Figure 6-9: Annual April, May and June Flow Graphs (BCH Ideal Case) ...................... 76 Figure 6-10: Flow Duration Curves for (April Flow-May Flow) and (May Flow – June Flow) (BCH Ideal Case) ................................................................................................ 77 Figure 6-11: Cumulative Occurrence of FA Storage for Different January Minimum Flow Limit (Trade-Off Cases) ................................................................................................ 78 Figure 6-12: Flow Duration Curves for (January Flow-February Flow) and (January Flow – March Flow) (Trade-Off Case: Target Flow 48 kcfs) .................................................. 79 Figure 6-13: Flow Duration Curve for April Flow with TS target flow (Trade-Off Case: Target Flow 48 kcfs) ..................................................................................................... 80 Figure 6-14: Flow Duration Curves for (April Flow-May Flow) and (May Flow – June Flow) (Trade-Off Case: Target Flow 48 kcfs) ................................................................ 80 Figure 6-15: Annual April, May and June Flow Graphs (Trade-Off Case: Target Flow 48 kcfs) .............................................................................................................................. 81 Figure 6-16: Mica Average Monthly Generation for Different Case Studies .................. 82 ix LIST OF ABBREVIATIONS ACO Ant Colony Optimization AMPL Applied Mathematical Programming Language AOP Assured Operating Plan BC British Columbia BC Hydro British Columbia Hydro and Power Authority BA Biological Assessment BPA Bonneville Power Administration cms Cubic meter per second cms-d Cubic meter per second-day CRT Columbia River Treaty DOP Detailed Operating Plan DP Dynamic Programming DFO Department of Fisheries and Oceans Canada e.g. For example Exp Energy Export FCC Flood Control Curve x ft Foot GA Genetic Algorithm GP Goal Programming GOM Generalized Optimization Model GWh Gigawatt-hour GWh/a Gigawatt-hours per annum i.e. That is IJC International Joint Commission Imp Energy Import IPP Independent Power Producers kcfs Thousand cubic foot per second ksfd Thousand cubic foot per second-day kV Kilo Volt LP Linear Programming LGP Lexicographic Goal Programming m Meter Maf Million Acre Feet xi m3 Cubic meter MW Megawatt MWh Megawatt-hour NLP Non-Linear Programming PEB Permanent Engineering Board PWL Piecewise Linear Programming SDP Stochastic Dynamic programming SOP Supplemental Operating Agreements TVA The Tennessee Valley Authority TSR The Treaty Storage Regulation xii ACKNOWLEDGEMENTS I am very grateful to my thesis supervisor Dr. Ziad Shawwash. Without his guidance and support, this thesis would never have been completed. Through his consistent guidance and support, I have gained understandings and knowledge about this research in the course of my graduate studies. I also like to express my gratitude to Dr. Greg Lawrence for his insightful suggestions and helpful comments. I am very thankful to Dr. Thomas Siu for his continuous support and help for this research. This research has advanced and benefited from his vast experience in the Columbia River Treaty and operations planning of BC Hydro reservoir systems. I also like to show my gratitude to Alaa Abdalla, Manager of the Reliability and Planning group-Generation Resource Management at BC Hydro, for his support and thoughtful recommendations throughout this research. I also like to thank Yuehao Tang, a former consultant at BC Hydro. My understanding of the Generalized Optimization Model (GOM) and the Columbia River Treaty (CRT) models was enhanced by many discussion sessions that I had with him. Interaction with my colleague Amr Ayad was very helpful and often helped me to think critically. He always encouraged me and offered his help if I needed any. I am very indebted to my wife Rubaiat, for her continuous support, love and patience throughout my graduate study. Finally, I like to thank my parents for believing in me and for the great care they showed throughout my life. xiii DEDICATION This thesis is dedicated to my parents and my loving wife, Rubaiat for their great care and love for me and giving me courage to move ahead in my life. xiv CHAPTER 1: INTRODUCTION 1.1 BACKGROUND British Columbia is blessed with numerous creeks and rivers with significant potential for hydro power generation. To meet the growing demand for electricity, a large number of dams were built throughout the province and they currently generate the majority of electricity in B.C. In total, 29 hydroelectric generating stations are operated by the British Columbia Hydro and Power Authority (BC Hydro), that produce around 90 percent of the total electricity production in the province. BC Hydro is the third largest utility company in Canada, the largest supplier of electrical energy to the people of British Columbia and in charge of power generation and operation of the majority of power generating plants in B.C. In addition, the BC Hydro Electric Generation System includes one thermal station, and two combustion gas turbine stations with a total maximum generating capacity of 10,800 megawatts (MW) and on average produces about 50,000 Gigawatt-hours per annum (GWh/a) (Hydro, 2000). The hydroelectric plants are distributed into four main systems: i) the Peace River system which includes the Peace Canyon and the G.M. Shrum generating stations producing about 34 percent of BC Hydro‟s total electricity production, ii) the Columbia River system which includes Mica, Revelstoke, and the Keenleyside hydroelectric plants contributing approximately 31 percent, iii) Kootenay Canal and Seven Mile and Waneta generating stations producing about 13 percent, and iv) the remaining 23 hydroelectric generating stations producing about over 16 percent of electricity production. The balance of the electricity is either provided by the thermal stations, Independent Power Producers (IPP) plants or imported from U.S./Alberta markets. Figure 1-1shows the location and name of some of the generating stations in B.C. operated by BC Hydro. 1 Figure 1-1: The BC Hydro Electric System (http://www.knowbc.com) The Williston reservoir on the Peace River and the Kinbasket reservoir on the Columbia River are the two major hydroelectric storage facilities of the BC Hydro system having live storage capacity of 39.4 billion m3 and 14.8 billion m3 respectively. This large storage capability can contribute significantly to the stability and security of BC Hydro‟s hydroelectric system by providing a reliable and sufficient supply of water to generate 2 enough electricity for multiple years and these two reservoirs are strategically used for planning the long-term operations of the BC Hydro system. Lack of storability of electric power can impose immense pressure on the system to meet the energy demand. Therefore, the hydroelectric system has to be capable of supplying energy within a wide range of output and should also be able to change its production level in a short period of time. Usually, the capability of BC Hydro‟s electric generation system is determined by the firm energy produced under all historical streamflow conditions over a given period (e.g. a sequence of several years) as well as its peaking capacity during peak electric demand periods which typically occurs in the winter months in B.C. However, increasing energy demand, growing water demand for non-power uses, public awareness and tighter environmental regulations also impose pressures on the system. In addition, all BC Hydro reservoirs have to deal with complex provincial and federal regulations and international (trans-boundary) agreements (e.g. The Columbia River Treaty), fisheries, recreational and environmental flow requirements. The electrical transmission network in British Columbia consists of 17,800 kilometers of transmission lines (60 kilovolts and above) and 52,600 kilometers of distribution lines (below 60 kV). The transmission network is interconnected with Alberta, West Kootenay Power and Cominco in southeast B.C., the Alcan system in the North Coast, and to the Bonneville Power Administration (BPA) and the interconnected system in the Western United States (Hydro, 2000). These interconnections offers the opportunity of trading electricity to BC Hydro but at the same time it makes the reservoir operations problem more complex as it has to incorporate the profit maximization from electricity trade. The complexity of a multi-purpose and multi-reservoir system such as the BC Hydro system can be represented by optimization and/or simulation models that determine the 3 release decisions. Simulation models describe the behavior of the system for a given scenario and assess any changes resulting from alternative scenarios while optimization models systematically provide optimum solutions for specific objectives and a set of constraints. At BC Hydro, several simulation and optimization models are used for planning and operation purposes. BC Hydro developed Hydro Simulation Model (HYSIM) for long term planning studies. The model can be used for single or multiple load year studies with multiple years of flow data, or water years. Loads are met by dispatching the available generation resources particularly using water value tables, calibrated by heuristics in a trial-and-error process, for marginal values of water that are used for the operation of reservoir storages of large hydro. A special logic is used for implementing a set of constraints for the Columbia River operations, including the Columbia River Treaty requirements. A Short-Term Optimization Model (STOM) was developed by Shawwash et al. (2000) which is used by BC Hydro to determine the optimal hourly generation and trading schedules while satisfying system demands. The STOM model was modified by the research team at the University of British Columbia and BC Hydro to develop the Generalized Optimization Model (GOM) having the capability of handling longer time periods ranging from hourly to monthly time-steps. GOM was modified to include the Columbia River Treaty operating plans and regulations and the new version was named the Columbia River Treaty Model (CRTM). This study extended the Columbia River Treaty Model (CRTM) to deal with the various Columbia River Treaty and non-power related issues in the Columbia River and it used the CRTM model to investigate the potential impacts of incorporating these non-power issues on BC Hydro‟s generation system. 4 1.2 PROBLEM STATEMENT The Columbia River is the 15th longest river in North America and the 4th largest river as measured by the average annual flow (Engineers and Administration, 2009) and it is the most productive hydropower generating river in North America. Hydroelectric development of the Columbia River in the U.S. started in 1932 and continued to grow to facilitate power generation, navigation, flood control, and irrigation. Unfortunately, all the projects in the U.S. could not provide adequate flood control due to their limited storage capacity. The limited storage capacity and the large variability of streamflows resulted in significant floods which in turn, motivated the U.S. authorities to search for a coordinated development plan between Canada and the U.S. that could deal with the Columbia River basin flooding and at the same time meet the region‟s ever increasing demands for energy. This led both countries to sign the Columbia River Treaty (CRT) in 1961 and ratified in 1964. Under the treaty agreement, Canada built three large dams: Duncan (1968), Hugh- Keenleyside (also known as Arrow) (1973) and Mica (1973) to provide 15.5 million acre-feet (Maf) of water storage and the U.S. built the Libby dam in 1973. In addition to flood control and power generation, the new CRT dams also provided other river regulation benefits such as additional power generation by the downstream projects. There are several primary uses of water of the Columbia River system: flood control, fish migration, fish and wildlife habitat, electric power generation, navigation, irrigation, recreation, water supply and quality control, and cultural resources. Most of the dams that were built in the Columbia River basin have been used successfully to satisfy the majority of these uses (System, 2001). Due to the inevitable effects of the Columbia River dams on the ecosystem specifically on the fishes, public concerns have been rising on this issue over the last two decades. 5 As a result, the Department of Fisheries and Oceans Canada (DFO) and the U.S. Fish and Wildlife Service (Service) have studied the impacts of hydroelectric dams on fish resources in the Columbia River basin. In a study conducted by DFO in 1991 the overall impact of the operation of all existing 46 hydroelectric dams on both anadromous and inland fisheries resources was reviewed. According to the study, Rainbow Trout, Dolly Varden (Bull Trout), Mountain Whitefish and Kokanee were considered to be the most common fish population in the Columbia River basin in Canada. The study also listed a number of negative impacts of hydroelectric dams on the fish population including: restrictions on spawning migration and mainstem spawning, rearing due to flow fluctuations, low flow, low/high water temperatures, stranding and exposure of eggs due to fluctuation of water levels, and mortality due to passage through powerhouse turbines (Hirst, 1991). On the other hand, Service reviewed the Biological Assessment (BA) and the National Environmental Policy Act (NEPA) reports and provided opinion of the effects of their proposed action on two particular listed fish species: the endangered Kootenai River White Sturgeon (Acipenser transmontanus); and the threatened Bull Trout (Salvelinus confluentus). Recent studies confirmed the effects of impoundment on nutrient availability and productivity in these lakes (Matzinger el al. 2007). Service recommended some guidelines to improve fisheries resources based on extensive studies. They have also identified several activities including water diversions, dams, timber extraction, mining, grazing, agriculture, introduction of non-native fishes, channelization, modification of habitat and the hydrograph, human activities such as side-channel habitats removal, water chemistry changes, and a loss of nutrient inputs from flooding as the main causes of alteration or disruption to the Bull Trout and White Sturgeon species in the Columbia River basin (Service, 2000). 6 Usually in reservoir operations planning, the release policies are determined based on the maximization of the expected value of the systems resources over the planning period ensuring that the firm domestic demands are met and the value of stored water at the end of time horizon is maximized. The general technique that is typically used is to develop an optimization model with an objective to be maximized or minimized. However, due to multi-purpose nature of the Columbia River system a multi-objective optimization technique is believed to be the most suitable one. Nowadays, non-power related issues have gained significant importance and have received considerable attention from both the Federal and Provincial Governments indicating that it must be addressed in the planning process. As a result, satisfying the non-power constraints and requirements is ranked as the highest priority to the decision makers these days. 1.3 GOALS AND OBJECTIVES The main goal of this research is to develop a multi-objective optimization model which can be used as a decision support tool for operations planning of the Columbia River Treaty Plants at BC Hydro. The model should be able to: Provide optimal operations planning for the BC Hydro major reservoir system while considering the Columbia River Treaty operating criteria and constraints. Deal with different multi-objective functions with different priority and associated weights. Satisfy some of the Non-Power requirements that were agreed upon by both of the U.S.A and Canada Entities. Have the capability to assess the trade-offs between multiple objectives. Several objectives were identified to make it possible to achieve these goals: 7 1. Obtain sufficiently in-depth knowledge and clear understanding of multiobjective optimization methods and techniques in general and the BC Hydro‟s operations planning models with focus on the Columbia River Treaty Model (CRTM). 2. Carry out a comprehensive literature review on different reservoir optimization techniques with a main focus on multi-objective optimization procedures and techniques. 3. Formulate a multi-objective optimization model that can address different nonpower requirements while satisfying the CRT operating plans and regulations and which can deal with user‟s assigned priorities and weights to different nonpower objectives using the Goal Programming (GP) technique. 4. Perform a number of case studies to test the multi-objective GP model and implement it for the optimization of BC Hydro‟s major reservoir system for the Columbia River Treaty operations. 1.4 ORGANIZATION OF THE THESIS This chapter presented an introduction of the problem, motivation for the research work, and defined the goals and objectives of this research. Chapter 2 reviews the literature on different reservoir optimization techniques. Chapter 3 presents an introduction and background information on the Columbia River Treaty and non-power requirements which were agreed upon by both the U.S. and Canadian entities. Chapter 4 presents the details of the multi-objective optimization technique used in this research and algorithm used in this research. Chapter 5 presents the details of GP model development. Chapter 6 includes application of the developed model on different case studies and presents sample results from these studies. Finally, Chapter 7 lists the research conclusions and recommendations for future research work. 8 CHAPTER 2: SURVEY OF THE LITERATURE 2.1 BACKGROUND Due to the complexity, uncertainty and dimensionality (Datta, 1993; Labadie, 2004; Yeh, 1985; Mousavi et al., 2004) of water resources systems, particularly multi-reservoir systems, numerous studies have been conducted to plan, design, and manage these systems. For many reservoir systems, it can be significantly complicated to balance a number of competing objectives if they require optimization over one or many objectives as they could involve significant number of decision variables and system constraints. To choose the appropriate approach to handle this type of problems becomes very crucial, and many optimization techniques have been developed to overcome the problem of dimensionality (Yeh, 1985). In general, optimization techniques can be grouped into three main categories: deterministic, stochastic, and heuristic models (Abdalla, 2007). i. Deterministic models: Deterministic models do not address uncertainty in the optimization process. Types of deterministic models include: Deterministic Linear Programming (LP), Deterministic Integer, Mixed-Integer and Non-Linear programming. ii. Stochastic models: Stochastic models consider uncertainties that are capable of affecting the performance of the system in future. This can be captured either implicitly where optimization is done over series of random variables assuming perfect foresight; or explicitly where the optimization models deal directly with probabilistic random variables (Abdalla, 2007; Datta, 1993). Examples of stochastic models are Stochastic LP, Stochastic Dynamic programming (SDP), 9 Stochastic Dual Dynamic Programming and Stochastic Chance-Constrained Programming. iii. Heuristic models: Heuristic models include Genetic Algorithm (GA), Artificial Neural Networks, Fuzzy Programming, Tabu Search and so on. Since all the data inputs used in this research are deterministic, the literature review will primarily focus on the deterministic optimization methods with a brief review of other optimization methods. 2.2 2.2.1 OPTIMIZATION TECHNIQUES LINEAR PROGRAMMING Linear programming (LP) is one of the most robust optimization techniques used in the reservoir operations planning. It can solve non-linear problems by linearization or piecewise linearization of non-linear equations or by iteration under certain assumptions and situations. Characteristically, the planning objectives are function of storage and release during the planning horizon. In most of the reservoir optimization problems, the planning objective is either to minimize the cost of operating a reservoir while satisfying all constraints or to maximize the net revenue resulting from operating a reservoir (Yeh, 1985). The major advantages of LP models are: i) capability of solving large-scale problems, ii) assurance of convergence to a global optima, iii) no initial guess is required by the user; iv) capability of performing sensitivity analyses, v) ease of problem formulation, and vi) readily available efficient software packages e.g., LINDO, LINGO, CPLEX, MINOS (Murtagh and Saunders, 2003), MOSEK (Andersen et al., 2009) and GLPK (GNU LP Kit). On the other hand, the major disadvantages of LP model are the restriction of using linear and convex objective functions and linear constraints (Rani and Moreira, 2010). 10 Piekutowski et al. (1993) formulated large scale linear programming algorithm to determine optimal generation schedules and also to examine export and import of the Tasmanian system under a proposed DC interconnection with mainland Australia. They used minimization of the value of energy generated by releasing water through the turbines and spilled energy as the objective function and solved the model using commercially available linear programming package. The optimal schedules generated by the LP model showed significant improvement of stored potential energy, compared to historical operation record, in a range of 3% to 5% and annual energy savings were estimated to be of 0.3% to 0.4%. The model also provided unit constrained incremental costs which provide a priority order of short-term economic dispatch. Shawwash et al. (2000) developed the BC Hydro Short Term Optimization Model (STOM) which maximize the value of BC Hydro resources by maximizing revenues from spot transactions in the U.S. and Alberta electricity market but at the same time satisfying the hourly load and other constraints. The estimated benefits of using this model by BC Hydro are amount to 0.25-1.0% and the piecewise linear optimization model provides valuable sensitivity analysis data. 2.2.2 INTEGER AND MIXED-INTEGER PROGRAMMING In most cases, it is not always possible to maintain all the linearity assumption of variables and some variables must be formulated as integer which gives importance to Integer or Mixed-Integer programming problems. In Integer programming, the decision variables are integer values whereas in Mixed-Integer programming some of the variables can be integers while others are real values. Mixed-Integer programming can be successfully applied to unit commitment problems in hydro power generation planning (Kerr and Read, 1997). 11 Tang (2007) developed a linear mixed-integer optimization technique to solve the maintenance scheduling problem for large scale hydro systems and determined the best „timing‟ for each unit outage in the system. He found that it “is very difficult to generalize one standardized approach to effectively handle this complex and large scale problem.” and he focused his research on two main points. “One focused on decreasing the number of possible binary variables in the model. The other was to find an appropriate algorithm that could approximate and reasonably simplify the computational process and to transform the nonlinear constraints into linear ones.” (Tang, 2007). 2.2.3 DYNAMIC PROGRAMMING Another powerful optimization technique is Dynamic Programming (DP), which is one of the most popular methods used in reservoir operations (Labadie, 2004). DP can decompose the original problems into different sub-problems that can be solved consecutively in each time period. One of the most attractive features of DP is that it follows a serial or progressive directed network to solve an operation or a planning problem (Hastings, 1973). It also has the capability of handling non-convex and noncontinuous functions. Nandalal and Bogardi (2007) identified the limitations of DP methods, particularly in reservoir system operations. One of the major limitations lies in the fact that the computational time is a function of the number of state variables which is referred as the „curse of dimensionality‟ (Bellman, 2003). To alleviate this limitation, various enhancements of DP algorithms have been developed including: coarse grid/interpolation methods, dynamic programming with successive approximation (DPSA), and incremental dynamic programming or discrete differential dynamic programming (DDDP) (Labadie, 2004). 12 2.2.4 NON-LINEAR PROGRAMMING Reservoir operation problem is traditionally a non-linear optimization problem and nonlinear programming (NLP) has been used to solve it. However, it has not gained popularity due to slow optimization procedure and possibility of getting inferior and suboptimal solutions. The most powerful and widely used NLP methods are: successive linear programming (SLP), successive quadratic programming (SQP), augmented Lagrangian method, and the generalized reduced gradient method (GRG) (Labadie, 2004). In 1981, Loucks et al. (1981) developed a linearization procedure for non-linear terms in an optimization model and using this idea Grygier and Stedinger (1985) developed and applied the Successive Linear Programming (SLP) algorithm to solve the reservoir operations problem. Reznicek and Simonovic (1989) used the SLP technique for reservoir operation at Manitoba Hydro and compared the developed algorithm with the existing one and they showed significant improvement in the release policy. Comparing the various methods of the NLP (e.g., SLP, GRG and SQP), Hiew (1987) concluded that SLP is the most efficient method, however, one of the disadvantages of NLP is that despite the availability of linear programming solvers, the method is not guaranteed to converge to the optimal solution (Bazaraa and Shetty, 1979) as it might yield sub-optimal solutions as previously stated. 2.2.5 EVOLUTIONARY AND HEURISTIC ALGORITHMS Evolutionary and heuristic search methods are inspired by bio-systems and are gaining popularity by researchers in optimization of reservoir operations. They have the capability of dealing with non-convex, non-linear, multi-objective, discontinuous, discrete, stochastic and large scale problems, however the global optimality is not 13 guaranteed (Shabani, 2009). Genetic algorithms (GA), Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO), Simulated Annealing (SA), and Tabu Search (TS) methods are the most commonly used evolutionary methods in reservoir operation and management problems. Recently ACO has gained popularity among researchers in the field of reservoir operation. The method “was inspired by the behavior of ants in finding the shortest route between their nest and the food source” (Abdalla, 2007). Kumar and Reddy (2006) applied Ant Colony Optimization technique to Hirakud reservoir, a multi-purpose reservoir system located in India by taking into consideration a finite time series of inflows with several reservoir volume class intervals, and estimating the reservoir release for each period with respect to a pre-defined optimality criterion. They evaluated the performance of the developed model to compare it with a Genetic Algorithm (GA) and found that ACO‟s gives a better performance and yields higher annual power production. They also observed that ACO outperforms GA particularly for long term reservoir operation. Afsar and Moeini (2008) applied ACO methods for the large scale optimization problem and used it to solve the problem of hydropower operation of “Dez” Reservoir in Iran and showed that their method optimally solved large scale reservoir problems where the conventional methods (e.g., Weighted Sum approach and Epsilon constraint method) cannot even find a feasible solution. 2.2.6 MULTI-OBJECTIVE OPTIMIZATION Reservoir operation in real life involves many conflicting and competing objectives, such as irrigation, flood control, water supply, hydropower production, and environmental considerations. Numerous methods of multi-objective optimization exist. Collette and Siarry (2003) classified them into five categories: scalar methods, interactive methods, fuzzy methods, methods which use a metaheuristic, and decision aid methods. The five 14 categories can be further grouped into three families of multi-objective optimization methods (Collette and Siarry, 2003), mainly according to their use in the decision making process: i. A priori preference methods, where the decision maker characterizes the tradeoff to be applied before the optimization process begins. Scalar methods are in general included in this group. ii. Progressive preference methods where the decision maker can improve the tradeoff while the optimization process is in action. Interactive methods fall into this group. iii. A posteriori preference methods where the decision maker picks the optimum solution after finishing the optimization process by analyzing the output solutions. In this method, a tradeoff surface can be generated at the end of the optimization process. Other than these categories, algorithms using a combination of these groups also exist. Ko et al. (1992) conducted a comprehensive study on available methods of multiobjective optimization in 1992. Three of the most used methods are weighted-sum-ofobjective method, epsilon constraint method, and the goal programming (GP) method. The weighted-sum-of-objective method is the “naive approach” to multi-objective optimization (Coello and Christiansen, 1998). In this method, multiple objectives are transformed into a single objective by assigning weights to each objective functions. The new single objective function becomes the weighted sum of all objective functions. Though this method is very efficient from an algorithmic point of view, it has some limitations which restrict the use of the method in many cases such as: Requirement of conversion of all objective function into one type for mixed optimization problem (e.g., Min-Max problems). 15 Uniformly distributed set of weights does not guarantee a uniformly distributed set of Pareto-optimal solutions. Different set of weight vectors cannot generate different Pareto-optimal solutions at all time. Multiple minimum solutions may exist for a specific weight vector which represents different solutions in the Pareto-optimal front and could be wasting the search effort. This method cannot discover solutions which are hidden in concavities. Another type of multi-objective optimization method is the epsilon (Є) constraint method which is also used robustly. In this method, an objective is selected and optimized while other objectives are considered as constraints and this process is repeated until all objective functions are transformed into inequality constraints (Collette and Siarry, 2003). This method is applicable for non-linear, dynamic problems but can be sensitive to the number of objectives considered (Ko et al., 1992). Some of the disadvantages of this method are: Solution is largely dependent on the selection and discretization of the objective function range as it must be within the minimum and maximum value for each objective function. It requires more iteration depending on the number of objective functions in the model. Goal programming (GP) is another multi-objective optimization method which has been widely used in water resources systems. When it was first used, GP was considered as another extension of LP models but eventually it is now recognized as a stand-alone problem solving methodology (Schniederjans, 1995). 16 A number of multi-objective optimization methods used in reservoir operation planning are reviewed in this research. Yoo et al., (2009) presented an application of weighted LP model to a multipurpose reservoir to maximize hydropower generation and they showed the applicability of the weighted method to multi-objective optimization. Liang et al. (1996) did a comparison study between the constraint method and the method of combined stochastic and deterministic modeling (CSDM). They used two conflicting objectives: reliability of annual water supply maximization and hydropower production maximization. Comparing the two methods, they found CSDM works better and provides more hydropower production and higher reliability of annual water supply than the constraint method (Liang et al., 1996). Barros et al. (2003) used NLP, LP and SLP model to solve a large scale multi-objective hydropower system in Brazil which includes 75 hydropower plants with an installed capacity of 69,375 MW. They used the SLP because of its lower computation time and storage requirements and readily available software package to solve LP models. Weighted programming and epsilon constraint programming were used to model multiobjective programming. The authors evaluated the performance of these three models and concluded that SLP model can be used for planning purposes similar to the LP model but with fast convergence whereas the NLP model can provide the most accurate and suitable results particularly for real-time operations. Lai et al. (1994) used compromise programming to solve the multi-objective problem in a water resource system. The algorithm TOPSIS was based on the idea of having shortest distance from the Positive Ideal Solution (PIS) and the farthest from the Negative Ideal Solution (NIS) for any chosen alternative which confirms that a decision is not only making as much profit as possible but also having lowest possible risk. Applying this algorithm for multi-objective optimization problem, they found satisfactory results in compare to other methods but due to the limitation of compensatory operators 17 and membership functions they could not get any better result which they recommended for future studies. Application of multi-objective optimization technique coupled with hydrologic model was developed by Wang et al. (2010) where they combined a global optimization system with a distributed biosphere hydrologic model coupled with reservoir routing model. The integration of these models resulted in significant reduction of peak flood at downstream control point and increased reservoir levels after the simulation period which can be beneficial for future water supply when they applied the model for Hoa Binh Reservoir in China (Wang et al., 2010). Heuristic models, including Genetic Algorithm (GA), have been recently used in multiobjective reservoir operation (Labadie, 2004). Although they cannot guarantee global optimality, robustness of GA makes it a strong optimization technique. The key feature of multi-objective genetic algorithms (MOGAs) is the generation of Pareto-dominant solutions which are used to discriminate non-dominated solutions in a search space. Kim et al. (2006) used a popular genetic algorithm to optimize the multi-objective multireservoir system in the Han River basin and compared alternative reservoir operating plan with historical release and storage and showed that the GA model can efficiently generate well distributed Pareto–optimal solutions which can help the decision maker to select the best solution (Kim et al., 2006). Uncertainty can play a vital role in reservoir operations problem and can make the complex system even more complicated. Generation of Pareto-optimal solutions by optimization methods are crucial in water resources decision making and these methods can provide significant benefit when evaluations of different alternatives are highly subjective. In this regard, fuzzy set theory can be appropriate (Simonovic and Verma, 2008). Simonovic and Verma (2008) used fuzzy methods to generate fuzzy 18 Pareto-optimal solutions for multi-objective problem with triangular fuzzy weights. After comparing the results from Pareto-optimal solution generated by using fuzzy triangular weights with crisp (non-fuzzy) weights, they observed that earlier one gives wider range of choices for selecting the most preferred solution. 2.3 GOAL PROGRAMMING (GP) MODELS After the earliest development of LP method in 1947 by a team of scientists, led by George Dantzig, under sponsorship of the U.S. Air Force project SCOOP (Scientific Computation of Optimum Programs), LP has been used extensively in almost every field of optimization and goal programming (GP) emerged from LP in 1950s. Though it was developed as an extension of LP model, GP gained considerable and pervasive attention since mid-1970s (Ignizio, 1985). Since then many papers, research articles, textbooks have been devoted in part or totally to the subject of GP in almost every field of professional application particularly in the Operational Research, Management Science, and Single and Multi-criteria Decision Analysis (Schniederjans, 1995). A number of different GP methods have been developed and among them weighted GP, preemptive GP and minmax GP are the most common. The main advantages of GP over other methods of optimization are: only one dimensional information (physical phenomena such as storage corresponding to water intake levels, spillway elevations, flow for irrigation demands or flooding, etc.) are needed whereas other methods require two dimensional information; the “Best” solutions refer to minimize the deviations from the set of targets or maximize the attainment of the set of goals; and this way the decision maker is not forced to assign numerical weights or penalties to the flows or storage zones so that no, or very general, economic analysis will be required (Can and Houck, 1984). 19 One of the best ways to incorporate different objectives into an optimization model is the priority-based constraint method which can solve an optimization problem given the priority for a number of constraints. The Tennessee Valley Authority (TVA) and the University of Colorado have developed a new generalized river basin modeling tool, RiverWare, which is capable of representing a diverse and complex system and operating policy details for a wide range of applications. In RiverWare, three simulation methods are provided: Pure Simulation, Rule-based Simulation and Optimization. An important requirement for specifying multiple objectives was that priorities need to be assigned to the objectives rather than relative weights which will avoid the subjective determination of proper weights for non-commensurate objectives such as weights that can be difficult to determine, difficult to justify, and their relative importance is unclear to both modelers and other interested parties. RiverWare‟s optimization solution method meets the user‟s priority requirements or preferences by solving the system for each prioritized set of objectives, starting with the highest priority and advancing to lower priority objectives utilizing a linear pre-emptive goal programming technique (Zagona and Magee, 1999). If the objective is included in the form of a constraint, the software translates it to an objective to minimize the deviation of the solution from the constraint limits (Zagona et al., 2001). The pre-emptive goal programming method allows some flexibility in expressing policy constraints as objectives and avoids the practical problems associated with assigning and justifying values of relative weights (Schultz, 1989). The TVA study used preemptive goal programming model as part of a weekly model because its: acceptability of deterministic optimization for short-term operational modeling, sufficiently realistic solution capability of GP model, and efficiency and robustness of GP model in daily reservoir operations. RiverWare maximizes constraints satisfaction as compared to other models which minimize deviation of the variables from a preset limits and 20 RiverWare‟s method enhances systems performance. Pre-emptive GP confirms that the optimal solution of a higher priority goal is not sacrificed while it optimizes a lower priority goal and this is an important characteristic of the methodology (Eschenback et al., 2001). Gilmore et al. (2000) used pre-emptive goal programming to model the Colorado River Basin which is operated by the treaties, compacts, laws and court decisions. Although the existing models (The Colorado River Simulation System (CRSS) and the 24 Month Study) are able to simulate different operational choices in this realm, manual trade-off analysis is required after each run. However, Optimization techniques are a natural choice for access to this information, as well as for quick selection of the optimal from many policies. The authors developed the goal programming formulation to match closely the simulation results of the existing models and evaluated the effect of introducing alternative types of policy flexibility: deviation from rule curves, varying the timing of flood control releases, and varying the timing of meeting demands (Gilmore et al., 2000). Linearization is very common in optimization modeling to convert the nonlinear or polynomial problems into linear problem and piecewise linearization is an important technique for solving nonlinear programming problems. GP method has the ability to deal with piecewise linear function with appropriate linearization of the constraints. Chang (2002) proposed a modified GP technique to deal with piecewise linear function and concluded that the modified method is more efficient than the classic GP method as it uses lower number of auxiliary constraints and it is applicable to nonlinear problems. Goal programming requires the Decision Maker (DM) to set an aspiration level for each goal which can be a very difficult task as there are several of uncertainties in nature that must be considered: 21 Consideration of economic, environmental, social and technical issues. Selection of different alternative based on quantification of possible sequences. Uncertainties associated with the performance of alternative (Keeney and Wood, 1977). To deal with these uncertainties, different methods of fuzzy goal programming were introduced and gained widespread appreciation. Chen and Tsai (2001) presented a fuzzy GP method which considers different relative importance and priorities of goals similar to preemptive GP but in fuzzy environment and showed the computational superiority over other GP methods. Hu et al. (2007) also developed a fuzzy GP methodology to work with different priorities. Their proposed model gives the Decision Maker (DM) more flexibility to represent the information in a more direct way when they are unable to express it precisely unlike the method proposed by Chen and Tsai (2001) where the added constraints are too strict which may result in infeasible solutions for highly desirable fuzzy goal and it also requires accurate and precise input from DM for the aspiration level of each goal. Chang et al. (1997) applied fuzzy GP method for optimal land development of the reservoir watershed. Loganathan and Bhattacharya (1990) presented an application of fuzzy goal programming in reservoir operations. 2.4 SUMMARY The survey of literature provides a brief overview of different modeling techniques with particular focus on linear and multi-objective problem solving methods. This survey shows that various optimization approaches are being tried by researchers in the field of reservoir operation. From this literature review, it can be concluded that goal programming technique is the suitable method to solve multi-reservoir and multiobjective problem of this research because of its robustness, unique characteristics to 22 deal with different priorities and availability of suitable solvers to solve the optimization problems. In Chapter 4, the main philosophies and computational aspects of Goal Programming method is described thoroughly. 23 CHAPTER 3: THE COLUMBIA RIVER TREATY (CRT) 3.1 COLUMBIA RIVER The Columbia River is one of the greatest natural resources in the Pacific Northwest and is the most hydro-power generating river in the North America. The total drainage area of the Columbia River is around 567,000 square kilometers (219,000 square miles) of which only 15 percent is in British Columbia, Canada and rest of the watershed is within seven western U.S. states: Washington, Oregon, Idaho, Montana, Wyoming, Nevada, and Utah (Figure 3-1). Although 15% of the area is in Canadian territories it supplies around 38 percent of the average annual volume and contributes about 50 percent of the peak flood waters. The Columbia originates at the Columbia Lake on the western slopes of the Rocky Mountains in British Columbia. The river flows from Canada to the U.S. and discharges into the Pacific Ocean near Astoria, Oregon. The total length of the river is 1954 kilometers which makes it the 15th longest river in North America. Its east and north boundary is the Rocky Mountain while the Cascade Range covers west and the Great Basin covers the south boundary. Within its basin, numerous sub-basins formed by the tributaries of the mainstream river and these all together makes the Columbia River Basin as the predominant river system in the Pacific Northwest. 24 Figure 3-1: Columbia River Basin and Existing Hydropower Plants (USACE) 25 Flows in the Columbia River vary seasonally. Flow in the Columbia River from Canada varies from 396 m3/sec to 15,575 m3/sec at the border before any of the mainstream dams were built (Figure 3-2). Snow fall in the winter forms the largest share of annual precipitation in the Columbia River Basin. Snowmelt during freshet period (May, June, and July) is responsible for about 60 percent of natural runoff in the basin. The average annual runoff in the Columbia River at The Dalles is about 244 billion cubic meters of which 62 billion cubic meters come from Canada. Figure 3-2: Columbia River Streamflows (System, 2001) Several different and competitive uses of the Columbia River water make the system very difficult to manage. Flood control, fish migration, fish and wildlife habitat, power generation, navigation, irrigation, recreation, water supply and quantity, and cultural resources are some of the major uses in the system. Due to large variability of the river flows, flood control is ranked as the highest priority for system operations especially 26 during high runoff years. Fish migration and wildlife and fish habitat uses are very important as the Columbia River is very well known for its Salmon runs and is abundant with wildlife and with both resident fish and anadromous fish. There are a number of hydroelectric projects throughout the Columbia River with total nameplate capacity of over 37,000 megawatts (MW) (Hyde, 2010). These projects provide majority of power to the Northwest region. The Columbia River and its tributary, the Snake River, are also used as navigation channel from the Pacific Ocean to Richmond, Washington and Lewiston, Idaho. Agriculture plays an important part in the Columbia River water uses and about six percent of the water from the basin is diverted for agriculture use. Columbia River and its lakes are also important for recreation uses: boating, sport angling, swimming, hunting, hiking and many other uses. Although municipal and industrial water supply from the basin is not significant, it must be accounted for in system operation. Columbia River basin is also the witness of ancient culture i.e., Indian cultures which also must be addressed in system operation. 3.2 HISTORY OF THE COLUMBIA RIVER TREATY The first ever hydroelectric project in the Columbia River is the Rock Island Dam which was constructed in the U.S. in 1932. After one year, the U.S. government began to construct the Bonneville and the Grand Coulee dams. Upon completion of these large scale projects started to provide low cost electricity a number of manufacturing industries were built in the region in support for World War II efforts. The Northwest region also faced rapid development during post-war period and this has motivated the construction of a numerous dams in the Columbia River mainstem and its tributaries. These projects, unfortunately, were not capable of storing a large amount of water to protect from flood which caused devastating damages in 1948 from Trail, BC to Vanport, Washington. That flood completely destroyed Vanport, the second largest city 27 in Oregon at that time and was the home of 35,000 people. The flood caused more than 50 deaths and displaced around 30,000 people from their homes. Before the flood in 1944 Canada and the U.S. requested the International Joint Commission (IJC), which was formed in 1909 under the Boundary Waters Treaty, to determine beneficial uses of Columbia River water. The 1948 flood triggered the necessary action and raised the importance of coordinated actions from both Canada and the U.S. The Columbia Basin study, conducted by IJC took 15 years and studied a number of different dam sites in the basin and developed alternative plans. During that time, U.S. Army Corps of Engineers (USACE) also updated its master resource plan. Both of these studies recommended developing storage at the upstream portion of the Columbia River and its tributaries (Canadian side) for economic development and flood control benefits as well. Direct negotiations between Canadian and U.S. representatives started in February 11, 1960 to decide on the selection, construction and coordinated use of hydroelectric projects. Within very short time, both countries reached an agreement and on January 17, 1961 U.S. President Dwight D. Eisenhower and Canadian Prime Minister John Diefenbaker signed the Columbia River Treaty (CRT). However, the treaty was only ratified when British Columbia Provincial Government approved the treaty on September 16, 1964. 3.3 MAIN FEATURES OF THE TREATY The Treaty has two corresponding authorities in Canada and the U.S., called the "Entities". The Canadian Entity is appointed by the Canadian Federal Government and is entrusted to the British Columbia Hydro and Power Authority (BC Hydro). The U.S. Entity which was created by the U.S. President includes the Administrator of the Bonneville Power Administration (chair) and the North-western Division Engineer of the U.S. Army Corps of Engineers. 28 The two governments set up a Permanent Engineering Board (PEB) established by the Treaty to monitor and report on the outputs achieved under the Treaty. Furthermore, the board resolves any technical or operational differences that may arise between the two Entities. Some of the main features of the Treaty are: One of the main components of the Treaty was the building of three storage reservoirs in the Canadian portion of the Columbia River to store 15.5 million acre-feet of water. For this reason, Canada built three dams: Duncan (Completed in 1968), Hugh Keenleyside (also referred to as the Arrow) (Completed in 1969) and Mica (Completed in 1973). The U.S. also has the option to build the Libby Dam on the Kootenai River, a tributary of the Columbia River, in Montana according. These four dams more than doubled the storage capacity in the Columbia River Basin. Due to the regulated stream flow resulting from the operation of the Canadian storage reservoirs, the hydroelectric facilities in the U.S. can now be operated more efficiently and this was the basis of the downstream power benefits calculation. Both the U.S. and Canada are sharing equally the downstream power benefits that will be generated in the U.S. resulting from operation of the Canadian storage. Canada received a lump sum of the $64.4 million (U.S.) from the U.S. for one half of the present worth of expected future flood control benefits in the U.S. to September 2024, resulting from operation of the Canadian storage. In the Treaty, the U.S. has an option of requesting the evacuation of additional flood control space above that specified in the CRT, for a payment of $1.875 million (U.S.) plus power losses for each of the first four requests for this "on29 call" storage for the first four calls. No requests under this provision have been made to date. Both Canada and the U.S. have the right to make diversions of water for consumptive uses. If there is any differences arise under the Treaty that cannot be resolved by the two entities then these differences would be referred to PEB. If PEB fails to resolve that issue, then it will request the respective government to forward this issue to International Joint Commission (IJC). There is no end date of the Treaty. It will remain in force for at least 60 years from its date of ratification, 16 September 1964, after which either Government has the option to terminate most sections of the Treaty if a minimum of 10 years‟ advance notice has been given. 3.4 THE COLUMBIA RIVER TREATY PROJECTS According to the provision of the Treaty, Canada built three dams in the upper reaches of the Columbia River: Duncan which started operation in 1967, then Keenleyside Dam in 1968 and Mica Dam in 1973. Canada built Mica Dam higher than required by the CRT which increased its storage capability by up to 5 Maf and at the same time its power-generating capacity. Mica Dam was the only dam that included a powerhouse. All other Canadian Treaty projects were serving as flow regulating reservoir only. After the completion of the Treaty projects, BC hydro and others developed the Kootenay Canal and other projects on the Kootenay River (1975), a large run-of-river project at Revelstoke (1984) and in 2002, a canal and powerhouse at the Keenleyside dam, called Arrow Lakes Hydro project. The Duncan Dam is still a pure storage project and currently does not have a power generation facility. 30 The U.S. also built the Libby Dam on the Kootenai River in Montana in 1872 according to the provision of the Treaty. It has 90 miles long reservoir (Koocanusa Lake) of which 42 miles extends into Canada. It is providing additional 5.0 Maf of active storage with a powerhouse, flood control, and other benefits. The characteristics of the Treaty projects are shown in Table 3-1. Table 3-1: Characteristics of the Treaty Projects (Hyde, 2010) Mica Arrow Duncan Libby 8108 mile2 14093 mile2 925 mile2 9070 mile2 (21000 km2) (36500 km2) (2396 km2) (23491 km2) 168 mile2 204 mile2 28 mile2 73 mile2 (435 km2) (528 km2) (72.5 km2) (189 km2) Max reservoir 605 ft 171ft 127 ft 370 ft depth (184.1 m) (52.1 m) (38.7 m) (112.8 m) 7.0 Maf 7.1 Maf 1.4 Maf 5.0 Maf Basin Area Reservoir Area Treaty Storage Non-Treaty Storage Powerhouse size 3.5 3 (8.63 km ) Up to 4.5 Maf (Under negotiation) 1792 MW 3 (8.76 km ) Under negotiation 180 MW 3 (1.73 km ) (6.14 km3) None None 0 MW 600 MW THE CRT BENEFITS The direct benefits of the Columbia River Treaty in both Canada and the U.S. are: Power benefits: By regulating streamflows into different periods when demand for power is high, reducing spill releases, maintaining higher reservoir levels, 31 and supplementing low inflows with releases of up to 15.5 Maf of Canadian storage and 5.0 Maf of Libby Storage, provide power benefits to both the U.S. and Canada. Treaty operation also increases dependable capacity and firm and non-firm energy at downstream projects in Canada and in the U.S. Flood Control benefits: Treaty operation significantly reduces the flood damage in both countries. Before the treaty projects, the Columbia River Basin did not have enough storage capacity to cope with the large variation in seasonal streamflows of the Columbia River. Treaty operation required Canada to provide 15.5 Maf storage and additional 5.0 Maf from Libby which reduces the peak flow down to 600 kcfs (16990 m3/s). The U.S. Army Corps of Engineers estimated flood damage reduction in 1972, 1974, and 1997 by about $260, $306, and $379 million respectively due to the Columbia Basin Reservoir regulation (Hyde, 2010). Other benefits: In addition to power and flood control benefits, CRT provides other indirect benefits and development. For example, the Kootenay Canal Plant, Revelstoke and Arrow Lake Hydro project in Canada were feasible due to the streamflow regulation by the Treaty and in the United States, the Grand Coulee, the third powerhouse and expansion of many downstream projects were possible due to the Treaty. 3.6 i. THE CRT OPERATING PLANS Assured Operating Plan (AOP) The U.S. Entity and Canadian Entity develop Assured Operating Plan (AOP) to guide the Canadian Storage operation to prevent flood damage in both Canada and the U.S. in accordance with the terms of the Treaty. The goal of this operating plan is to reduce the high flows to non-damaging levels and regulate large floods as much as possible. 32 The CRT requires the Entities to prepare an AOP annually for Canadian Storage and also to determine the Canadian Entitlement amounts for downstream power benefits. The AOP is designed to achieve optimal power and flood control for both U.S. and Canada and is prepared for the six succeeding operating year. These optimal operations are based on firm and non-firm energy capacity but do not include any nonpower requirements (e.g., Fisheries and recreation). Both countries sign the AOP and it is then reviewed by the Permanent Engineering Board (PEB). PEB ensures that the CRT terms and objectives are satisfied and reports their recommendations to both Entities. ii. Assessment of Downstream Power Benefits Based on Pacific Northwest (PNW) load and actual thermal installations, downstream power benefits are calculated but it does not represent other actual storage and power systems operation. In reality, the Canadian Entitlement does not reflect or adjust actual power benefits. It is based on the operation of a theoretical U.S. Pacific Northwest Hydro-thermal power system with operating criteria from the Assured Operating Plan. The Canadian Entitlement to the downstream U.S. hydro power benefits is 50 percent of the increase in downstream energy and capacity in the U.S. in excess to those specified by the Canadian Treaty storage. The Base system consists of all the major projects that existed when the CRT was signed in 1961 plus projects under construction or planned on the main stem of the Columbia River. The Energy Entitlement is 50 percent of the increase in the 30-year (August 1928 to July 1958) average sum of firm hydro energy (from the critical streamflow period), the non-firm hydro which can replace the thermal power required to meet the demand in the Pacific Northwest Area and 40 percent of the remaining non-firm energy (Hyde, 2010). On August 13, 1964 the Canadian Entitlement and Purchase Agreement (CEPA) was signed and Canada sold its entitlement to downstream power benefits (Canadian Entitlement) to the Columbia Storage Purchase 33 Exchange (CSPE - a consortium of U.S. utilities) for 30 years which is expired on April 1, 2003. Now all Canadian Entitlement has reverted to British Columbia provincial ownership and is being either delivered to the Canada-U.S. border or sold directly in the United States. iii. Detailed Operating Plan (DOP) The CRT also allow to prepare a Detailed Operating Plan (DOP) just prior to the beginning of the next operating year to consider fisheries, recreation, and other benefits which are not addressed in the AOP. DOP is prepared to make more advantage to both the U.S. and Canada than the AOPs that were prepared only for flood control and power benefits. iv. Treaty Storage Regulation (TSR) Studies The Treaty Storage Regulation (TSR) study is the coordinated system hydro regulation study which is conducted by the U.S. Entity for the implementation of the rules of the DOP within current operating year. It uses the Upper Rule Curve (URC), the Energy Content Curve (ECC), and different Critical Rule Curves (CRC) and gives priority to flood control, firm power, refill, and secondary power. TSR considers the entire Columbia River Basin in the modeling process (Shabani, 2009). 3.7 SUPPLEMENTAL OPERATING AGREEMENTS (SOP) The Columbia River Treaty Operating Committee, empowered by the two Entities can prepare additional operations criteria for additional mutually beneficial results. These additional operations are included into Supplemental Operating Agreements (SOP) which are usually focused on fisheries and environmental issues as well as power benefits and need to be signed by both Entities. The first Supplemental Operating 34 Agreement was signed in 1993 to protect Rainbow Trout downstream of the Arrow Lake Hydro project. Since then a number of different SOPs were signed and implemented. 3.7.1 FALL STORAGE AGREEMENT In September 2009 a Fall Storage Agreement was signed to provide power and nonpower benefits to both the U.S. and Canada for three consecutive years. It is primarily driven by market opportunities which means when the market price of the power is favorable, more power would be generated using the additional storage from Arrow. The agreement allows a total of 485 thousand cubic foot per second-day (ksfd) (13730 m3/sday) additional storage at Arrow from October through Early November. This additional storage will be released starting from December to March in the following year. It can provide some important benefits to Canada: Provide a significant amount of power deliveries from the U.S. which is valued at millions of U.S. dollars. Head gains at Arrow Lakes Hydro can provide millions of dollars because of higher reservoir levels and head gains at Arrow. 3.7.2 This agreement can also benefit Canadian Whitefish operation in March. SUMMER STORAGE AGREEMENT Summer Storage Agreement provides some power and non-power benefits for the U.S. and Canada and was signed in June 2010. It requires shaping of spring flow at Arrow. According to the agreement, a total of 100 ksfd (2830 m 3/s-day) of additional storage at Arrow from June through mid-August is permitted and this storage will be released in mid-August and September. The benefits to Canada from this agreement are: 35 Arrow Lakes summer reservoir level enhancement in June to mid-August which in turn improves summer recreational activities. Provide power deliveries from the U.S. Head gains at Arrow Lakes Hydro due to higher reservoir level. 3.7.3 ARROW FLOW SHAPING AGREEMENT Arrow Flow Shaping Agreement was not signed for any power delivery purpose, only for shaping the Arrow releases. It was signed in July 2007 to smooth high Arrow outflows in late July by utilizing available Non-Treaty storage space. The agreement allowed storing 232 ksfd (6570 m3/s-day) from July 20, 2007 to August 3, 2007 and releasing the stored water from August 11, 2007 to August 21, 2007. The benefits of this agreement to Canada are: Higher Arrow reservoir levels in July and August which improved summer recreational activities. Environmental benefits with smoother flows at downstream of Arrow Lake Hydro project. Head gains at Arrow Lakes Hydro which valued at around four hundred thousand US dollars. 3.7.4 NON-POWER USES AGREEMENT Columbia River is habitat for a number of fish for a long time. In Canada, before Mica Dam was built, the Columbia and Canoe River system habited Mountain Whitefish, Bull Trout (Dolly Varden), Eastern Brook Trout, Rainbow Trout and Burbot. Below the Mica Dam, the resident sport fish before impoundment were Bull Trout, Rainbow Trout, Cutthroat Trout, Brook Trout, Burbot, White Surgeon, and Mountain Whitefish. Rainbow Trout, Bull Trout and Kokanee were found before the Arrow Reservoir was built in the 36 Columbia River. In the downstream of Arrow Lake, Mountain Whitefish and Rainbow Trout were the two most dominant fish species (Hirst, 1991). In the United States, development of hydroelectric projects also adversely impacted the fish population. In the Lower Columbia River, Bull Trout is the most dominant fish species which has declined due to hydro-power dams although the Bonneville, the Dalles, the John Day, and the McNary Dams are equipped with fish passages. All these dams are currently operated to pass juvenile anadromous Salmonids during their migrating season (March 1 through November at the Bonneville Dam; April 1 through November at the Dalles and the John Day Dams; April 1 through December 15 at the McNary Dam). Natural Marine Fisheries Service (NMFS) established the flow objectives at the McNary Dam to reduce the time required by the juvenile Salmonids to migrate through the Lower Columbia River at spring from 220 to 260 thousand cubic feet per second (kcfs) (6230 to 7360 m3/s) and in the summer to 200 kcfs (5660 m3/s). These flow objectives can be met from the Upper Columbia River Dams (Service, 2000). Non-power Uses Agreement was developed to incorporate these fisheries issues into the Columbia River Treaty operation for the period of December to July the following year. The following fisheries requirements are addressed in the Non-Power Uses Agreement: Flow Augmentation (FA): It requires storage of 1 Maf (1.233 km3) from January to mid-April in the Arrow reservoir (behind the Mica Dam) between the Treaty Storage Regulation (TSR) level and flood control rule curve to meet the flow objectives at McNary to help juvenile Salmonids to migrate through the Lower Columbia River. This FA water will be released from the second half of April to June based on their requirement. 37 Whitefish (WF): It also addresses discharge objectives at Arrow during January through March to protect eggs broadcasted by Mountain Whitefish during the period of January 1 to January 21. Trout Spawning (TS): It refers to the certain flow requirement from Arrow during April to June to protect eggs deposited by Trout during April and May. This research objective is to consider and incorporate these three fish requirements in the optimization models used by BC Hydro. For this reason, other fisheries issues in the Columbia River Basin were not discussed. For detailed report on the fisheries issues in the Columbia River Basin the reader is referred to (Hirst, 1991) and (Service, 2000). 3.8 SUMMARY The Columbia River is very dynamic river and provides a significant portion of hydroelectricity to both Canada and the U.S. To provide flood control and power benefit, the Columbia River Treaty was signed between these two countries. In addition to flood control and power benefits, recently environmental and recreational requirements are also taken into account. This chapter provides different features of the CRT and supplemental agreements related to additional power, environmental and recreational benefits. 38 CHAPTER 4: MODELING METHODOLOGY 4.1 INTRODUCTION “Man is a goal seeking animal. His life only has meaning if he is reaching out and striving for his goal” Aristotle 384-322 BC Goal programming is a multi-objective programming method which has been used in various fields, particularly in Operations Research, Management Science, Multi-criteria Decision Analysis, and also in Reservoir operations. It was first introduced by Charnes et al. (1955) where they dealt with executive compensation methods. The term “goal programming” was first introduced in 1961 by Charnes and Cooper. Since then, it has been used extensively and is considered as a robust modeling technique, supported by a wide range of researchers and practitioners who are continuously developing theoretical and practical applications of GP (Aouni and Kettani, 2001). Among the many applications of GP, some are of particular interest including: management of reservoir watershed, solid waste management, management of accounting and financial resources, production, quality control and marketing, human resources, transportation, and agriculture and forestry. The Tennessee Valley Authority (TVA) used GP for reservoir operation (Zagona et al., 2001) which motivated the current research to apply GP to multipurpose reservoir operation at BC Hydro. The following sections present the underlying philosophy of goal programming which is followed by different techniques of GP with a particular emphasis on three main categories: Weighted GP, Lexicographic GP, and MinMax GP. Then different issues which were raised during various applications of GP in different field are discussed. 39 Different practices of GP modeling are also presented in this chapter. For a more comprehensive reviews of goal programming the reader is referred to Aouni and Kettani (2001), Schniederjans (1995) and Jones and Tamiz (2010). 4.2 PHILOSOPHY OF GOAL PROGRAMMING In goal programming, usually the term „goal‟ means a criterion and a numerical level known as the “target level” which the decision maker sets to achieve on a criterion. There can be three principal types of goals in GP models: Type 1- Maximizing goal: This needs to be achieved at highest target level Type 2- Minimizing goal: This needs to be achieved at lowest target level Type 3- Equalizing goal: This needs to be achieved exactly at target level (Jones and Tamiz, 2010) To apply goal programming in any field it is required to deeply understand the underlying philosophy of goal programming. This will ensure that the right choices of variables and corresponding parameters are set. i. Satisficing Satisficing is the primarily underlying philosophy in goal programming. The word satisficing and related verb „to satisfice‟ were originally introduced by American economist Herbert Simon (Simons, 1957). In goal programming, a target level is set and an attempt to reach that target as close as possible. This is an alternative of optimizing philosophy, and it assumes that human behavior is more related to satisficing rather than optimizing as they are more interested and able to reach goals than optimizing each outcome of a decision problem. 40 ii. Optimizing Optimizing in decision making problem refers to determine the „best‟ possible outcome from a set of different possible solutions. In multi-criteria decision making problems, optimized solution are called Pareto Optimal solutions which means it is not possible to improve one decision variable without making worse others. In goal programming, the optimizing philosophy can become important in three different situations: - First, for optimistic goals, which have been set up to its ideal values, the dominant philosophy would be optimizing rather than satisficing. Second, for twosided goals, optimizing and satisficing philosophy will coincide for these goals. Third, for Pareto optimality detection and restoration, the dominant philosophy is the combination of both satisficing and optimizing. iii. Ordering or Ranking This is particularly important for Lexicographic Goal Programming where deviation from the goal is minimized according to a weak order. In Lexicographic goal programming models, the ordering of different goals is based on their importance and it is known by the decision maker. In real life problems, this philosophy sometimes is very important one to consider in goal programming. iv. Balancing In reality, sometimes balance among goals is more important than the overall achievement of goals. Overlooking the balance between achievements of different goals can lead to undesirable results and solutions that are difficult to implement. This balancing philosophy is more dominant in Chebyshev goal programming (MinMax goal programming). 41 4.3 GOAL PROGRAMMING TECHNIQUES There are a number of different goal programming techniques developed since GP was introduced in 1961. The major approaches are: Archimedean GP or Minsum GP or Weighted GP, Non-Archimedean GP or Preemptive GP or Lexicographic GP, and Chebysheb GP or Minmax GP. Other approaches have also been used including nonlinear GP, fuzzy GP, fractional GP but the formulation of these are not distinctly different than single objective forms. 4.3.1 WEIGHTED GOAL PROGRAMMING (WGP) This approach was first presented in the first textbook on goal programming by Charnes and Cooper in 1961. This is similar to the weighting method of multi-objective optimization. Instead of assigning weights to different objective functions directly, weights are assigned to different goals in this method. This method allows direct tradeoffs between all unwanted deviational variables. This method involves identifying objectives, setting goal (target value for each objective, assign weights to each goal and then developing a normalized single objective function. Each goal, i has its achievement value Fi which is equal to the target Ti. Satisficing philosophy allows underachievement or overachievement of each of the goals, deviational variables di- (for underachievement) and di+ (for overachievement) are introduced: (4.1) (4.2) 42 If underachievement is desirable then di+ is minimized, while di- can take any positive value. Where overachievement is desirable, di- is minimized while di+ can have any positive value. The weighted GP objective function is then: (4.3) Here, K is the total number of objectives, in underachievement deviational variables, di-, and is the weights assigned to ip is the weights given to + overachievement deviational variables, di . This method allows more flexibility and direct comparison between different goals by trade-off analysis. 4.3.2 LEXICOGRAPHIC GOAL PROGRAMMING (LGP) Ijiri (1965) first introduced preemptive priority factors as a way of ordering goals in the objective function in GP models. He also established the process of assigning relative weights to goals of same priority level and it involves a different optimization process: 1. Identification of objective functions, 2. Specification of target value for each objective, 3. Prioritization of the objectives-target pairs, and 4. Solution of linear programming models for different priority level sequentially. The mathematical formulation of a typical LGP problem can be expressed as follows: (4.4) subject to: 43 Here, k is the total number of priority levels, and is the negative deviation from the target, is the value of the target and Pk is is the positive deviation from the target, the lowest priority and “P1>> P2” indicates that the value of P1 is greater than the value of P2. The algorithm in the LGP algorithm aims at minimizing the deviational variables for higher priority level and considers them to be more important than that of deviational variables placed in the lower priority level. This is done by following a sequential optimization process, where in each step the feasible region will reduced as minimization of higher priority goals are maintained (Jones and Tamiz, 2010). Although preemptive goal programming can allow weights associated with each goal, the common practice is not to use weights in preemptive goal programming. It is possible to move completely away from weighting deviational variables to an absolute priority structure (Schniederjans, 1995). In such a case the formulation would then become: (4.5) subject to: 44 4.3.3 MINMAX GOAL PROGRAMMING The purpose of this technique is to minimize the worst, or maximum unwanted goal deviations. It is very similar to weighted goal programming, the only exception is in the objective function which is to minimize the maximum deviational variables and that‟s why it is called MinMax goal programming and it was first introduced by Flavell (1976). When the decision maker desires to achieve a balance between different goals rather than prioritizing one goal over another or weighting different goals, minmax goal programming gives better result. Also it can identify optimal solutions for linear models that are not located at extreme points in the decision space (Jones and Tamiz, 2010). It also indicates that balancing philosophy is dominant in minmax goal programming. However, this technique is not extensively used in practice as much as the weighted GP and preemptive GP methods. In minmax GP, a new variable Max is introduced, which is constrained to be greater than or equal to each deviational variables to be minimized. The mathematical formulation is: (4.6) subject to: 45 4.3.4 OTHER GOAL PROGRAMMING TECHNIQUES Among other of goal programming methods, fractional goal programming, fuzzy goal programming and nonlinear goal programming is described next. i. Fractional Goal Programming This method involves targets for performance ratios. When the decision makers interest is to determine the best policy based on its target performance ratio, this method can be used. A typical mathematical formulation for a fractional goal programming model is: (4.7) subject to: Here, ii. are fractions which is a function of variable xi Fuzzy Goal Programming Fuzzy set theory is used in fuzzy goal programming which can deal with uncertainty in the decision variables. In fuzzy goal programming, the objective is to satisfy all goals which are described as a functional form of membership functions as compared to the conventional goal programming where all the goals are in crisp and an objective function with deviational variables from these crisp goals is minimized (Loganathan and Bhattacharya, 1990). There are many different fuzzy membership functions such as the right-sided linear, left-sided linear, triangular linear and the trapezoidal linear functions are the most widely used. 46 iii. Nonlinear Goal Programming In real life situation, nonlinearity is a very common phenomenon which for simplicity, can be transformed into linear relationship in most optimization models. Saber and Ravindran (1993) presented a thorough review of different nonlinear goal programming methods and applications. They reviewed four major nonlinear GP methods: simplex method, direct search method, gradient search method, and interactive approaches. Several different applications of these methods of nonlinear GP includes engineering design, energy sector and manufacturing industries, marketing, finance and accounting, agriculture, quality control and many others. 4.4 ISSUES WITH THE USE OF GOAL PROGRAMMING Although goal programming has been used widely in numerous practical fields, it is criticized for a number of issues. Romero (1991) addressed these issues in his book and provided a number of methods for alleviation of these criticisms. 4.4.1 INCOMMENSURABILITY Incommensurability means the incompatibility of different decision variables into a single objective function, which mainly occurs due to the use of different units of deviational variables in an objective function of weighted goal programming where the sum of unwanted deviational variables are minimized. This different measurement units damages the relative importance of the objective to the decision maker (Tamiz and Jones, 1994). This problem can easily be solved by the use of normalization procedure or simply using same unit for all deviational variables in an objective function. Different normalization techniques can also be used. 47 Percentage Normalization: This method can be used when all deviations are set as percentage deviations from the target but it is not suitable for zero target values. In this method the divisor is the absolute value of the right hand side of the objective. Euclidean Normalization: In this method, the divisor is the Euclidean sum of the coefficients of the decision variables in the objective function. Summation Normalization: Here the divisor is the sum of the absolute values of the coefficients of the decision variables in the objectives. It is useful for extreme cases of bad scaling of objectives and decision variables. 4.4.2 PARETO EFFICIENT SOLUTIONS Another major disadvantage of GP is that the solutions generated by the model can be non-efficient or Pareto inefficient. Pareto efficiency in GP is referred to as a state in which any objective cannot be improved without compromising the value of another objective. The solution from GP would be Pareto inefficient only if the linear weighted goal programming problem or the last problem in a lexicographic goal programming problem has alternative optimal solutions. The restoration algorithm presented by Romero (1991) describes the algorithm used to overcome this problem: 48 Figure 4-1: Algorithm for Solving GP Models Avoiding Non-efficient Solutions (Adopted from Romero, 1991) 49 4.4.3 NAIVE PRIORITIZATION AND REDUNDANCY IN LEXICOGRAPHIC GP In LGP, it is assumed that linear problems in each priority have an alternate solution. If for the higher priority objective, there is no alternative solution then the goals with priority lower than that one would be redundant or inferior. Excessive number of priorities can cause redundancy in LGP but it is not the only reason. If the target values for goals for a given priority are set at very high level or at an optimistic level then there will be more chances to have redundant goals despite the number of priorities used in the model. Redundancy can also occur if there are many two-sided goals exist in the model (Romero, 1991). To alleviate this problem, the decision maker has to revise the model to: re-adjust the priorities, reset the weights and targets, re-write the two-sided goals to get rid of redundant objectives (Tamiz and Jones, 1994). 4.4.4 TRADE-OFFS ACROSS PREEMPTIVE PRIORITY LEVELS Another major criticism of LGP is the existence of potentially large number of trade-offs between preemptive priority levels and it does not allow small sacrifice in the higher priority objective for a possibly major gain in the lower priority objective which in essence violate the principles of normative preference functions (Gál et al., 1999). Therefore care should be taken in performing goal sensitivity analysis with a special focus on the trade-offs between the various goals. 4.5 GOOD AND POOR MODELING PRACTICES IN GOAL PROGRAMMING Romero (1991) pointed out a number of poor modeling practices which can cause unexpected and non-satisfactory results when GP models are used in practice and could cause modelers and analysts to question the usefulness of GP in solving practical problems. Romero (1991) presented some of the poor modeling practices and outlined 50 a number of preferred modeling practices that could be followed when GP is used in practical studies. 4.6 SUMMARY This chapter provided an overview of goal programming models and solution algorithms. GP has proven to be very useful for many real life contexts. It has also been used in reservoir operation problems which make it an attractive candidate for use in the present research which deals with multi-reservoir and multi-purpose reservoir system at BC Hydro. A multi-objective optimization model using goal programming is developed in the next Chapter for the Columbia River Reservoir Operation for BC Hydro. 51 CHAPTER 5: MULTI-OBJECTIVE DEVELOPMENT FOR THE GOAL PROGRAMMING COLUMBIA RIVER MODEL RESERVOIR OPERATIONS 5.1 INTRODUCTION Reservoir operation is a very complex problem which may involve thousands of decision variables and constraints and could typically involve analysis of multiple objectives. To optimize this complex multi-purpose and multi-reservoir system operation problem, many multi-objective optimization methods has been developed and used over the last few decades. BC Hydro is operating three large reservoirs in the Columbia River of which the Kinbasket Lake (Mica dam) and the Arrow lakes (Keenleyside dam) are operated according to the Columbia River Treaty operations criteria. Although BC Hydro must comply with the Treaty operating plans and regulations, they are also operating their system in a way to maximum the revenues that can be achieved by trading electricity with the U.S. and Alberta electricity markets. For this reason, Shawwash (2000) and the BC Hydro research team developed the Generalized Optimization Model (GOM) at BC Hydro for medium term reservoir operation and the model has been used in reservoir operations planning at BC Hydro since it was developed. This research modified the CRT Model and adapted it to model the Columbia River Operation under the Treaty operating criteria. This model optimizes BC Hydro revenues using its resources without considering any other requirements except flood control and power generation. Due to growing concerns for environmental requirements, especially fisheries requirements, it is necessary to include these requirements into the optimization model and express them as objectives. 52 To optimize reservoir operation using fisheries requirements as an additional objectives a multi-objective optimization model is developed using the goal programming technique. The following sections describe various components of GOM and the multiobjective GP model formulation and the solution algorithm used to solve this problem. 5.2 COMPONENTS OF CRT MODEL This research modified the Columbia River Treaty Model (CRTM) and incorporated a number of Goal programming equations to model the supplementary agreements between BC Hydro and BPA as described below. 5.2.1 DECISION VARIABLES Decision variables in GOM are the conventional decision variables that are typically used in reservoir optimization model: QTj,t,h: Turbine Releases from plant j at time step t and sub-time step h in m3/s, QSj,t,h, : Spill release from plant j at time step t and sub-time step h in m3/s. QPj,t,h : Total plant outflows from plant j at time step t and sub-time step h in m3/s. Pj,t,h : Plant generation from plant j at time step t and sub-time step h in MWh. SpotUSt,h: Spot trade transaction schedules (export and imports) to the U.S. market at time step t and sub-time step h in MWh. SpotABt,h : Spot trade transaction schedules (export and import) to the Alberta market at time step t and sub-time step h in MWh. 53 5.2.2 BASIC CONSTRAINTS GOM models several constraints; some are basic equations which are commonly used in typical reservoir operation models. Most of the constraints are linear and a number of them models nonlinear relationships and they are approximated by convex piecewise linear equations as discussed below. i. Hydraulic Continuity Equation This is a basic constraint in any reservoir operation problem. It calculates the storage in the reservoir at each time step by summing storage in the previous time step, upstream plants‟ turbine flows and spill releases, natural inflows and plant discharge through turbines and spillways. Given: Qinj,t: Local natural inflows to reservoir j in time step t in m3/s. HCTj,k: Matrix representing the hydraulic connectivity between upstream and downstream reservoirs and are used to calculate the turbine outflows from reservoir j to reservoir k, k . HCTj,k = 0 if there is no physical hydraulic connection between the reservoirs, else =1. HCSj,k: Matrix representing the hydraulic connectivity between upstream and downstream reservoirs and are used to calculate the spill releases from reservoir j to reservoir k. HCSj,k = 0 if there is no physical hydraulic connection between the reservoirs, else =1. Ht,h: Number of hours in sub-time step h at time step t. Ht : Number of hours in time step t. 54 Sj,t : Reservoir storage in reservoir j at time step t in m3/s-day. Sj,t = Sj,1 when t = 1, Total number of time steps. The continuity equation can be written as: (5.1) ii. Storage Bound Constraints Given: Min Sj,t : Minimum reservoir storage for reservoir j and time step t in m3/s-day. Max S j,t: Maximum reservoir storage for reservoir j and time step t in m3/s-day. In this constraint reservoir storage must be within the maximum and minimum storage limits. These limits are calculated based on piecewise linear functions which relate the storage volume to the reservoir elevation level (forebay) in this model. This relationship can be stated as: . The constraint is: iii. (5.2) Power Generation Constraints Power generation of a reservoir is a function of reservoir elevation (forebay level), turbine discharge and the hydraulic factor of power generation per unit discharge. HKj,t : The amount of generation per unit discharge for plant j at time t in MWh/ m3/s. 55 (5.3) iv. Total Power Generation Constraints GRMj,t,h : Regulating margin minimum requirement for plant j at time step t and sub-time step h in MW. GORj,t : Percentage of operating reserve obligation for plant j. PTj,t,h : Total potential power generation and operating reserve for plant j at time step t and sub-time step h in MWh. Total power generation constraint is: (5.4) v. Generation Limit Constraints Generation from each plant j must be within a maximum and minimum generation limit at each time step t and sub-time step h. Max Pj,t : Maximum possible power generation from plant j at time step t in MWh. Min Pj,t : Minimum possible power generation from plant j at time step t in MWh. The equation is: (5.5) 56 vi. Load-Resource Balance Constraints This is one of the important constraints in GOM and it requires that summation of the amount of energy generated from plant j and other small hydro and thermal plants of BC Hydro at time step t and sub-time step h, imported power from the U.S./Alberta , and exported power to the U.S./Alberta is equal to the BC Hydro system load at that time step and sub-time step. Lt,h : BC Hydro System load at time step t and sub-time step h in MWh. G`t,h : Total fixed and shaped generation from other small hydro and thermal plants which are not included in the optimization study as decision variables. The load-resource balance equation is: (5.6) vii. Spot U.S. and Alberta Transmission Constraints BC Hydro has the capability to trade electricity with the U.S. and Alberta but this trading must be within the transfer capacity of the high voltage transmission limits connecting the BC Hydro system to these markets. Max TRUSt,h : Maximum transaction limit from BC to the U.S. at time step t and sub-time step h in MWh. Min TRUSt,h : Minmum transaction limit from BC to the U.S. at time step t and sub-time step h in MWh. Max TRABt,h : Maximum transaction limit from BC to Alberta at time step t and sub-time step h in MWh. 57 Min TRABt,h : Minmum transaction limit from BC to Alberta at time step t and sub-time step h in MWh. The constraints are: (5.7) (5.8) viii. Turbine Bound Constraints Each generating plant has physical bounds on the turbine outflows that it can be released and is referred to as turbine bound constraints. Max QTj,t : Maximum limit of turbine discharge for plant j at time step t in m3/s. Min QTj,t : Minimum limit of turbine discharge for plant j at time step t in m3/s. The equation is: (5.9) ix. Plant Discharge Bound Constraints Plant discharge must be within a certain range which is calculated based on reservoir elevation, number of unit available, and units available and plant spill capability which could also be a function of reservoir water level. Max QPj,t : Maximum plant discharge from plant j at time step t in m3/s. Min QPj,t : Minimum plant discharge from plant j at time step t in m3/s. 58 The constraint equation is: (5.10) 5.2.3 CRT RELATED CONSTRAINTS The Generalized Optimization Model (GOM) was modified to include the Columbia River Treaty operating criteria in the optimization process. The CRT imposes some special constraints on the reservoirs operated under the terms of the CRT. These special constraints are applicable to the Mica and the Arrow Lake hydro plants. i. Flood Control Constraints This is the most important constraint as one of the major objectives of the CRT is to control potential floods in the Columbia River. The flood control constraints are implemented in the model as a set of rule curves for Mica and Arrow reservoir. They are: The Upper Rule Curve (URC): This is also known as the Flood Control Curve (FCC) and it defines the highest reservoir storage limit that could minimize the flooding risk. Flood control level is a function of the volume flow at the Dalles. According to this curve, reservoirs are drafted to a specified level to ensure adequate flood control space. In this research, perfect foresight was assumed and that is why the FCC for the Arrow reservoir was at its maximum level. In GOM, FCC are used for the Mica and the Arrow reservoirs. For these two reservoirs, the storage bound constraint is: (5.11) Where FCCj,t: Flood Control Curve for reservoir j at time t in m3/s-day. 59 ii. Storage Constraint for MICA In the model, total storage at Mica reservoir consists of several storage accounts: Treaty Storage requirement at Mica, Flexible storage at Mica, Non-Treaty storage for both the U.S. and Canada and the Dead Storage. TTYSMicat : Treaty Storage at Mica reservoir at time step t in cms-day. FlexSMicat : Flexible Storage at Mica reservoir at time step t in cms-day. NT_US_SMicat : Non-Treaty Storage for BPA at Mica reservoir at time step t in cms-day. NT_BC_SMicat : Non-Treaty Storage for BC Hydro at Mica reservoir at time step t in cmsday. The constraint is: (5.12) iii. Storage Constraint for Arrow Storage at Arrow reservoir includes Treaty storage required at Arrow reservoir, flexible storage and Non-power storage at Arrow. TTYSArrowt : Treaty Storage at Arrow reservoir at time step t in cms-day. FlexSArrowt : Flexible Storage at Arrow reservoir at time step t in cms-day. NPSArrowt : Storage requirement to satisfy Non-power requirements at Arrow reservoir at time step t in cms-day. The constraint is: 60 (5.13) 5.3 COMPONENTS OF THE CRT-GP MODEL In this research, a combination of weighted goal programming and Lexicographic goal programming approach is adopted. Fisheries requirements (Flow Augmentation, Whitefish, and Trout Spawning) included in Non-Power Uses Agreement are incorporated into the optimization model using these two GP techniques. Flow Augmentation (FA) and Whitefish (WF) have the same importance to the Decision Maker and hence have the same priority level with equal weight assigned to both while Trout Spawning (TS) will have lower priority. Different combination of priority for FA+WF and TS were tested and the third priority in this model is for revenue of BC Hydro by trading electricity to the U.S. and Alberta. Components of GP model is presented in this section. Decision variables: Decision variables in the CRT-GP model are: NPQArrowt : Total flow to satisfy Non-power requirements at the Arrow reservoir at time step t in m3/s. FAQArrowt : Flows to satisfy the Flow Augmentation at Arrow reservoir at time step t in m3/s. WFQArrowt : Whitefish flow at Arrow reservoir at time step t in m3/s. TSQArrowt : Trout Spawning flow at Arrow reservoir at time step t in m3/s. PosDevFAt : Positive deviational variable from the target FA flows at time step t in m3/s. NegDevFAt : Negative deviational variable from the target FA flows at time step t in m3/s. 61 PosDevWFt : Positive deviational variable from the target WF flows at time step t in m3/s. NegDevWFt : Negative deviational variable from the target WF flows at time step t in m3/s. PosDevTSt : Positive deviational variable from the target Trout Spawning flows at time step t in m3/s. NegDevTSt : Negative deviational variable from the target Trout Spawning flows at time step t in m3/s. Parameters: Parameters specific to the CRT-GP model and their values for this research are: FA_target_storage = 1 Million-Acre-Feet (Maf =14276 m3/s-day) WF_target_flow_difference = 19 kcfs (538 m3/s) Target_April_flow = 30 kcfs (849.5 m3/s) Constraints: The constraints in the CRT-GP model are: i. Non-Power Flow Constraints for Arrow Reservoir This constraint sums Non-power flow requirements: FA, WF, and TS flow. (5.14) 62 ii. FA Storage Constraints: To help downstream migration of Salmonids at McNary Dam, it is required to store 1 Million-Acre-Feet (Maf =14276 m3/s-day) from January to April. This constraint is written in the CRT-GP model as: (5.15) iii. FA Release Constraints: Water stored for FA must be released in May, June and July of the same year. The release distribution can be 15%, 15% and 70% in May, June and July respectively. In other months, there would be no flow for FA purpose. (5.16) (5.17) iv. WF Flow Constraints: To meet Whitefish requirements, it is necessary to release a certain amount of flow in February and maintain the March flows in such a way to prevent Whitefish eggs from getting exposed at the downstream of the Arrow reservoir. To achieve this it is required that the difference in outflows between February and January and March would be a less than or equal to 19 kcfs (538 m3/s). The GP constraints are: (5.18) 63 (5.19) v. TS Flow Constraints: To meet the Trout Spawning requirements, it is necessary to maintain a non-declining flow from April to June and also the anticipated flow in April should be higher than or equal to 30 kcfs (849.5 m3/s). These requirements are included into GP model as: (5.20) (5.21) vi. FA and WF Equity Constraint: In reality considering all other constraints (Basic and Treaty related constraints), it is not possible to satisfy both the WF and the FA requirements. Since FA and WF have equal priority, it is necessary to equally distribute the deviation from target for both FA and WF. This equity constraint equalizes the difference, or deviation from the target, in FA storage from the target FA storage to negative deviation for WF requirements. 5.4 OBJECTIVE FUNCTION The developed model is a multi-objective model with objective function terms for Nonpower requirements and revenues from power generation for the BC Hydro system. For the CRT-GP model, the objective function was modified to minimize undesirable deviations from the target in addition to the GOM objective of maximizing the revenues from trading for BC Hydro less the value of energy spilled from reservoirs as uncontrolled spills. 64 Given: Pricet,h : Market price (import ∕ export) at time step t and sub-time step h in $ ∕ MWh. CRT-GP Objectives: Objective 1: (5.22) Objective 2: (5.23) And Objective 3: (5.24) 5.5 SOLUTION ALGORITHM The solution algorithm for the developed model is as follows: 1. The total number of time steps is defined at first. Also the start and end date of the study are defined. 2. Solve the model for all time steps using the GOM objective function. 3. Add the CRT-GP to equations to GOM. 4. Drop the GOM objective function. 5. Drop the associated constraints for lower priority goal (Goals are prioritized based one DM`s choice). 6. The model is then solved for all time steps for the first priority goal for a number of iteration (here 3 iterations were done). 65 7. The results from the first priority goal are saved to output files. 8. The decision variables associated with the first priority goal are fixed for the next step so that for lower priority goals the model does not sacrifice the solution from higher priority goal. 9. The model now moves to the next priority and the model optimizes the second prioritized objective function. 10. The results are saved to output files. 11. The model solves the problem using the third objective function again and save the outputs which is used for the comparison. Figure 5-1 illustrates a flow chart of the solution algorithm described above. 66 Figure 5-1: GOM Model Algorithm with GP Formulation 67 5.6 SUMMARY The model outlined in this chapter was used for the Columbia River Treaty operation including only BC Hydro`s major reservoir system on the Columbia River: Mica, Revelstoke and the Arrow reservoirs. The model also extended to include other two major reservoirs in the British Columbia, Peace Canyon reservoir and the GM Shrum. 68 CHAPTER 6: MODEL APPLICATIONS AND RESULTS ANALYSIS 6.1 INTRODUCTION The CRT-GP model developed in this research was tested using a number of case studies by using data from the Detailed Operating Plan (DOP) study (DOP 2012) which does not include any fisheries requirements. The model is a monthly model and it used data starting from October 1st 1928 for 70 years. The model was first run without adding any of the goal programming equations to test the level of satisfaction of fisheries‟ requirements with the base Treaty flows and this case was labeled as the Base Treaty case. Then the GP equations were added and the model was run using CRT-GP formulation and the highest priority was given to the FA and WF objectives followed by the TS objective. Using the GP formulation, the first case study was performed using no minimum flow limit on the Arrow outflow in January. Next, four different minimum flow limits were imposed on the January outflow from the Arrow reservoir and these were used for different case studies. 6.2 BASE TREATY CASE For the Base Treaty case study, no goal programming formulation was used and the model was run using CRTM formulation with the Treaty constraints excluding any fisheries constraints. The purpose of this case study is to evaluate the satisfaction level of WF, FA, and TS requirements under AOP operations, under which flood control and hydro-power generation are only considered as objectives. This case study also shows that Treaty flows need to be modified to satisfy the fish requirements and they need to be incorporated in the optimization process. The data in this study does not include any fisheries requirements and it only includes Treaty operating criteria. 69 To meet the downstream power demand in the U.S., it is necessary to maintain a minimum Arrow and Duncan reservoir flow of 55 kcfs (1557 m3/s) in January. In this study the Duncan outflow was set at 7 kcfs, so the minimum Arrow outflow will become 48 kcfs in January. In Figure 6-1, the flow duration curve for the Arrow outflow in January is plotted and it can be seen that about 75 percent of the time the January outflow at Arrow was greater than or equal to 48 kcfs (1362 m3/s), which means that the Arrow outflow was below the target outflow level less than 25 percent of the time. To meet the Whitefish requirement, it is necessary to have the difference in outflow between January and February and January and March flow at Arrow reservoir less than or equal to 19 kcfs (538 m3/s). Figure 6-2 presents the flow duration curves for flow difference between January and February and the flow difference between January and March. Arrow minimum Target flow of 48 kcfs Base Case satisfaction = 23% Figure 6-1: Flow Duration Curve for Arrow Flow in January (Base Treaty Case) 70 January-February flow satisfaction level = 77% January-March flow satisfaction level = 23% Target flow difference of 19 kcfs Figure 6-2: Flow Duration Curves for (January Flow-February Flow) and (January Flow – March Flow) (Base Treaty Case) It can be seen from Figure 6-2 that the target flow difference can be satisfied 77 percent of the time in February (Figure 6-2) while in March, the target flow difference can be satisfied only 27 percent. These results indicate that WF flow requirements cannot be met 23 percent and 73 percent time in February and March respectively. To meet Trout Spawning requirements the Arrow outflow in April has to be equal to or greater than 30 kcfs (849.5 m3/s) and the flow rate has to be non-declining from April to June. Figure 6-3 presents the results of the study for the flow duration curves for Arrow reservoir flow in April with the TS target flow in April. Figure 6-4 presents the flow duration curves for flow difference between April and May and flow difference between May and June and Figure 6-5 shows the annual flows in April, May, and June. 71 It can be seen in Figure 6-3 that April outflows from the Arrow reservoir is less than or equal to 30 kcfs 85 percent of the time. Figure 6-4 shows that the difference in outflows between April and May (May flow minus April flow) exceeds zero (i.e., it meets the requirements) only 52 percent of the time while the outflow difference between May and June (June flow minus May flow) exceeds zero about 65 percent of the time which indicates that the flow in May and June are not non-declining. From Figure 6-4, it is clear that the Base Case operation will result in dissatisfaction of the desired Trout Spawning flow requirements 48% in May and 35% in June. April target flow satisfaction = 15% TS Target flow in April at Arrow Figure 6-3: Flow Duration Curve for Arrow Flow in April with TS target flow (Base Treaty Case) 72 May- June flow satisfaction level = 64% April - May flow satisfaction level = 53% Figure 6-4: Flow Duration Curves for (April Flow-May Flow) and (May Flow – June Flow) (Base Treaty Case) Figure 6-5: Annual April, May and June Flow Graphs (Base Case) 73 The Base Treaty Case results shows that without modifying the Treaty flows, it will not be possible to satisfy Non-power requirements for WF, FA, and TS. This result was expected and it is behind the reason that Canadian and the U.S. Entities have signed an agreement to modify the Treaty operation to meet WF, FA, and TS flow requirements. 6.3 CASE STUDIES USING PRIORITIZED OBJECTIVES The CRT-GP model includes three different GP objectives. A number of case studies were performed using these prioritized objectives by giving the highest priority to the Whitefish and Flow Augmentation objectives and a number of different case studies were performed. 6.3.1 BC HYDRO IDEAL CASE The purpose of this study is to identify the ability of the model to satisfy at least the high priority objective without imposing any limit on the January outflow at Arrow. Figure 6-6 to Figure 6-10 and Appendix B presents the results from this case study. In general, the results show that removing any limit on the Arrow reservoir outflow in January guarantees the full satisfaction of FA and WF requirements as these objectives are set at the highest priority. However, it can be seen in Figure 6-6 that the Arrow flow in January is lower than 48 kcfs (1362 m3/s) 46 percent of the time, thereby satisfying the FA and WF requirements as shown in Figure 6-7. Although the FA and WF objectives were met in this case study, flow requirements for TS were not completely satisfied as can be seen in Figure 6-8, and it can also be seen that 79 percent of the time the April flow is at or below 30 kcfs (849.5 m3/s), thereby violating the TS requirement in April. Figures 6-9 and 6-10 show that the flow in May is less than or equal to the flow in April only 17 percent of the time while the June flow is always higher than or equal to the May flows thereby violating the TS requirement. 74 Arrow minimum target flow of 48 kcfs Base Case satisfaction = 54% Figure 6-6: Flow Duration Curve for Arrow Flow in January (BCH Ideal Case) Figure 6-7: Flow Duration Curves for (January Flow-February Flow) and (January Flow – March Flow) (BCH Ideal Case) 75 TS Target flow in April at Arrow April target flow satisfaction = 15% Figure 6-8: Flow Duration Curve for April Flow with TS target flow (BCH Ideal Case) Figure 6-9: Annual April, May and June Flow Graphs (BCH Ideal Case) 76 April – May flow satisfaction level = 83% Figure 6-10: Flow Duration Curves for (April Flow-May Flow) and (May Flow – June Flow) (BCH Ideal Case) 6.3.2 TRADE-OFF CASES After solving the model without imposing any limit on the January flow at Arrow, the model was run for different Arrow minimum flow limits in January. In the first case study, the combined Arrow and Duncan reservoir flow was set to a minimum limit of 55 kcfs (1557 m3/s). The Duncan reservoir flow was assumed to be 7 kcfs (198 m3/s). For the rest of the studies the Arrow minimum flow limit was set at 43 kcfs (1217.6 m 3/s), 38 kcfs (1076 m3/s), and 33 kcfs (934.5 m3/s). Figure 6-11compares the occurrences of FA storage from January to April. From this graph, it is clear that lowering the target flow in January increases the satisfaction of FA Storage requirement of storing 1 Maf (14376.4 m3/s-d) by end of April. It can be seen that for a flow limit of 48 kcfs, 34 percent of the time FA Storage is below 1 Maf while for flow limit of 43 kcfs, 38 kcfs, and 33 kcfs, the cumulative occurrences of 77 FA Storage below 1 Maf (<1.0) are 27 percent, 9 percent, and 4 percent respectively. It can be seen in Figure 6-12 and Appendix A that the flow difference between January and February flow (January flow minus February flow) from Arrow reservoir is not affected by different target flow in January and it is always within the acceptable range of 19 kcfs (538 m3/s). However, the flow difference between January flow and March flow from the Arrow reservoir is affected by the flow limit in January and the satisfaction level increases with lowering the limit and this is consistent with FA Storage requirement. Figure 6-12 and Appendix A show that the flow difference between the January and March flow from Arrow at or above 19 kcfs (538 m 3/s) are 32 percent, 27 percent, 11 percent, and 4 percent for the corresponding minimum January flow limits. Figure 6-11: Cumulative Occurrence of FA Storage for Different January Minimum Flow Limit (Trade-Off Cases) 78 January-March flow satisfaction level = 66% Target flow difference of 19 kcfs Figure 6-12: Flow Duration Curves for (January Flow-February Flow) and (January Flow – March Flow) (Trade-Off Case: Target Flow 48 kcfs) Figure 6-13 and Appendix A show that the satisfaction of April flow limit for TS requirements does not depend on the target minimum flow in January at the Arrow reservoir and remains constant (around 79 percent of the time the flow is less than 30 kcfs) for all target flow in January. Another TS requirement is to maintain a nondeclining flow through April to June and Figure 6-14 to 6-15 show that the June flow is always higher than or equal to May flow but the May flow is often less than the April flow and the satisfaction level changes with January target flow at Arrow reservoir. 79 TS Target flow in April at Arrow April target flow satisfaction = 21% Figure 6-13: Flow Duration Curve for April Flow with TS target flow (Trade-Off Case: Target Flow 48 kcfs) April - May flow satisfaction level = 88% Figure 6-14: Flow Duration Curves for (April Flow-May Flow) and (May Flow – June Flow) (TradeOff Case: Target Flow 48 kcfs) 80 Figure 6-15: Annual April, May and June Flow Graphs (Trade-Off Case: Target Flow 48 kcfs) 6.4 IMPACTS ON GENERATION Incorporation of FA, WF, and TS requirements in the optimization algorithm has little impacts on power generation of BC Hydro major reservoir system. There are no significant changes in the generation patterns for the different case studies investigated. However, the overall BC Hydro revenue slightly increases with the satisfaction of WF, FA, and TS requirements. Figure 6-16 shows the average monthly generation of the Mica plant for different case studies. Plots for generation of other optimized plants are included in Appendix B. 81 Figure 6-16: Mica Average Monthly Generation for Different Case Studies 82 CHAPTER 7: CONCLUSIONS AND RECOMMENDATIONS 7.1 SUMMARY Reservoir operation problems are becoming more complex due to growing environmental concerns and requirements. To solve these complex and often conflicting objectives, multi-objective optimization technique is one of best methods to develop operations planning strategies at a relatively satisfactory level of performance on these objectives. A reservoir planning entity usually considers objectives which include flood protection, power generation, and fisheries requirements. Among different multiobjective optimization techniques, the weighted sum method, epsilon (Є) constraint method, and goal programming method are the most commonly used in reservoir operations. Due to certain limitations of the weighted sum and epsilon (Є) constraint methods, in this research goal programming technique was used to model the CRT Supplemental Operating Agreements between the U.S. and the Canadian Entities. Goal Programming (GP) method is a widely used method for solving multi-objective optimization problem in many different fields of optimization. It was first developed by Charnes et al. (1955) and since then it has been used by a number of researchers in various fields, thereby establishing it as a reliable method to solve multi-objective optimization problems. Since the 1960s, a number of different goal programming methods have been developed of which weighted goal programming, Lexicographic goal programming and minmax goal programming are widely used today. In this research a combination of weighted goal programming and Lexicographic goal programming was used to model the terms of these supplementary agreements for fish related issues. 83 In this study, a goal programming algorithm was developed to model the BC Hydro power generation system with consideration of the Columbia River Treaty operating criteria and the terms of the supplementary agreements. The Columbia River Treaty is a very complex treaty, signed between Canada and the U.S. in 1961 and ratified in 1964 by the Canadian Parliament. Canada operates three major reservoirs in the Canadian portion of the Columbia River, namely the Mica, the Duncan and the Arrow reservoir in accordance with the terms of the CRT. However, CRT operation only considers flood control and power generation. To accommodate fisheries requirements in the Columbia River reservoir operation, Canada and the U.S. signed Non-Power Uses Agreement which defined a set of additional terms on storage and flow requirements for Flow Augmentation (FA), Whitefish (WF), and Trout Spawning (TS) from January to July each year. The current research modified the Columbia River Treaty Model (CRTM), developed by UBC and the BC Hydro Research team. The model includes FA, WF and TS fisheries requirements in the optimization process using goal programming techniques. The model was formulated in AMPL and solved by the Cplex solver and was run using 70 years of monthly data. 7.2 CONCLUSION The goal programming formulation successfully incorporated three non-power requirements (Flow Augmentation, Whitefish, and Trout Spawning requirement), which were agreed on by both the U.S. and Canada in Non-Power Uses Agreement, in the Columbia River Treaty Model (CRTM). Equal weights were assigned to both the Whitefish and the Flow Augmentation objectives which were of highest priority followed by the Trout Spawning objective which was of a relatively lower priority according to current Decision Maker‟s (DM) preferences. Using this priority structure, the model was 84 used to perform a number of case studies. Since the flow limit on the Arrow outflows in January is very important to meet high power demand in the U.S., the model evaluated different minimum flow limits in January to assess the impacts of different flow limits on the satisfaction level of three non-power requirements. A Base Treaty Case was studied to identify the satisfaction level of these requirements given the Columbia River Treaty operating plans and criteria. Then a case study without imposing any flow limit on January flow from the Arrow reservoir was investigated. Four different case studies were performed to evaluate the effects of different January minimum flow limits on the level of satisfaction of non-power requirements. Results from these case studies show that different minimum Arrow flow limits in January impact the satisfaction of FA and WF objective, while they do not have any clear impact on the satisfaction of the TS objective as no trade-off between FA and TS was not considered in this research. As the flow limit in January decreases, the satisfaction level of FA and WF increases accordingly. For a flow limit of 40 kcfs (1557 m 3/s, combined Arrow and Duncan flow), the satisfaction level of the FA and WF objectives are about 96 percent. Satisfaction of these objectives has very little impact on BC Hydro generation and the revenues slightly increase with decreasing January flow limit. The GP formulation allows deviation from the target value of any constraint which makes this method very attractive to investigate the trade-offs between multiple objectives. Also the deviation gives flexibility to the model to handle any infeasibility which can be caused by strict constraints. The goal programming formulation can represent the complex, real life situation more realistically and can provide reliable operations planning for a complex multi-reservoir system like the BC Hydro system. 85 7.3 FUTURE WORK There are several opportunities for further development of this model and its use it in many studies. Some of these are listed below: A technique to assign weights to different fish requirements can be developed to automate the weights assigning process. Trade-off between Flow Augmentation and Trout Spawning requirement can be performed to evaluate the relationships between these two non-power requirements. The model can be compared with other multi-objective optimization methods to evaluate the performance of goal programming formulation. A daily model can be developed to include daily variation of inflows into the reservoir system to provide more realistic reservoir operations. The model can be further extended to include downstream hydroelectric facilities in the U.S. to optimize reservoir operations for the entire Columbia River system. 86 BIBLIOGRAPHY Abdalla, A. E., 2007, A Reinforcement Learning Algorithm for Operations Planning of a Hydroelectric Power Multireservoir System, University of British Columbia, Vancovuer, BC, Canada. Afshar, M. H., and R. Moeini, 2008, Partially and Fully Constrained Ant Algorithms for the Optimal Solution of Large Scale Reservoir Operation Problems: Water Resources Management, v. 22, p. 1835-1857. Andersen, E. D., B. Jensen, J. Jensen, R. Sandvik, and U. Woesoe, 2009, MOSEK version 6. MOSEK Technical Report: TR-2009-3. Aouni, B., and O. Kettani, 2001, Goal Programming Model: A Glorious History and a Promising Future: European Journal of Operational Research, v. 133, p. 225-231. Barros, M. T. L., F. T. C. Tsai, S. L. Yang, J. E. G. Lopes, and W. W. G. Yeh, 2003, Optimization of Large-Scale Hydropower System Operations: Journal of Water Resources Planning and Management-Asce, v. 129, p. 178-188. Bazaraa, M. S., and C. M. Shetty, 1979, Nonlinear Programming Theory and Algorithms, John Wiley. Bellman, R. E., 2003, Dynamic Programming, Dover Publications. Can, E. K., and M. H. Houck, 1984, Real Time Reservoir Operations by Goal Programming: Journal of Water Resources Planning and Management-Asce, v. 110, p. 297-309. Chang, C. T., 2002, A Modified Goal Programming Model for Piecewise Linear Functions: European Journal of Operational Research, v. 139, p. 62-67. Chang, N. B., C. G. Wen, and Y. L. Chen, 1997, A Fuzzy Multi-Objective Programming Approach for Optimal Management of the Reservoir Watershed: European Journal of Operational Research, v. 99, p. 289-302. Charnes, A., W. W. Cooper, and R. O. Ferguson, 1955, Optimal Estimation of Executive Compensation by Linear Programming: Management Science, v. 1, p. 138-151. Chen, L. H., and F. C. Tsai, 2001, Fuzzy Goal Programming with Different Importance and Priorities: European Journal of Operational Research, v. 133, p. 548-556. Coello, C. A. C., and A. D. Christiansen, 1998, Two New GA-based Methods for Multiobjective Optimization: Civil Engineering and Environmental Systems, v. 15, p. 207-243. 87 Collette, Y., and P. Siarry, 2003, Multiobjective Optimization: Principles and Case Studies, Springer. Datta, B., 1993, Operation Model for Single and Multipurpose Reservoirs – A Review, Jalvygyan Samecksha (INCH)-A Publication of Indian National Committee on Hydrology, p. 1-12. Engineers, U. S. A. C. o., and B. P. Administration, 2009, Columbia River Treaty Review: History and 2014/2024 Review. Eschenback, E. A., T. H. Magee, E. Zagona, M. Goranflo, and R. Shane, 2001, Goal programming Decision Support System for Multiobjective Pperation of Reservoir Systems: Journal of Water Resources Planning and Management-Asce, v. 127, p. 108120. Flavell, R., 1976, A New Goal Programming Formulation: Omega, v. 4, p. 731-732. Gilmore, A., T. Magee, T. Fulp, and K. Strezepek, 2000, Multiobjective Optimiztion of the Colorado River: the ASCE 2000 Joint Conference on Water Resources Engineering and Water Resources Planning and Management. Grygier, J. C., and J. R. Stedinger, 1985, Algorithms for Optimizing Hydropower System Operation: Water Resources Research, v. 21, p. 1-10. Gál, T., T. J. Stewart, and T. Hanne, 1999, Multicriteria Decision Making: Advances in MCDM Models, Algorithms, Theory, and Applications, Kluwer Academic. Hastings, N. A. J., 1973, Dynamic Programming with Management Application: New york, U.S.A, Crane Russal & Company. Hiew, K. L., 1987, Optimization Algorithms for Large-Scale Multireservoir Hydropower Systems, Colorado State University. Hirst, S. M., 1991, Impacts of the Operation of Existing Hydroelectric Developments on Fishery Resources in British Columbia. Volume II. Inland Fisheries, Canadian Manuscript Report of Fisheries and Aquatic Sciences 2093, p. xxv. http://www.knowbc.com/ Hu, C. F., C. J. Teng, and S. Y. Li, 2007, A Fuzzy Goal Programming Approach to MultiObjective Optimization Problem with Priorities: European Journal of Operational Research, v. 176, p. 1319-1333. Hyde, J. M., 2010, Columbia River Treaty Past and Future: HydroVision International. 88 Hydro, BC, 2000, Making the Connection: The BC Hydro Electric System and How It Operates, Vancovuer, BC, Canada. Ignizio, J. P., 1985, Introduction to Linear Goal Programming, Sage Publications. Ijiri, Y., 1965, Management Goals and Accounting for Control: Studies in Mathematical and Managerial Economics, v. 3: Amsterdam, North-Holland. Jones, D., and M. Tamiz, 2010, Practical Goal Programming, Springer. Keeney, R. L., and E. F. Wood, 1977, Illustrative Example of Use of Multiattribute Utility Theory for Water-Resource Planning: Water Resources Research, v. 13, p. 705-712. Kerr, A. L., and E. G. Read, 1997, Short-term Hydro Scheduling Using Integer Programming: Management and Modelling Issues, University of Canterbury. Kim, T., J. H. Heo, and C. S. Jeong, 2006, Multireservoir System Optimization in the Han River Basin Using Multi-Objective Genetic Aalgorithms: Hydrological Processes, v. 20, p. 2057-2075. Ko, S.-K., D. G. Fontane, and J. W. Labadie, 1992, Multiobjective Optimization of Reservoir Systems Operation: JAWRA Journal of the American Water Resources Association, v. 28, p. 17. Kumar, D. N., and M. J. Reddy, 2006, Ant Colony Optimization for Multi-Purpose Reservoir Operation: Water Resources Management, v. 20, p. 879-898. Labadie, J. W., 2004, Optimal Operation of Multireservoir Systems: State-of-the-art Review: Journal of Water Resources Planning and Management-ASCE, v. 130, p. 93-111. Lai, Y. J., T. Y. Liu, and C. L. Hwang, 1994, TOPSIS for MODM: European Journal of Operational Research, v. 76, p. 486-500. Liang, Q. F., L. E. Johnson, and Y. S. Yu, 1996, A Comparison of Two Methods for Multiobjective Optimization for Reservoir Operation: Water Resources Bulletin, v. 32, p. 333-340. Loganathan, G. V., and D. Bhattacharya, 1990, Reservoir Operations by Fuzzy Goal Programming: Optimizing the Resources for Water Management: Proceedings of the 17th Annual National Conference, p. 456-461. Loucks, D. P., J. R. Stedinger, and D. A. Haith, 1981, Water Resource Systems Planning and Analysis, Prentice-Hall (Englewood Cliffs, N.J.). 89 Matzinger, A., R. Pieters, K.I. Ashley, G.A. Lawrence, and A. Wiiest, 2007, Effects of Impoundment on Nutrient Availability and Productivity in Lakes: Limnology and Oceanography, v. 52, p. 2629-2640. Mousavi, S. J., A. G. Zanoosi , and A. Afsha, 2004, Optimization and Simulation of A Multiple Reservoir System Operation: Journal of Water Supply: Research & Technology-AQUA, v. 53, p. 409-424. Murtagh, B. A., and M. A. Saunders, 2003, MINOS 5.51 User's Guide, Stanford, California, U.S.A, Systems Optimization Laboratory, Department of Management Science and Engineering, Stanford University. Nandalal, K. D. W., and J. Bogárdi, 2007, Dynamic Programming Based Operation of Reservoirs: Applicability and Limits, Cambridge University Press. Piekutowski, M. R., T. Litwinowicz, and R. Frowd, 1993, Optimal Short-Term Scheduling for a Large-Scale Cascaded Hydro System: Power Industry Computer Application Conference, p. 292-298. Rani, D., and M. M. Moreira, 2010, Simulation-Optimization Modeling: A Survey and Potential Application in Reservoir Systems Operation: Water Resources Management, v. 24, p. 1107-1138. Reznicek, K. K., and S. P. Simonovic, 1989, Practical Application of Successive Linear Programming for Reservoir Operations at Manitoba Hydro: Baltimore Symposium, p. 12. Romero, C., 1991, Handbook of Critical Issues in Goal Programming, Pergamon Press. Saber, H. M., and A. Ravindran, 1993, Nonlinear Goal Programming Theory and Practice: A Survey: Computers & amp; Operations Research, v. 20, p. 275-291. Schniederjans, M. J., 1995, Goal Programming: Methodology and Applications, Kluwer Academic Publishers. Schultz, G. A., 1989, Ivory Ttower Versus Ghosts?-or- The Interdependency Between Systems Analysts and Real-World Decision Makers in Water Management: Closing the Gap Between Theory and Practice, The 3rd Scientific Assembly of International Association of Hydrological Sciences (IAHS), p. 23-32. Service, U. S. F. a. W., 2000, Biological Opinion: Effects to Listed Species from Operations of the Federal Columbia River Power System. Shabani, N., 2009, Incorporating Flood Control Rule Curves of the Columbia River Hydroelectric System in A Multireservoir Reinforcement Learning Optimization Model, University of British Columbia, Vancovuer, BC, Canada. 90 Shawwash, Z. K., T. K. Siu, and S. O. D. Russell, 2000, The BC Hydro Short Term Hydro Scheduling Optimization Model: Ieee Transactions on Power Systems, v. 15, p. 11251131. Shawwash, Z. K. E., 2000, A Decision Support System for Real-Time Hydropower Scheduling in A Competitive Power Market Environment, University of British Columbia, Vancovuer, BC, Canada. Simonovic, S. P., and R. Verma, 2008, A New Methodology for Water Resources Multicriteria Decision Making Under Uncertainty: Physics and Chemistry of the Earth, v. 33, p. 322329. System, F. C. R. P., 2001, The Columbia River System: Inside Story, Bonneville Power Administration Tamiz, M., and D. F. Jones, 1994, An Overview of Current Solution Methods and Modelling Practices in Goal Programming: First International Conference in Multi-objective Programming and Goal Programming Theories and Applications. Tang, Y., 2007, A Mixed Integer-Llinear Programming Model for Solving the Hydroelectric Unit Maintenance Scheduling Problem, University of British Columbia, Vancouver, BC, Canada. Wang, L., C. T. Nyunt, T. Koike, O. Saavedra, L. C. Nguyen, and T. v. Sap, 2010, Development of An Integrated Modeling System for Improved Multi-Objective Reservoir Operation: Frontiers of Architecture and Civil Engineering in China, v. 4, p. 9. Yeh, W., 1985, Reservoir Management and Operation Models: A State-of-Art Review: Water Resources Research, v. 21, p. 1797-1818. Yoo, J. H., 2009, Maximization of Hydropower Generation Through the Application of A Linear Programming Model: Journal of Hydrology, v. 376, p. 182-187. Zagona, E. A., T. J. Fulp, R. Shane, Y. Magee, and H. M. Goranflo, 2001, Riverware: A Generalized Tool for Complex Reservoir System Modeling: Journal of the American Water Resources Association, v. 37, p. 913-929. Zagona, E. A., and T. M. Magee, 1999, Modeling Hydropower in RiverWare: The International Conference on Hydropower. 91 APPENDICES APPENDIX A: TRADE-OFF CASES Appendix A 1: Flow Duration Curves for (January Flow-February Flow) and (January Flow – March Flow) (Trade-Off Case: Target Flow 43 kcfs) 92 Appendix A 2: Flow Duration Curve for April Flow with TS target flow (Trade-Off Case: Target Flow 43 kcfs) Appendix A 3: Flow Duration Curves for (April Flow-May Flow) and (May Flow – June Flow) (TradeOff Case: Target Flow 43 kcfs) 93 Appendix A 4: Annual April, May and June Flow Graphs (Trade-Off Case: Target Flow 43 kcfs) Appendix A 5: Flow Duration Curves for (January Flow-February Flow) and (January Flow – March Flow) (Trade-Off Case: Target Flow 38 kcfs) 94 Appendix A 6: Flow Duration Curve for April Flow with TS target flow (Trade-Off Case: Target Flow 38 kcfs) Appendix A 7: Flow Duration Curves for (April Flow-May Flow) and (May Flow – June Flow) (TradeOff Case: Target Flow 38 kcfs) 95 Appendix A 8: Annual April, May and June Flow Graphs (Trade-Off Case: Target Flow 38 kcfs) Appendix A 9: Flow Duration Curves for (January Flow-February Flow) and (January Flow – March Flow) (Trade-Off Case: Target Flow 33 kcfs) 96 Appendix A 10: Flow Duration Curve for April Flow with TS target flow (Trade-Off Case: Target Flow 33 kcfs) Appendix A 11: Flow Duration Curves for (April Flow-May Flow) and (May Flow – June Flow) (Trade-Off Case: Target Flow 33 kcfs) 97 Appendix A 12: Annual April, May and June Flow Graphs (Trade-Off Case: Target Flow 33 kcfs) 98 APPENDIX B: IMPACTS ON GENERATION Appendix B 1: GM Shrum Average Monthly Generation for Different Case Studies Appendix B 2: Peace Canyon Average Monthly Generation for Different Case Studies 99 Appendix B 3: Revelstoke Average Monthly Generation for Different Case Studies Appendix B 4: Arrow Average Monthly Generation for Different Case Studies 100
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- A goal programming algorithm to incorporate the Columbia...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
A goal programming algorithm to incorporate the Columbia river non-power flow requirements in the Columbia… Mamun, Abdullah Al 2012
pdf
Page Metadata
Item Metadata
Title | A goal programming algorithm to incorporate the Columbia river non-power flow requirements in the Columbia River treaty model |
Creator |
Mamun, Abdullah Al |
Publisher | University of British Columbia |
Date Issued | 2012 |
Description | Canada built and operates three large dams and the U.S. built and operates one dam in the Columbia River based on the Columbia River Treaty (CRT) which was signed in 1961 and ratified in 1964. Annual Operating Plan developed by two Entities does not include non-power requirements, unless they are mutually agreed upon by both Entities. Supplemental Operating Agreements (SOA) have been negotiated and implemented since the 1990s to meet the U.S. and the Canadian power, fish, wildlife and/or recreation needs. The objective of this research was to develop a multi-objective optimization model to deal with multiple and conflicting objectives. The Columbia River Treaty Model (CRTM) developed by BC Hydro was modified by this research to incorporate three non-power requirements that are agreed upon by both Entities. The new model, which utilized the Goal Programming technique to solve the multi-objective reservoir optimization problem, was used to perform a number of case studies in order to investigate the impacts of incorporating different non-power requirements onto the BC Hydro system. Specific minimum outflow at the border in January affects the level of fulfillment of three non-power requirements. The first requirement is the Flow Augmentation requirement to aid in the downstream migration of Salmon in the U.S. The second requirement is the flow requirements below the Arrow reservoir to protect Whitefish eggs during the spawning and hatching periods. The third requirement is the specific flow requirement to provide enough water cover for the Trout spawning downstream of Arrow. The model uses three prioritized objectives of which the Flow Augmentation and Whitefish are of highest priority followed by the Trout Spawning and the maximization of BC Hydro revenues. Four Arrow minimum flow scenarios were compared with the Treaty operation. The study results show that lowering the minimum Arrow flow limit in January increases the satisfaction level of the Flow Augmentation and Whitefish non-power requirements. However, it may be in conflict with the power requirement of meeting Pacific North-west winter peak loads. Unless additional flow is required for Flow Augmentation during April, it has no effect on Trout spawning. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2012-01-19 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0050648 |
URI | http://hdl.handle.net/2429/40170 |
Degree |
Master of Applied Science - MASc |
Program |
Civil Engineering |
Affiliation |
Applied Science, Faculty of Civil Engineering, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2012-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
Aggregated Source Repository | DSpace |
Download
- Media
- 24-ubc_2012_spring_mamun_abdullahal.pdf [ 1.71MB ]
- Metadata
- JSON: 24-1.0050648.json
- JSON-LD: 24-1.0050648-ld.json
- RDF/XML (Pretty): 24-1.0050648-rdf.xml
- RDF/JSON: 24-1.0050648-rdf.json
- Turtle: 24-1.0050648-turtle.txt
- N-Triples: 24-1.0050648-rdf-ntriples.txt
- Original Record: 24-1.0050648-source.json
- Full Text
- 24-1.0050648-fulltext.txt
- Citation
- 24-1.0050648.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0050648/manifest