An application of Karmarkar's interior-point linear programming algorithm for multi-reservoir operations optimization

Optimization of multi-reservoir systems operations is typically a very large scale optimization problem. The following are the three types of optimization problems solved using linear programming (LP): (i) deterministic optimization for multiple periods involving fine stage intervals, for example, from an hour to a week (ii) implicit stochastic optimization using multiple years of inflow data, and (iii) explicit stochastic optimization using probability distributions of inflow data. Until recently, the revised simplex method has been the most efficient solution method available for solving large scale LP problems. In this paper, we show that an implementation of the Karmarkar's interior-point LP algorithm with a newly developed stopping criterion solves optimization problems of large multi-reservoir operations more efficiently than the simplex method. For example, using a Micro VAX II minicomputer, a 40 year, monthly stage, two-reservoir system optimization problem is solved 7.8 times faster than the advanced simplex code in MINOS 5.0. The advantage of this method is expected to be greater as the size of the problem grows from two reservoirs to multiples of reservoirs. This paper presents the details of the implementation and testing and in addition, some other features of the Karmarkar's algorithm which makes it a valuable optimization tool are illuminated.     

Stochastic differential dynamic programming for multi-reservoir system control

: As with all dynamic programming formulations, differential dynamic programming (DDP) successfully exploits the sequential decision structure of multi-reservoir optimization problems, overcomes difficulties with the nonconvexity of energy production functions for hydropower systems, and provides optimal feedback release policies. DDP is particularly well suited to optimizing large-scale multi-reservoir systems due to its relative insensitivity to state-space dimensionality. This advantage of DDP encourages expansion of the state vector to include additional multi-lag hydrologic information and/or future inflow forecasts in developing optimal reservoir release policies. Unfortunately, attempts at extending DDP to the stochastic case have not been entirely successful. A modified stochastic DDP algorithm is presented which overcomes difficulties in previous formulations. Application of the algorithm to a four-reservoir hydropower system demonstrates its capabilities as an efficient approach to solving stochastic multi-reservoir optimization problems. The algorithm is also applied to a single reservoir problem with inclusion of multi-lag hydrologic information in the state vector. Results provide evidence of significant benefits in direct inclusion of expanded hydrologic state information in optimal feedback release policies.     

Stochastic differential dynamic programming for multi-reservoir system control

: As with all dynamic programming formulations, differential dynamic programming (DDP) successfully exploits the sequential decision structure of multi-reservoir optimization problems, overcomes difficulties with the nonconvexity of energy production functions for hydropower systems, and provides optimal feedback release policies. DDP is particularly well suited to optimizing large-scale multi-reservoir systems due to its relative insensitivity to state-space dimensionality. This advantage of DDP encourages expansion of the state vector to include additional multi-lag hydrologic information and/or future inflow forecasts in developing optimal reservoir release policies. Unfortunately, attempts at extending DDP to the stochastic case have not been entirely successful. A modified stochastic DDP algorithm is presented which overcomes difficulties in previous formulations. Application of the algorithm to a four-reservoir hydropower system demonstrates its capabilities as an efficient approach to solving stochastic multi-reservoir optimization problems. The algorithm is also applied to a single reservoir problem with inclusion of multi-lag hydrologic information in the state vector. Results provide evidence of significant benefits in direct inclusion of expanded hydrologic state information in optimal feedback release policies.     

A split operator approach to reactive transport with the forward particle tracking Eulerian Lagrangian localized adjoint method

A forward particle tracking Eulerian Lagrangian localized adjoint method (ELLAM) is applied to the multicomponent reactive transport problem using a split operator approach. Two split operator algorithms are compared, the Strang algorithm and the sequential non-iterative algorithm (SNIA). The reaction equations are integrated using a coupled predictor corrector algorithm with adaptive time stepping. Reaction time steps are adjusted at the inflow boundary to reflect the actual time of transport inside the solution domain.Results show that split operator ELLAM formulations are competitive with direct or fully coupled ELLAM solutions for reactive transport problems. The SNIA algorithm is more accurate than the Strang splitting algorithm when large time steps are used. The reaction algorithm employed dominates computational effort in runs with large time step sizes. To illustrate the use of the method in practical problems, the model is fitted to aerobic aniline degradation data from laboratory scale column experiments. Model inversion is achieved using non-linear regression with a shuffled complex evolution optimization algorithm and parameter uncertainty is assessed using a Bayesian uncertainty analysis procedure.     

