检索结果-内蒙古大学图书馆

stochastic DYNAMIC LINEAR programming: A SEQUENTIAL SAMPLING ALGORITHM FOR multistage stochastic LINEAR programming\ast

引用

SIAM JOURNAL ON OPTIMIZATION 2021年第3期31卷 2111-2140页

作者： Gangammanavar, Harsha Sen, Suvrajeet Southern Methodist Univ Dept Engn Management Informat & Syst Dallas TX 75275 USA Univ Southern Calif Epstein Dept Ind & Syst Engn Los Angeles CA 90089 USA

multistage stochastic programming deals with operational and planning problems that involve a sequence of decisions over time while responding to an uncertain future. Algorithms designed to address multistage stochastic linear programming (MSLP) problems often rely upon scenario trees to represent the underlying stochastic process. When this process exhibits stagewise independence, sampling-based techniques, particularly the stochastic dual dynamic programming algorithm, have received wide acceptance. However, these sampling-based methods still operate with a deterministic representation of the problem which uses the so-called sample average approximation. In this work, we present a sequential sampling approach for MSLP problems that allows the decision process to assimilate newly sampled data recursively. We refer to this method as the stochastic dynamic linear programming (SDLP) algorithm. Since we use sequential sampling, the algorithm does not necessitate a priori representation of uncertainty, through either a scenario tree or sample average approximation, both of which require a knowledge/estimation of the underlying distribution. This method constitutes a generalization of the stochastic decomposition algorithm for two-stage stochastic linear programming models. The approximations used within SDLP may be viewed either through the lens of proximal methods or via regularization. Furthermore, we introduce the notion of basic feasible policies which provide a piecewise affine solution discovery scheme, which is embedded within the optimization algorithm to identify incumbent solutions used in the context of proximal iterations. Finally, we show that the SDLP algorithm provides a sequence of decisions and corresponding value function estimates along a sequence of state trajectories that asymptotically converge to their optimal counterparts, with probability one.

关键词： multistage stochastic programming regularized cutting-plane methods stochastic decomposition sequential sampling

来源：评论

学校读者我要写书评

暂无评论

Bounds in multistage Linear stochastic programming

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2014年第1期163卷 200-229页

作者： Maggioni, Francesca Allevi, Elisabetta Bertocchi, Marida Bergamo Univ Dept Management Econ & Quantitat Methods I-24127 Bergamo Italy Univ Brescia Dept Econ & Management I-25122 Brescia Italy

multistage stochastic programs, which involve sequences of decisions over time, are usually hard to solve in realistically sized problems. Providing bounds for optimal solution may help in evaluating whether it is worth the additional computations for the stochastic program vs. simplified approaches. In this paper we generalize measures from the two-stage case, based on different levels of available information, to the multistage stochastic programming problems. A set of theorems providing chains of inequalities among the new quantities are proved. Numerical results on a case study related to a simple transportation problem illustrate the described relationships.

关键词： multistage stochastic programming Expected value problem Value of stochastic solution Skeleton solution

来源：评论

学校读者我要写书评

暂无评论

Inexact multistage Fuzzy-stochastic programming Model for Water Resources Management

引用

JOURNAL OF WATER RESOURCES PLANNING AND MANAGEMENT 2015年第11期141卷 04015027-04015027页

作者： Chen, Fang Huang, G. H. Fan, Y. R. Univ Regina Fac Engn & Appl Sci Regina SK S4S 0A2 Canada Univ Regina Inst Energy Environm & Sustainabil Res UR NCEPU Regina SK S4S 0A2 Canada North China Elect Power Univ Inst Energy Environm & Sustainabil Res UR NCEPU Beijing 102206 Peoples R China

