Power generation planning in hydrothermal systems is a complex optimization task, specially due to the high uncertainty in the inflows to hydro plants. Since it is impossible to traverse the huge scenario tree of the ...
详细信息
Power generation planning in hydrothermal systems is a complex optimization task, specially due to the high uncertainty in the inflows to hydro plants. Since it is impossible to traverse the huge scenario tree of the multistage problem, stochastic dual dynamic programming (SDDP) is the leading technique to solve it, originally from an expected-cost minimization perspective. However, there is a growing need to apply risk-averse/robust formulations to protect the system from critical hydrological scenarios. This is particularly important for predominantly hydro systems, because environmental issues prevent the construction of large reservoirs, thus reducing their water regulating capability. This paper proposes a two-level SDDP/Benders decomposition approach to include a new risk averse surface (RAS) concept for reservoir operation in power generation planning. The upper level problem is a SDDP solving strategy with expected-cost minimization criterion, where recourse functions for each time step are built through forward/backward passes. The second level consists in multi-period deterministic optimization subproblems for each node of the scenario tree, which are solved to ensure a desired level of protection from a set of given critical scenario several months ahead. An inner iterative procedure for each SDDP stage/scenario is applied, where feasibility cuts are included in the upper level subproblems to derive the RAS surface, which are multidimensional rule curves for reservoir operation. Such curves ensure that the policy provided by the SDDP algorithm yields storage levels in the reservoirs that are high enough to protect the system against such critical scenarios. A "max-type" time-linking penalization scheme for violation of RAS constraints is also proposed, which avoids the multiple application of the penalty value for the same violation in consecutive time steps, which may result in large marginal costs. Results are presented for the large-scale Brazilian sys
The paper is devoted to a scalability study of the NSLP algorithm for solving non-stationary high-dimension linearprogramming problem on the cluster computing systems. The analysis is based on the BSF model of parall...
详细信息
ISBN:
(纸本)9783319712543;9783319712550
The paper is devoted to a scalability study of the NSLP algorithm for solving non-stationary high-dimension linearprogramming problem on the cluster computing systems. The analysis is based on the BSF model of parallel computations. The BSF model is a new parallel computation model designed on the basis of BSP and SPMD models. The brief descriptions of the NSLP algorithm and the BSF model are given. The NSLP algorithm implementation in the form of a BSF program is considered. On the basis of the BSF cost metric, the upper bound of the NSLP algorithm scalability is derived and its parallel efficiency is estimated. NSLP algorithm implementation using BSF skeleton is described. A comparison of scalability estimations obtained analytically and experimentally is provided.
The Big Data phenomenon has spawned large-scale linear programming problems. In many cases, these problems are nonstationary. In this paper, we describe a new scalable algorithm called NSLP for solving high-dimensiona...
详细信息
ISBN:
(纸本)9783319670355;9783319670348
The Big Data phenomenon has spawned large-scale linear programming problems. In many cases, these problems are nonstationary. In this paper, we describe a new scalable algorithm called NSLP for solving high-dimensional, non-stationary linearprogramming problems on modern cluster computing systems. The algorithm consists of two phases: Quest and Targeting. The Quest phase calculates a solution of the system of inequalities defining the constraint system of the linearprogramming problem under the condition of dynamic changes in input data. To this end, the apparatus of Fejer mappings is used. The Targeting phase forms a special system of points having the shape of an n-dimensional axisymmetric cross. The cross moves in the n-dimensional space in such a way that the solution of the linearprogramming problem is located all the time in an e-vicinity of the central point of the cross.
The paper describes a new scalable algorithm called NSLP for high-dimension, non-stationary linearprogramming problem solving on the modern cluster computing systems. The algorithm consists of two phases: Quest and T...
详细信息
ISBN:
(纸本)9781538605219
The paper describes a new scalable algorithm called NSLP for high-dimension, non-stationary linearprogramming problem solving on the modern cluster computing systems. The algorithm consists of two phases: Quest and Targeting. The Quest phase calculates a solution for the system of inequalities defining the constraint system of the linearprogramming problem under the condition of the input data dynamic changes. To do this, it uses the apparatus of Fejer maps. The Targeting phase forms a special system of points having the shape of the n-dimensional axisymmetric cross. The cross moves in the n-dimensional space in such a way that the solution of the linearprogramming problem is permanently in the epsilon-vicinity of the cross central point.
We describe an active-set, cutting-plane approach called Constraint Optimal Selection Techniques (COSTs) and develop an efficient new COST for solving nonnegative linearprogramming problems. We give a geometric inter...
详细信息
We describe an active-set, cutting-plane approach called Constraint Optimal Selection Techniques (COSTs) and develop an efficient new COST for solving nonnegative linearprogramming problems. We give a geometric interpretation of the new selection rule and provide computational comparisons of the new COST with existing linearprogramming algorithms for some large-scale sample problems. (C) 2014 Elsevier Inc. All rights reserved.
We study a class of linearprogramming (LP) problems motivated by large-scale machine learning applications. After reformulating the LP as a convex nonsmooth problem, we apply Nesterov's primal-dual excessive-gap ...
详细信息
We study a class of linearprogramming (LP) problems motivated by large-scale machine learning applications. After reformulating the LP as a convex nonsmooth problem, we apply Nesterov's primal-dual excessive-gap technique. The iteration complexity of the excessive-gap technique depends on a parameter theta that arises because we must bound the primal feasible set, which is originally unbounded. We also dynamically update theta to speed up the convergence. The application of our algorithm to two machine learning problems demonstrates several advantages of the excessive-gap technique over existing methods.
Recently, computational results demonstrated remarkable superiority of a so-called ＂largest-distance＂ rule and ＂nested pricing＂ rule to other major rules commonly used in practice, such as Dantzig＇s original rule...
详细信息
Recently, computational results demonstrated remarkable superiority of a so-called ＂largest-distance＂ rule and ＂nested pricing＂ rule to other major rules commonly used in practice, such as Dantzig＇s original rule, the steepest-edge rule and Devex rule. Our computational experiments show that the simplex algorithm using a combination of these rules turned out to be even more efficient.
The integrated refinery-planning (IRP), an instrumental problem in the petroleum industry, is made of several subsystems, each of them involving a large number of decisions. Despite the complexity of the overall plann...
详细信息
The integrated refinery-planning (IRP), an instrumental problem in the petroleum industry, is made of several subsystems, each of them involving a large number of decisions. Despite the complexity of the overall planning problem, this work presents a mathematical model of the refinery operations characterized by complete horizontal integration of subsystems from crude oil purchase through to product distribution. This is the main contribution from a modelling point of view. The IRP, with a planning horizon ranging from 2 to 300 days. results in a large-scale linear programming (LP) problem of up to one million constraints, 2.5 million variables and 59 millions of nonzeroes in the constraint matrix. large instances become computationally challenging for generic state-of-the-art LP solvers, such as CPLEX. To avoid this drawback, after the identification of the nonzero structure of the constraints matrix, structure-exploiting techniques such as Dantzig-Wolfe and block coordinate-descent decomposition were applied to IRP. It was also observed that interior-point methods are far more efficient than simplex ones in large IRP instances. These were the main contributions from the optimization viewpoint. A set of realistic instances were dealt with generic algorithms and these two decomposition methods. In particular the block coordinate-descent heuristic, with a reverse order of the subsystems, appeared as a promising approach for very large integrated refinery problems, obtaining either the optimal or an approximate feasible solution in all the instances tested. (c) 2008 Elsevier Ltd. All rights reserved.
In this paper, a multi-period stochastic optimization model for solving a problem of optimal selection of a pension fund by a pension plan member is presented. In our model, members of the pension plan are given a pos...
详细信息
In this paper, a multi-period stochastic optimization model for solving a problem of optimal selection of a pension fund by a pension plan member is presented. In our model, members of the pension plan are given a possibility to switch periodically between J types of funds with different risk profiles and so actively manage their risk exposure and expected return. Minimization of a multi-period average value-at-risk deviation measure under expected return constraint leads to a large-scalelinear program. A theoretical framework and a solution for the case of the pension system of Slovak Republic are presented.
The standard basis, which plays a fundamental role in simplex methodology, was recently extended to include a deficient case (with fewer columns than rows) by taking advantage of primal degeneracy. Computational resul...
详细信息
The standard basis, which plays a fundamental role in simplex methodology, was recently extended to include a deficient case (with fewer columns than rows) by taking advantage of primal degeneracy. Computational results have been favorable with dense implementations. In this paper, we propose a primal simplex algorithm using sparse LU factors of deficient bases. Amenable to real-world linearprogramming problems, which are often degenerate or even highly degenerate, the algorithm would solve them with potentially improved stability compared to the simplex algorithm. The proposed algorithm has been implemented and tested on a set of 50 Netlib test problems as well as a set of 15 much larger real-world problems, including 8 Kennington and 5 BPMPD problems. It significantly outperformed MINOS 5.3 in terms of both iteration counts and run time. In particular,. these results reveal that there is no inevitable correlation between an algorithm's inefficiency and degeneracy (contradicting common belief). (C) 2007 Elsevier Inc. All rights reserved.
暂无评论