On the implementation of Prabhu’s exact solution of the stochastic reservoir equation

After 50 years of Prabhu’s paper on the exact solution of the stochastic reservoir equation for the important class of gamma inflow distributions with an integral shape parameter, a detailed implementation of the exact solution is still lacking, despite its potential usefulness from both theoretical and practical points of view. This paper explores some properties of Prabhu’s exact solution and investigates the numerical difficulties associated with its implementation. The solution is also extended to derive the distributions of deficit, spillage, yield, and actual release from the reservoir. Explicit analytical solutions for three relatively simple cases are given in detail as examples and comparisons with approximate numerical solutions are made, which reveal some shortcomings of approximate methods. The implementation of the solution in the general case reveals some numerical problems associated with large values of the shape parameter of the inflow distribution and large ratios of reservoir size to draft, mainly due to accumulation of round-off errors. A Matlab program has been developed to calculate emptying and filling probabilities over a wide range of reservoir parameters using extended precision. Comparison of Prabhu’s solution with the numerical solution of the reservoir integral equation highlights possible problems with the numerical solution, which may produce inaccurate or even invalid results for large reservoirs, large drift, and large skewness of the inflow distribution. A comparison between gamma and lognormal distributions as models of skew revealed that as the reservoir size, drift, and skewness increase, the probability of emptying of the reservoir becomes smaller for the case of gamma inflow than in the case of lognormal flow having the same skewness coefficient.     

Application of the gravity search algorithm to multi-reservoir operation optimization

Complexities in river discharge, variable rainfall regime, and drought severity merit the use of advanced optimization tools in multi-reservoir operation. The gravity search algorithm (GSA) is an evolutionary optimization algorithm based on the law of gravity and mass interactions. This paper explores the GSA's efficacy for solving benchmark functions, single reservoir, and four-reservoir operation optimization problems. The GSA's solutions are compared with those of the well-known genetic algorithm (GA) in three optimization problems. The results show that the GSA's results are closer to the optimal solutions than the GA's results in minimizing the benchmark functions. The average values of the objective function equal 1.218 and 1.746 with the GSA and GA, respectively, in solving the single-reservoir hydropower operation problem. The global solution equals 1.213 for this same problem. The GSA converged to 99.97% of the global solution in its average-performing history, while the GA converged to 97% of the global solution of the four-reservoir problem. Requiring fewer parameters for algorithmic implementation and reaching the optimal solution in fewer number of functional evaluations are additional advantages of the GSA over the GA. The results of the three optimization problems demonstrate a superior performance of the GSA for optimizing general mathematical problems and the operation of reservoir systems.     

2D多尺度非线性地震速度成像

将遗传算法和单纯形算法相结合,得到了一种高效、健全的2D混合地震走时反演方法.把速度场划分为不同的空间尺度,定义网格节点上的速度作为待反演参数,采用双三次样条函数模型参数化,正问题采用有限差分走时计算方法,反问题采用多尺度混合反演方法.首先在较大的空间尺度内反演,然后减小空间尺度,将大尺度的反演结果作为次一级尺度反问题的初始模型,再进行混合反演,如此类推逐次逼近全局最优解.一个低速度异常体的数值模拟试验和抗走时扰动试验表明该方法是有效和健全的.我们将该方法应用到青藏高原东北缘阿尼玛卿缝合带东段上部地壳速度结构研究中,并与前人的成果进行了对比.     

Optimal operation of reservoirs for downstream water quality control using linked simulation optimization