In this study, an inexact multistage fuzzy-stochastic programming (IMFSP) model was developed for water resources management under uncertainty. In the IMFSP model, the uncertainties existing in the objective functions, and the constraints' left side and right side are expressed as fuzzy sets so that the uncertainties can be directly communicated into the optimization process and various water allocation schemes can be obtained under different a-cut levels at a plurality of periods regardless of the shapes of their membership functions. The IMFSP model can not only generate the most possible, lower and upper bound values for all possible decision schemes but it can also provide information about the degrees of membership of the decision variables between the lower and upper bound values. Meanwhile, the scenario-based multistage stochastic programming was incorporated in the IMFSP model to adequately reflect the dynamic variations and uncertain information of the water resources system. Therefore, the IMFSP model offers significant improvements over existing multistage stochastic programming models for water resources management with respect to the capacity of tackling various uncertainties and their interrelationships. Additionally, a simple hypothetical case for water resources management was provided for demonstrating applicability of the IMFSP model to support decision making within multiple scenarios during many time periods under uncertainty. In general, the proposed IMFSP has only been demonstrated and tested on a hypothetical example. Future research can be directed toward expanding/testing it on more complex real-world problems. (C) 2015 American Society of Civil Engineers.

关键词： multistage stochastic programming Water resources management Decision making Fuzzy sets Uncertainty

来源：评论

学校读者我要写书评

暂无评论

An effective heuristic for multistage linear programming with a stochastic right-hand side

引用

COMPUTERS & OPERATIONS RESEARCH 2014年第Nov.期51卷 237-250页

作者： Beltran-Royo, C. Escudero, L. F. Monge, J. F. Rodriguez-Ravines, R. E. Rey Juan Carlos Univ Stat & Operat Res Dept Madrid Spain Miguel Hernandez Univ Stat Math & Comp Sci Dept Elche Spain Bayes Forecast Madrid Spain

The multistage stochastic Linear programming (SLP) problem may become numerically intractable for huge instances, in which case one can solve an approximation for example the well known multistage Expected Value (EV) problem. We introduce a new approximation to the SLP problem that we call the multistage Event Linear programming (ELP) problem. To obtain this approximation the SLP constraints are aggregated by means of the conditional expectation operator. Based on this new problem we derive the ELP heuristic that produces a lower and an upper bound for the SLP problem. We have assessed the validity of the ELP heuristic by solving large scale instances of the network revenue management problem, where the new approach has clearly outperformed the EV approach. One limitation of this paper is that it only considers randomness on the right-hand side, which is assumed to be discrete and stagewise independent. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： multistage stochastic programming Constraint aggregation Conditional expectation Scenario tree Revenue management

来源：评论

学校读者我要写书评

暂无评论

multistage stochastic inexact chance-constraint programming for an integrated biomass-municipal solid waste power supply management under uncertainty

引用

RENEWABLE & SUSTAINABLE ENERGY REVIEWS 2015年 41卷 1244-1254页

作者： Wu, C. B. Huang, G. H. Li, W. Xie, Y. L. Xu, Y. North China Elect Power Univ SC Resources & Environm Res Acad MOE Key Lab Reg Energy & Environm Syst Optimizat Beijing 102206 Peoples R China Chinese Acad Environm Planning Beijing 100012 Peoples R China

In this study, a multistage stochastic inexact chance-constraint programming (MSICCP) model is developed for power supply management under uncertainties. In the MSICCP model, methods of multistage stochastic programming (MSP), interval-parameter programming (IPP), and chance-constraint programming (CCP) are introduced into a general optimization framework, such that the developed model can tackle uncertainties described in terms of interval values and probability distribution s over a multistage context. Moreover, it can reflect dynamic and randomness of energy resources during the planning horizon. The developed method has been applied to a case of managing the process of power supply in an integrated biomass-municipal solid waste power plant. Useful solutions for the power supply management have been generated. Interval solutions associated with different risk levels of constraint violation have been obtained. The generated solutions can provide desired energy resource allocation with a minimized system cost, maximized system reliability and a maximized energy security. Tradeoffs between system costs and constraint-violation risks can also be tackled. Higher costs will increase system stability, while a desire for lower system costs will run into a risk of potential instability of the management system. They are helpful for supporting (a) adjustment or justification of allocation patterns of energy resources, and (b) analysis of interactions among economic cost, environmental requirement, and power supply security. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： multistage stochastic programming Chance-constraint programming Power supply management Uncertainty

