Microsoft Word - 476hernandez.docx CHEMICAL ENGINEERING TRANSACTIONS VOL. 43, 2015 A publication of The Italian Association of Chemical Engineering Online at www.aidic.it/cet Chief Editors: Sauro Pierucci, Jiří J. Klemeš Copyright © 2015, AIDIC Servizi S.r.l., ISBN 978-88-95608-34-1; ISSN 2283-9216 MILFP Model and Algorithms for Network Design and Long- Term Planning of Water Management System for Shale Gas Production Jiyao Gao, Fengqi You* Department of Chemical and Biological Engineering, Northwestern University, Evanston, IL 60208, USA you@northwestern.edu This paper addresses the optimal design and operations of water supply chain networks for shale gas production. We develop a mixed-integer linear fractional programming (MILFP) model with the objective to maximize profit per unit freshwater consumption, such that both economic performance and water-use efficiency are optimized. The model simultaneously accounts for the design and operational decisions for freshwater source selection, multiple transportation modes, and water management options. Water management options include underground injection, commercial centralized wastewater treatment (CWT), and different onsite treatment technologies. To globally optimize the resulting MILFP problem efficiently, we present three tailored solution algorithms: a parametric approach, a reformulation-linearization method, and a novel Branch-and-Bound & Charnes-Cooper transformation method. The proposed models and algorithms are illustrated through one case study based on Marcellus shale play, in which onsite treatment shows its superiority in improving freshwater conservancy, maintaining a stable water flow, and reducing transportation burden. 1. Introduction Natural gas is playing a significant role in meeting global energy demand, and is also serving as a transition fuel as the U.S. develops more sustainable fuel options. Shale gas is unconventional natural gas extracted from shale rock and has emerged as one of the most promising energy sources within the past decade. In 2012, 35% of the U.S. natural gas production was from shale gas (EIA, 2011). With increasing production of shale gas, the U.S. has changed from an importer to a net exporter of natural gas (EIA, 2013). The recent large-scale production of shale gas would not have been possible without the development of hydraulic fracturing and horizontal drilling technologies (Gregory et al., 2011). Despite the economic potential of using hydraulic fracturing and horizontal drilling technologies for shale gas production, there are increasing concerns about its environmental impacts (Kotek and Tabasb, 2013). In 2006, about 35,000 shale wells were drilled in the U.S., and each well required approximately 4-6 million gallons of injected water for shale gas production (Jiang et al., 2013). Meanwhile, in shale plays such as Marcellus, 10%- 25% of the injected water flows back to the surface as highly contaminated water. This water contains a high concentration of total dissolved solids (TDS) as well as other toxic and radioactive dissolved constituents (Karapataki, 2012), which is challenging and costly to treat. Economical production of shale gas requires effective wastewater management to minimize freshwater consumption while ensuring sufficient water supply to fracturing operations. Due to different water flow rates and water compositions in the shale wells, it is very important to determine the corresponding optimal strategies for water management. Water from freshwater sources is transported to shale sites by pipelines or trucks. At shale sites, fracturing fluid is prepared and pumped into the wellbore at a high pressure, meanwhile a certain amount of the injected fracturing fluid returns to the surface as flowback water. This flowback water can be classified by the DOI: 10.3303/CET1543238 Please cite this article as: Gao J., You F., 2015, Milfp model and algorithms for network design and long-term planning of water management system for shale gas production, Chemical Engineering Transactions, 43, 1423-1428 DOI: 10.3303/CET1543238 1423 concentration of TDS (Slutz et al., 2012). The resulting wastewater can be temporarily stored in tanks or impoundments, transported to Class II disposal wells for underground injection, transported to commercial centralized wastewater treatment (CWT) facilities for treatment, or directly treated by onsite treatment facilities for reuse (Veil, 2010). Multiple technologies are involved in each of these water management options. In this work, we propose a novel mixed-integer linear fractional programming (MILFP) model for the optimal design and operations of water supply chain networks for shale gas production. We consider a fractional function as the objective, the numerator of which is the profit for shale gas production and the denominator is the net freshwater consumption. This objective function reflects the profit associated with unit net consumption of freshwater. The model takes into account both strategic design and operational planning decisions of water supply chain networks for shale gas production. To facilitate the solution process of resulting MILFP problem, we present three tailored global optimization algorithms: a parametric algorithm based on the exact Newton’s method, a reformulation-linearization method, and an algorithm integrating the Branch-and-Bound and Charnes-Cooper transformation methods. One case study based on Marcellus shale play is given to demonstrate the proposed optimization model and algorithms. 2. Model Formulation In this section, we present the MILFP model to address the optimal design and operations of water supply chain networks for shale gas production. A mixed-integer linear programming (MILP) model is also presented. The MILFP model (P) maximizes the profit per unit freshwater consumption, which is subject to six types of constraints: mass balance constraints, cost constraints, capacity constraints, composition constraints, lower and upper bounding constraints, and logic constraints. The MILP model (EP) minimizes the total cost of this water supply chain network, which is subject to the same constraints as in MILFP model (P). MILFP problem (P) MILP problem (EP) max NP cw npf nf − = (1) min given in equationcw (8) s.t. mass balance constraints (2) s.t. mass balance constraints (9) cost constraints (3) cost constraints (10) capacity constraints (4) capacity constraints (11) composition constraints (5) composition constraints (12) bounding constrains (6) bounding constrains (13) logic constrains (7) logic constrains (14) The term NP stands for the total net present revenue gained by shale gas production, which is calculated by, , , , , , , (1 ) i t i j l t i j t t i I j J l L t T SP WP CC NP DR∈ ∈ ∈ ∈ ⋅ ⋅ = + (15) where SPi,t denotes the average revenue per unit shale gas production at shale site i at time period t; WPi,j,l,t denotes the TDS concentration range l wastewater production profile for well j at shale site i at time period t; CCi,j,t is the correlation coefficient between water and shale gas production profiles for well j at shale site i at time period t; and DR is the discount rate per time period. The term cw stands for the total net present cost in the water supply chain, including the following items: water transport handlingcw c c c= + + (16) where cwater denotes the total net present cost for freshwater acquisition; ctransport denotes the total net present cost for water transportation, including both freshwater and wastewater; and ctreatment denotes the total net present cost for handling wastewater by different options. The term nf denotes the net freshwater consumption. Since the water treated by CWT facilities can be directly sent to surface discharge, the discharged water returns to the natural water cycle and does not count as net freshwater consumption. Thus, the net freshwater consumption is given by, , , , ,s i m t c t s S i I m M t T c C t T nf fw wtcd ∈ ∈ ∈ ∈ ∈ ∈ = −    (17) 1424 3. Solution Approaches In this section, we present three tailored global optimization algorithms for efficient solution of this MILFP problem, namely a parametric algorithm, a reformulation-linearization method, and a Branch-and-Bound algorithm that integrates with Charnes-Cooper transformation (Charnes and Cooper, 1962). 3.1 Parametric algorithm The main idea of this algorithm is to transform the original MILFP problem into an equivalent parametric MILP problem F(q). This problem has the same constraints but a different objective function formulated as the numerator of the original objective function minus the denominator multiplied by a parameter q. When F(q)=0, the inner MILP problem has a unique optimal solution which is exactly the same as the global optimal solution to the original MILFP problem (You et al., 2009). Therefore, solving the MILFP problem becomes equivalent to finding the root of the equation F(q)=0. Though F(q) does not have a closed-form analytical expression, we can apply numerical root-finding approaches such as Newton’s method to solve this problem (Zhong and You, 2014). In this work, we apply the parametric algorithm based on the exact Newton’s method. 3.2 Reformulation-linearization algorithm The reformulation-linearization approach integrates the Charnes-Cooper transformation with Glover’s linearization scheme (Glover, 1975). The key idea is to transform the original MILFP problem into an exactly equivalent MILP problem by introducing auxiliary variables and constraints (Yue et al., 2013). To do this, we first apply Charnes-Cooper transformation to reformulate the original MILFP problem into an equivalent MINLP problem. Glover’s linearization is then employed to convert bilinear terms and corresponding constraints into linear ones. Thus, an exactly equivalent MILP problem is obtained based on the MINLP problem, which can be solved efficiently using the Branch-and-Cut algorithm implemented in solvers like CPLEX. This approach only needs to solve the reformulated MILP once, but the reformulated MILP problem has a larger size than the original MILFP problem, which might need substantially more computational time (Yue et al., 2013). 3.3 Branch-and-Bound & Charnes-Cooper transformation algorithm The Branch-and-Bound & Charnes-Cooper transformation algorithm integrates the Branch-and-Bound algorithm (Gupta and Ravindran, 1985) and the Charnes-Cooper transformation method (Charnes and Cooper, 1962). Since MILFP problems are a special class of MINLP problems, we are able to apply a similar Branch- and-Bound algorithm for solving general MINLP problems to the global optimality of MILFP problems. The procedure of the proposed Branch-and-Bound & Charnes-Cooper transformation algorithm is introduced step- by-step in Table 1. Table 1. Pseudocode of the Branch-and-Bound & Charnes-Cooper transformation algorithm 1: Initialization. Set bestfound = -Inf, bestpossible = +Inf 15: if the objective value > bestfound, then 2: Relax the MILFP problem to obtain the relaxed LFP problem 16: Set bestfound = obj 3: Add node 1 to the waiting list Set upper bound of node 1 = +Inf 17: Remove all the nodes in the waiting list with their bound < bestfound 4: for node n=1,2,… in the waiting list, do 18: end if 5: if node n has the highest bound, then 19: else 6: Remove this node from the waiting list 20: Select the variable wj farthest from 0 and u 7: Transform the LFP to an equivalent LP by applying Charnes-Cooper transformation and introducing auxiliary variables 21: Create two new nodes based on the current one with 0jw ≤ and jw u≥ , respectively 8: Import bounding constraints { } { } 0 0 ; 1j j j jw j J y w u j J y= ∈ = = ∈ = 22: Store the new nodes in the waiting list 9: Solve the LP subproblem 23: end if 10: if solver encounters an error, then 24: else if this subproblem is infeasible, then 11: Abort this iteration 25: Abort and fathom this node 12: else if a feasible solution is obtained, then 26: end if 13: if all the variables wj =0 or u, then 27: end if 14: Store as a new integer solution 28: end for 4. Case studies To illustrate the application of the proposed models and solution approaches, we present one case study based on Marcellus shale play. All the models and solution procedures are coded in GAMS 24.2.2. The MILP 1425 problems are solved using CPLEX 12.6. The MINLP solvers utilized are DICOPT and SBB as well as the global optimizers SCIP 3 and BARON 12. All the input data are directly or indirectly derived from literature (Maenza and Posti, 2013). In this case study, we consider a network with 2 freshwater sources, 3 shale sites, and 10 wells in each site. Freshwater withdrawal availability is estimated based on historical data with a consideration of seasonal fluctuation (Yang and Grossmann, 2013). There are 3 different CWT facilities and 10 available disposal wells. Wastewater is classified into 3 different TDS concentration ranges based on the TDS concentration constraints of different treatment technologies, ranging from 0 to 20,000 mg/L, 20,000 to 40,000 mg/L, and greater than 40,000 mg/L, respectively (Gaudlip and Paugh, 2008). We note that for Marcellus shale play, available disposal wells are mainly located far away from the shale sites in Pennsylvania (e.g. in Ohio), which are not preferable due to the high transportation cost. There are 3 levels of onsite treatments. To be more specific, we consider the sequential treatment processes including coagulation, flocculation, and disinfection steps for the primary treatment; the application of hydrated lime (Ca(OH)2) and corresponding clarifier and filter facilities for the secondary treatment; and thermal distillation technology for tertiary treatment. We consider pipeline and truck transportation modes for freshwater transportation from freshwater sources to shale sites. Truck is considered as the only transportation mode for wastewater from shale sites to CWT facilities and disposal wells. We also consider 3 capacity ranges for the pipelines used for transporting freshwater and 3 capacity ranges for each level of onsite treatment facilities. The planning horizon is 10 years. Table 2. Summary of model statistics and computational results for case study 1 Discrete variables Continuous variables Constraints Objective value Solution time (CPUs) MILFP problem (P) Parametric 297 158,213 208,080 14,970 27 R-L 297 158,510 208.970 14,970 294 B&B + C-C 0a 158,213 208,080 14,970 11,272 DICOPT 297 158,213 208,080 14,970 7,180 SBB 297 158,213 208,080 14,970 29,486 SCIP 3 297 158,213 208,080 N/Ab N/Ab BARON 12 297 158,213 208,080 N/Ab N/Ab MILP problem (EP) CPLEX 12.6 297 158,213 208,080 4,533,300 5 a. For each iteration after reformulation and relaxation, there are no discrete variables. b. Solver failure encountered. As can be seen in Table 2, all of these solution methods return the same optimal solution to the MILFP problem (P), except SCIP 3 and BARON 12. The parametric algorithm based on the exact Newton’s method is the most efficient algorithm. It takes only three iterations and a total of 27 CPUs to converge to the global optimal solution. The reformulation-linearization algorithm also has excellent computational performance with a computational time of 294 CPUs. The Branch-and-Bound & Charnes-Cooper transformation algorithm returns the same objective value as the other approaches in 11,272 CPUs with a total of 183 nodes fathomed in the Branch-and-Bound tree. For the MILP problem (EP), the objective of which is to minimize the total cost, we directly apply the MILP solver CPLEX 12.6 to solve the problem with only 5 CPUs. Figure 4. Water supply chain network comparison between (a) MILFP problem (P) and (b) MILP problem (EP) 1426 As can be seen in Figure 4, in problem (P), all the three-level onsite treatments are applied, while in (EP), tertiary treatment is not chosen. Therefore, more wastewater is transported to the CWT for treatment and discharge. As to the freshwater acquisition, in problem (P), a total of 5,268,306 barrels of freshwater is withdrawn from freshwater source 1 over the 10-year time horizon. In contrast, 5,912,385 barrels of freshwater is withdrawn in (EP), which is 12% more than that in problem (P), resulting in 11% higher water supply cost. Obviously, the freshwater consumption and the corresponding cost are significantly reduced in problem (P). Detailed water management strategy is given in Figure 5. The water management strategies for both problem (P) and (EP) share some common features: disposal wells are not employed due to the long-distance transportation cost; CWT as well as onsite treatment options are applied to treat the wastewater; the treatment load for onsite treatment is relatively stable, while the amount of wastewater treated by CWT fluctuates with time; storage option behaves as a “buffer” to compensate the gap of wastewater treatment amount of CWT. The major difference between these two water management strategies is the preference of onsite treatment over the CWT. In problem (P), the amount of wastewater treated onsite and reused is almost twice as much as that in MILP problem (EP). As a result, less wastewater is transported to CWT facilities for treatment, and the inventory level is lower in the MILFP problem (P). Consequently, less water is reused onsite or recycled from CWT facilities, and more freshwater is required at each time period in the MILP problem (EP). Figure 5. Water management strategy comparison between (a) MILFP problem (P) and (b) MILP problem (EP) Table 3. Cost breakdown of water management options in MILFP problem (P) and MILP problem (EP) Water acquisition Transportation Onsite treatment CWT Storage MILFP problem (P) 3% 6% 79% 11% 1% MILP problem (EP) 4% 29% 13% 51% 3% The overall cost distribution of different water management sections is given by Table 3. The profit gained corresponding to unit freshwater consumption is $14,970 per thousand barrels of freshwater consumption in problem (P), 14% greater than $13,084 per thousand barrels of freshwater consumption in problem (EP), indicating a higher freshwater utilization efficiency. As to the detailed breakdown of total water management cost, the CWT facilities contribute 11% of the overall cost for water management in problem (P), while in (EP), this number is 51%; onsite treatment accounts for 79% of the total cost in problem (P), while in problem (EP) only 13% of the total cost comes from onsite treatment. Due to the extensive application of onsite treatment and reuse in MILFP problem (P), the stress on freshwater withdrawal, related transportation, and onsite storage is relieved. As a result, the costs of freshwater acquisition, storage, and transportation in problem (P) are all lower than those in problem (EP). Based on the comparison above, we conclude that it is impossible to obtain a good balance between cost effectiveness and freshwater conservancy by simply minimizing the total cost. In the MILP problem (EP), most of the wastewater is transported to the CWT for treatment and direct discharge. In contrast, the fractional objective function in problem (P) gives a more efficient and practical water management strategy with more water reuse, less freshwater consumption, and less stress on transportation and storage. Such a water management strategy is close to the real one applied at Marcellus shale play (Wilson and VanBriesen, 2012). 1427 5. Conclusions In this paper, we presented a novel optimization model for the optimal design and operations of water supply chain networks for shale gas production. The objective function was given as the profit per unit freshwater consumption. Such a problem was formulated as an MILFP problem. While the models were general enough to consider multiple water management options, we focused on the disposal, CWT, and onsite treatment options in this work. Furthermore, three levels of onsite treatment were considered. To illustrate the proposed models and solution methods, one case study was presented based on Marcellus shale play. The optimal water management strategies obtained from MILFP problem (P) and MILP problem (EP) were carefully analyzed and discussed. The superiority of problem (P) over problem (EP) was validated. Moreover, the onsite treatment option turned out to be appealing in improving freshwater conservancy, maintaining a stable water flow, and reducing transportation burden. The computational results indicated the outstanding efficiency of the parametric algorithm in solving large-scale MILFP problems. References Charnes A., Cooper W.W., 1962, Programming with linear fractional functionals, Naval Research Logistics Quarterly, 9(3-4), 181-186. EIA (2011) Review of emerging resources: U.S. shale gas and shale oil plays, Energy Information Administration. Washington, DC: U. S. EIA (2013) Annual Energy Outlook 2013, Washington, DC 20585: U. S. Energy Information Administration. Gaudlip A. W., Paugh L. O., Marcellus Shale Water Management Challenges in Pennsylvania, Shale Gas Production Conference, Fort Worth, Texas 16-18. Glover F., 1975, Improved linear integer programming formulations of nonlinear integer problems. Management Science, 22, 455-460. Gregory K. B., Vidic R. D., Dzombak D. A., 2011, Water Management Challenges Associated with the Production of Shale Gas by Hydraulic Fracturing, Elements, 7(3), 181-186. Gupta O. K., Ravindran A., 1985, Branch and Bound Experiments in Convex Nonlinear Integer Programming, Management Science, 31(12), 1533-1546. Jiang M., Hendrickson C. T., VanBriesen J. M., 2013, Life Cycle Water Consumption and Wastewater Generation Impacts of a Marcellus Shale Gas Well, Environmental Science & Technology, 48, 1911-1920. Karapataki C., 2012, Techno-economic analysis of water management options for unconventional natural gas developments in the Marcellus Shale. Master thesis, Massachusetts Institute of Technology, Cambridge, MA 02139-4307. Kotek L., Tabasb M., 2013, Prevention of Major Accidents of the Aboveground Parts of Natural Gas Storage Technologies and Shale Gas Production Facilities, Chemical Engineering Transactions, 31. Maenza T., Posti J., 2013. Pennsykvania american water announces $16.5 million investment to construct and rehab water storage tanks. Pennsylvania American Water. Slutz J. A., Anderson J. A., Broderick R., Horner P. H., Key Shale Gas Water Management Strategies: An Economic Assessment. International Conference on Health Safety and Environment in Oil and Gas Exploration and Production: Society of Petroleum Engineers. Veil J. A., 2010, Final Report Water Management Technologies Used by Marcellus Shale Gas Producers, Argonne, IL: U.S. Department of Energy. Wilson J. M., VanBriesen J. M., 2012, Oil and Gas Produced Water Management and Surface Drinking Water Sources in Pennsylvania, Environmental Practice, 14(04), 288-300. Yang L., Grossmann I. E., Superstructure-Based Shale Play Water Management Optimization. AIChE Annual Meeting, San Francisco, CA. You F., Castro P.M., Grossmann I.E., 2009, Dinkelbach's algorithm as an efficient method to solve a class of MINLP models for large-scale cyclic scheduling problems. Computers & Chemical Engineering, 33, 1879- 1889. Yue D., Guillen-Gosalbez G., You F., 2013, Global Optimization of Large-Scale Mixed-Integer Linear Fractional Programming Problems: A Reformulation-Linearization Method and Process Scheduling Applications, AIChE Journal, 59(11), 4255-4272. Yue D., Kim M.A., You F. (2013). Design of Sustainable Product Systems and Supply Chains with Life Cycle Optimization Based on Functional Unit: General Modeling Framework, Mixed-Integer Nonlinear Programming Algorithms and Case Study on Hydrocarbon Biofuels. ACS Sustainable Chemistry & Engineering, 1, 1003-1014. Zhong Z., You F., 2014, Globally convergent exact and inexact parametric algorithms for solving large-scale mixed-integer fractional programs and applications in process systems engineering, Computers & Chemical Engineering, 61, 90-101. 1428