A methodology is developed for optimal operation of reservoirs to control water quality requirements at downstream locations. The physicochemical processes involved are incorporated using a numerical simulation model. This simulation model is then linked externally with an optimization algorithm. This linked simulation–optimization‐based methodology is used to obtain optimal reservoir operation policy. An elitist genetic algorithm is used as the optimization algorithm. This elitist‐genetic‐algorithm‐based linked simulation–optimization model is capable of evolving short‐term optimal operation strategies for controlling water quality downstream of a reservoir. The performance of the methodology developed is evaluated for an illustrative example problem. Different plausible scenarios of management are considered. The operation policies obtained are tested by simulating the resulting pollutant concentrations downstream of the reservoir. These performance evaluations consider various scenarios of inflow, permissible concentration limits, and a number of management periods. These evaluations establish the potential applicability of the developed methodology for optimal control of water quality downstream of a reservoir. Copyright © 2007 John Wiley & Sons, Ltd.     

频率域电磁法三维有限元正演线性方程组迭代算法

在三维频率域电磁法的正演模拟方法中,有限元方法具有计算精度高、适应性强的优点,近年来来得到了越来越多的关注.在正演过程中,主要的计算量集中在求解由偏微分方程组离散得到的线性方程组上,因此求解线性方程组关系着正演计算速度以及模拟精度.由于由有限元方法离散得到的复系数线性方程组条件数非常大,使用常规的迭代法和预条件很难收敛.目前大多数的研究工作采用直接解法,需要大量的计算机内存,限制了可求解问题的规模.本文研究了线性方程组的迭代解法,通过将复系数线性方程组转化为其实对称形式,构造分块对角预条件.在应用预条件的过程中,需要求解两个较小的实数方程,通过辅助空间解法求解.本文的算法适用于可控源电磁法和大地电磁法,对一系列的数值算例的模拟结果证明了迭代算法的效率,结果表明迭代算法可以在小于20次迭代内收敛,同时迭代次数与模型电阻率、问题规模和频率无关.     

CEC比值法在凝灰质砂岩储层测井评价中的应用——以海-塔盆地X凹陷凝灰质砂岩储层为例

凝灰质砂岩储层一直是测井评价中的难点.凝灰质的存在使储层的孔隙结构和物性变化都很大,其含量直接影响储层参数的求取,对储层饱和度的影响不容忽视.本文以海-塔盆地X凹陷的凝灰质砂岩储层为例进行测井评价研究.基于泥质和凝灰质的测井响应差异利用粒子群和细菌觅食的混合优化算法计算储层中两者的含量,然后通过阳离子交换量(CEC)的实验数据验证了凝灰质具有导电性,进而利用CEC与电阻率之间的关系得到凝灰质电阻率的计算方法,并且应用到饱和度的计算,最终得到了一种新的计算凝灰质砂岩储层饱和度的方法——CEC比值法,并取得了良好的应用效果.     

The role of hydrologic information in reservoir operation – Learning from historical releases

Closing the gap between theoretical reservoir operation and the real-world implementation remains a challenge in contemporary reservoir operations. Past research has focused on optimization algorithms and establishing optimal policies for reservoir operations. In this study, we attempt to understand operators’ release decisions by investigating historical release data from 79 reservoirs in California and the Great Plains, using a data-mining approach. The 79 reservoirs are classified by hydrological regions, intra-annual seasons, average annual precipitation (climate), ratio of maximum reservoir capacity to average annual inflow (size ratio), hydrologic uncertainty associated with inflows, and reservoirs’ main usage. We use information theory – specifically, mutual information – to measure the quality of inference between a set of classic indicators and observed releases at the monthly and weekly timescales. Several general trends are found to explain which sources of hydrologic information dictate reservoir release decisions under different conditions. Current inflow is the most important indicator during wet seasons, while previous releases are more relevant during dry seasons and in weekly data (as compared with monthly data). Inflow forecasting is the least important indicator in release decision making, but its importance increases linearly with hydrologic uncertainty and decreases logarithmically with reservoir size. No single hydrologic indicator is dominant across all reservoirs in either of the two regions.     