来源：评论

学校读者我要写书评

暂无评论

stochastic dual dynamic programming for multistage stochastic mixed-integer nonlinear optimization

引用

MATHEMATICAL programming 2022年第1-2期196卷 935-985页

作者： Zhang, Shixuan Sun, Xu Andy Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta GA 30332 USA MIT Sloan Sch Management Operat Res Ctr 77 Massachusetts Ave Cambridge MA 02139 USA

In this paper, we study multistage stochastic mixed-integer nonlinear programs (MS-MINLP). This general class of problems encompasses, as important special cases, multistage stochastic convex optimization with non-Lipschitzian value functions and multistage stochastic mixed-integer linear optimization. We develop stochastic dual dynamic programming (SDDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. The key ingredient is a new type of cuts based on generalized conjugacy. Several interesting classes of MS-MINLP are identified, where the new algorithms are guaranteed to obtain the global optimum without the assumption of complete recourse. This significantly generalizes the classic SDDP algorithms. We also characterize the iteration complexity of the proposed algorithms. In particular, for a (T + 1)-stage stochastic MINLP satisfying L-exact Lipschitz regularization with d-dimensional state spaces, to obtain an e-optimal root node solution, we prove that the number of iterations of the proposed deterministic sampling algorithm is upper bounded by O((2LT/epsilon)(d)), and is lower bounded by O((LT/4 epsilon)(d)) for the general case or by O((LT/8 epsilon)(d/2-1)) for the convex case. This shows that the obtained complexity bounds are rather sharp. It also reveals that the iteration complexity depends polynomially on the number of stages. We further show that the iteration complexity depends linearly on T, if all the state spaces are finite sets, or if we seek a (T epsilon)-optimal solution when the state spaces are infinite sets, i.e. allowing the optimality gap to scale with T. To the best of our knowledge, this is the first work that reports global optimization algorithms as well as iteration complexity results for solving such a large class of multistage stochastic programs. The iteration complexity study resolves a conjecture by the late Prof. Shabbir Ahmed in the general setting of multistage stochastic mixed-integer o

关键词： multistage stochastic programming MINLP SDDP Complexity analysis

来源：评论

学校读者我要写书评

暂无评论

multistage stochastic DECOMPOSITION: A BRIDGE BETWEEN stochastic programming AND APPROXIMATE DYNAMIC programming

引用

SIAM JOURNAL ON OPTIMIZATION 2014年第1期24卷 127-153页

作者： Sen, Suvrajeet Zhou, Zhihong Univ So Calif Daniel J Epstein Dept Ind & Syst Engn Los Angeles CA 90089 USA Univ Arizona SIE Dept MORE Inst Tucson AZ 85721 USA

Multistate stochastic programs pose some of the more challenging optimization problems. Because such models can become rather intractable in general, it is important to design algorithms that can provide approximations which, in the long run, yield solutions that are arbitrarily close to an optimum. In this paper, we propose such a sequential sampling method which is applicable to multistage stochastic linear programs, and we refer to it as the multistage stochastic decomposition (MSD) algorithm. This algorithm represents a dynamic extension of a regularized version of stochastic decomposition (SD). While the method allows general correlation structures, specialized streamlined versions are also possible for special cases of stagewise independent and autoregressive processes commonly incorporated in stochastic programming. As with its two-stage counterpart, the MSD algorithm is shown to provide an asymptotically optimal solution, with probability one. As a by-product of this study, we also show that SD algorithms draw upon features of both approximate dynamic programming as well as stochastic programming.

关键词： multistage stochastic programming sequential sampling stochastic decomposition approximate dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Monotonic bounds in multistage mixed-integer stochastic programming

引用

COMPUTATIONAL MANAGEMENT SCIENCE 2016年第3期13卷 423-457页

作者： Maggioni, Francesca Allevi, Elisabetta Bertocchi, Marida Bergamo Univ Dept Management Econ & Quantitat Methods Via Caniana 2 I-24127 Bergamo Italy Brescia Univ Dept Econ & Management Contrada S Chiara 50 I-25122 Brescia Italy

multistage stochastic programs bring computational complexity which may increase exponentially with the size of the scenario tree in real case problems. For this reason approximation techniques which replace the problem by a simpler one and provide lower and upper bounds to the optimal value are very useful. In this paper we provide monotonic lower and upper bounds for the optimal objective value of a multistage stochastic program. These results also apply to stochastic multistage mixed integer linear programs. Chains of inequalities among the new quantities are provided in relation to the optimal objective value, the wait-and-see solution and the expected result of using the expected value solution. The computational complexity of the proposed lower and upper bounds is discussed and an algorithmic procedure to use them is provided. Numerical results on a real case transportation problem are presented.

关键词： multistage stochastic programming Group subproblems Mixed-integer programs Value of stochastic solution Computational complexity Bounds

来源：评论

学校读者我要写书评

暂无评论

Capacity planning of renewable energy systems using stochastic dual dynamic programming

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2025年第2期322卷 573-588页

作者： Hole, J. Philpott, A. B. Dowson, O. Univ Auckland Elect Power Optimizat Ctr Auckland New Zealand Norwegian Univ Sci & Technol Trondheim Norway Norwegian Water Resources & Energy Directorate Oslo Norway

We present a capacity expansion model for deciding the new electricity generation and transmission capacity to complement an existing hydroelectric reservoir system. The objective is to meet a forecast demand at least expected cost, namely the capital cost of the investment plus the expected discounted operating cost of the system. The optimal operating policy for any level of capacity investment can be computed using stochastic dual dynamic programming. We show how to combine a multistage stochastic operational model of the hydro system with a capacity expansion model to create a single model that can be solved by existing open-source solvers for multistage stochastic programs without the need for customized decomposition algorithms. We illustrate our method by applying it to a model of the New Zealand electricity system and comparing the solutions obtained with those found in a previous study.

关键词： OR in energy stochastic dual dynamic programming Capacity expansion multistage stochastic programming Policy graph

来源：评论

学校读者我要写书评

暂无评论

Column generation for multistage stochastic mixed-integer nonlinear programs with discrete state variables

引用

JOURNAL OF GLOBAL OPTIMIZATION 2025年 1-32页

作者： Rathi, Tushar Riley, Benjamin P. Flores-Quiroz, Angela Zhang, Qi Univ Minnesota Dept Chem Engn & Mat Sci Minneapolis MN 55455 USA Univ Chile Dept Elect Engn Santiago Chile Inst Sistemas Complejos Ingn Santiago Chile

stochastic programming provides a natural framework for modeling sequential optimization problems under uncertainty;however, the efficient solution of large-scale multistage stochastic programs remains a challenge, especially in the presence of discrete decisions and nonlinearities. In this work, we consider multistage stochastic mixed-integer nonlinear programs (MINLPs) with discrete state variables, which exhibit a decomposable structure that allows its solution using a column generation approach. Following a Dantzig-Wolfe reformulation, we apply column generation such that each pricing subproblem is an MINLP of much smaller size, making it more amenable to global MINLP solvers. We further propose a method for generating additional columns that satisfy the nonanticipativity constraints, leading to significantly improved convergence and optimal or near-optimal solutions for many large-scale instances in a reasonable computation time. The effectiveness of the tailored column generation algorithm is demonstrated via computational case studies on a multistage blending problem and a problem involving the routing of mobile generators in a power distribution network.

关键词： multistage stochastic programming Mixed-integer nonlinear programs (MINLPs) Column generation Stability in column generation Distributed computing

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：