A Stochastic Inversion Method for Potential Field Data: Ant Colony Optimization

Simulating natural ants’ foraging behavior, the ant colony optimization (ACO) algorithm performs excellently in combinational optimization problems, for example the traveling salesman problem and the quadratic assignment problem. However, the ACO is seldom used to inverted for gravitational and magnetic data. On the basis of the continuous and multi-dimensional objective function for potential field data optimization inversion, we present the node partition strategy ACO (NP-ACO) algorithm for inversion of model variables of fixed shape and recovery of physical property distributions of complicated shape models. We divide the continuous variables into discrete nodes and ants directionally tour the nodes by use of transition probabilities. We update the pheromone trails by use of Gaussian mapping between the objective function value and the quantity of pheromone. It can analyze the search results in real time and promote the rate of convergence and precision of inversion. Traditional mapping, including the ant-cycle system, weaken the differences between ant individuals and lead to premature convergence. We tested our method by use of synthetic data and real data from scenarios involving gravity and magnetic anomalies. The inverted model variables and recovered physical property distributions were in good agreement with the true values. The ACO algorithm for binary representation imaging and full imaging can recover sharper physical property distributions than traditional linear inversion methods. The ACO has good optimization capability and some excellent characteristics, for example robustness, parallel implementation, and portability, compared with other stochastic metaheuristics.     

地球物理随机联合反演

基于场方程的地球物理联合反演隐含着两个基本过程:正演的联合与反演的联合。当用遗传算法解决这类问题时,它蕴含着一个反演的随机联合的过程,称之为随机联合反演。借鉴模拟退火和禁区搜索方法的思想,通过对遗传操作对象、操作过程以及迭代过程的改进,使改进后的遗传算法表现较快的收敛速率和良好的全局收敛性;通过模型数据的反演,从理论上证明改进的遗传算法能较好地解决非线性、复杂、大尺度离散反问题,使随机联合反演问题的解决成为可能。     

2D多尺度混合优化地球物理反演方法及其应用(英文)

局部优化和全局优化方法广泛应用到地球物理反演,但是两者各有其优缺点。将两类方法结合起来可以取长补短。将退火遗传算法（SAGA）和单纯形算法相结合,得到了一种高效、健全的2D非线性混合地震走时反演方法。首先,利用SAGA进行大范围的全局搜索,然后由单纯形方法进行快速局部搜索。为了降低层析成像的多解性,我们采用了多尺度逐次逼近的技巧。把速度场划分为不同的空间尺度,定义网格节点上的速度作为待反演参数,采用双三次样条函数模型参数化,正问题采用有限差分走时计算方法,反问题采用多尺度混合反演方法。一个低速度异常体的数值模拟试验和抗走时扰动试验表明该方法是有效和健全的。我们将该方法应用到青藏高原东北缘阿尼玛卿rlet,Meyer,Marr,缝合带东段上部地壳速度结构研究中。数字模型试验和实际资料的应用表明了方法的有效性和健全性。     

Coupling of finite element and optimization methods for the management of groundwater systems

The paper describes an optimization method for the solution of groundwater management problems. The method consists of a combination of the computation of horizontal plane groundwater flow with a free surface (finite element method) and a linear optimization procedure (simplex algorithm). Considering the special structure of data which result form computing the groundwater flow with the finite element method, and modifying the simplex algorithm, the solution of management problems with complex groundwater flow is realized without any difficulties. Compared to a flow computation alone the additional effort of the optimization (computer time and scope for data storage) is only small.     

Performance evaluation of implicit stochastic reservoir operation optimization supported by long-term mean inflow forecast

This study applies implicit stochastic optimization (ISO) to develop monthly operating rules for a reservoir located in Northeast Brazil. The proposed model differs from typical ISO applications as it uses the forecast of the mean inflow for a future horizon instead of the current-month inflow. Initially, a hundred different 100-year monthly inflow scenarios are synthetically generated and employed as input to a deterministic operation optimization model in order to build a database of optimal operating data. Later, such database is used to fit monthly reservoir rule curves by means of nonlinear regression analysis. Finally, the established rule curves are validated by operating the system under 100 new inflow ensembles. The performance of the proposed technique is compared with those provided by the standard reservoir operating policy (SOP), stochastic dynamic programming (SDP) and perfect-forecast deterministic optimization (PFDO). Different forecasting horizons are tested. For all of them, the results indicate the feasibility of using ISO in view of its lower vulnerability in contrast to the SOP as well as the proximity of its operations with those by PFDO. The results also reveal that there is an optimal choice for the forecasting horizon. The comparison between ISO and SDP shows small differences between both, justifying the adoption of ISO for its simplified mathematics as opposed to SDP.     

Development of operating rules for a complex multi-reservoir system by coupling genetic algorithms and network optimization

Abstract

An alternative procedure for assessment of reservoir Operation Rules (ORs) under drought situations is proposed. The definition of ORs for multi-reservoir water resources systems (WRSs) is a topic that has been widely studied by means of optimization and simulation techniques. A traditional approach is to link optimization methods with simulation models. Thus the objective here is to obtain drought ORs for a real and complex WRS: the Júcar River basin in Spain, in which one of the main issues is the resource allocation among agricultural demands in periods of drought. To deal with this problem, a method based on the combined use of genetic algorithms (GA) and network flow optimization (NFO) is presented. The GA used was PIKAIA, which has previously been used in other water resources related fields. This algorithm was linked to the SIMGES simulation model, a part of the AQUATOOL decision support system (DSS). Several tests were developed for defining the parameters of the GA. The optimization of various ORs was analysed with the objective of minimizing short-term and long-term water deficits. The results show that simple ORs produce similar results to more sophisticated ones. The usefulness of this approach in the assessment of ORs for complex multi-reservoir systems is demonstrated.

Citation Lerma, N., Paredes-Arquiola, J., Andreu, J., and Solera, A., 2013. Development of operating rules for a complex multi-reservoir system by coupling genetic algorithms and network optimization. Hydrological Sciences Journal, 58 (4), 797–812.     

非均匀介质热蠕变流动的数值求解

针对非均匀介质中热蠕变流动问题,给出了有限单元方法与网格－粒子方法联合求解新技术,即有限单元方法求解欧拉网格节点上的未知量,分布于单元内部作为物质成分标记的粒子反映变形过程.有限元法求解动量方程和连续性方程时引入了速度场和压力场等阶插值的压力场稳定的Petrov Galerkin方法,求解能量方程时采用了流线迎风Petrov Galerkin方法,网格－粒子算法中采用双线性插值与有限单元插值函数对应.有限单元计算与网格－粒子计算相对独立,两种方法计算的数据通过有限单元节点传递.同时,实现了三角形单元的算法和程序,解决了复杂结构条件下不规则网格计算的问题.通过经典方腔热对流问题验证了程序,给出了不规则形态块体沉降算例,并分析了数值解的稳定性.     

基于主成分分析方法的海量地震数据属性降维优化

针对传统的地震数据属性降维优化方法所选取的地震数据属性特征贡献率低导致降维过程计算量大、CPU占用率高等问题,提出一种基于主成分分析的海量地震数据属性降维优化方法。首先根据地震样本特征建立地震数据特征矩阵,把矩阵中的特征进行聚类,运用降序法排列聚类结果,选取前几项数据作为地震数据属性特征选取结果,对其结果评估分类信息量;通过特征积分准则(FSC)修正分类信息量,获取海量地震数据属性特征节点;运用主成分分析方法对地震数据属性特征节点主成分添加标签,确定Fisher判别分析与PCA可变动选择不确定关系,建立半监督降维的全局最优化形式,运用特征值分解计算降维结果,克服海量地震数据属性降维过程中的过拟合问题,融合主成分分析算法与Fisher判别分析算法实现海量地震数据属性降维优化。实验结果证明,所提方法选取的属性特征精度及贡献率较高,降维过程中CPU占用率较低。