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

On a mixture of the fix-and-relax coordination and Lagrangian substitution schemes for multistage stochastic mixed integer programming

引用

TOP 2009年第1期17卷 5-29页

作者： Escudero, Laureano F. Univ Rey Juan Carlos Dpto Estadist & Invest Operat Madrid 28933 Spain

We present a framework for solving large-scale multistage mixed 0-1 optimization problems under uncertainty in the coefficients of the objective function, the right-hand side vector, and the constraint matrix. A scenario tree-based scheme is used to represent the Deterministic Equivalent Model of the stochastic mixed 0-1 program with complete recourse. The constraints are modeled by a splitting variable representation via scenarios. So, a mixed 0-1 model for each scenario cluster is considered, plus the nonanticipativity constraints that equate the 0-1 and continuous so-called common variables from the same group of scenarios in each stage. Given the high dimensions of the stochastic instances in the real world, it is not realistic to obtain the optimal solution for the problem. Instead we use the so-called Fix-and-Relax Coordination (FRC) algorithm to exploit the characteristics of the nonanticipativity constraints of the stochastic model. A mixture of the FRC approach and the Lagrangian Substitution and Decomposition schemes is proposed for satisfying, both, the integrality constraints for the 0-1 variables and the nonanticipativity constraints.

关键词： multistage stochastic integer programming Mean-risk measures Branch-and-fix coordination Lagrangian substitution and decomposition

来源：评论

学校读者我要写书评

暂无评论

multistage stochastic Unit Commitment Using stochastic Dual Dynamic integer programming

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2019年第3期34卷 1814-1823页

作者： Zou, Jikai Aluned, Shabbir Sun, Xu Andy Georgia Inst Technol Dept Ind & Syst Engn Atlanta GA 30332 USA

Unit commitment (UC) is a key operational problem in power systems for the optimal schedule of daily generation commitment. Incorporating uncertainty in this already difficult mixedinteger optimization problem introduces significant computational challenges. Most existing stochastic UC models consider either a two-stage decision structure, where the commitment schedule for the entire planning horizon is decided before the uncertainty is realized, or a multistage stochastic programming model with relatively small scenario trees to ensure tractability. We propose a new type of decomposition algorithm, based on the recently proposed framework of stochastic dual dynamic integer programming (SDDiP), to solve the multistage stochastic unit commitment (MSUC) problem. We propose a variety of computational enhancements to SDDiP, and conduct systematic and extensive computational experiments to demonstrate that the proposed method is able to handle elaborate stochastic processes and can solve MSUCs with a huge number of scenarios that are impossible to handle by existing methods.

关键词： Unit commitment multistage stochastic integer programming stochastic dual dynamic integer programming

来源：评论

学校读者我要写书评

暂无评论

stochastic dual dynamic integer programming

引用

MATHEMATICAL programming 2019年第1-2期175卷 461-502页

作者： Zou, Jikai Ahmed, Shabbir Sun, Xu Andy Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta GA 30332 USA

multistage stochastic integer programming (MSIP) combines the difficulty of uncertainty, dynamics, and non-convexity, and constitutes a class of extremely challenging problems. A common formulation for these problems is a dynamic programming formulation involving nested cost-to-go functions. In the linear setting, the cost-to-go functions are convex polyhedral, and decomposition algorithms, such as nested Benders' decomposition and its stochastic variant, stochastic dual dynamic programming (SDDP), which proceed by iteratively approximating these functions by cuts or linear inequalities, have been established as effective approaches. However, it is difficult to directly adapt these algorithms to MSIP due to the nonconvexity of integer programming value functions. In this paper we propose an extension to SDDPcalled stochastic dual dynamic integer programming (SDDiP)for solving MSIP problems with binary state variables. The crucial component of the algorithm is a new reformulation of the subproblems in each stage and a new class of cuts, termed Lagrangian cuts, derived from a Lagrangian relaxation of a specific reformulation of the subproblems in each stage, where local copies of state variables are introduced. We show that the Lagrangian cuts satisfy a tightness condition and provide a rigorous proof of the finite convergence of SDDiP with probability one. We show that, under fairly reasonable assumptions, an MSIP problem with general state variables can be approximated by one with binary state variables to desired precision with only a modest increase in problem size. Thus our proposed SDDiP approach is applicable to very general classes of MSIP problems. Extensive computational experiments on three classes of real-world problems, namely electric generation expansion, financial portfolio management, and network revenue management, show that the proposed methodology is very effective in solving large-scale multistage stochastic integer optimization problems.

关键词： multistage stochastic integer programming Binary state variables Nested decomposition stochastic dual dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Capacity expansion strategies for electric vehicle charging networks: Model, algorithms, and case study

引用

NAVAL RESEARCH LOGISTICS 2022年第3期69卷 442-460页

作者： Chen, Qianqian Huang, Kai Ferguson, Mark R. McMaster Univ Sch Computat Sci & Engn Hamilton ON Canada McMaster Univ DeGroote Sch Business Hamilton ON L8S 4M4 Canada McMaster Univ McMaster Inst Transportat & Logist Hamilton ON Canada

Governments in many jurisdictions are taking measures to promote the use of electric vehicles. As part of this goal, it is crucial to provide a sufficient number of charging stations to alleviate drivers' anxieties associated with the range of the vehicle. The goal of this research is to help governments develop vehicle charging networks for public use via the application of multistage stochastic integer programming model that determines both the locations and capacities of charging facilities over finite planning horizons. The logit choice model is used to estimate drivers' choices of nearby charging stations. Moreover, we characterize the charging demand as a function of the charging station quantity to reflect the range anxiety of consumers. The objective of the model is to minimize the expected total cost of installing and operating the charging facilities. An approximation algorithm, a heuristic algorithm, and a branch-and-price algorithm are designed to solve the model. We conduct numerical experiments to test the efficiency of these algorithms. Importantly, each algorithm has advantages over the CPLEX MIP solver. Finally, the City of Oakville in Ontario, Canada, is used to demonstrate the effectiveness of this model.

关键词： branch-and-price algorithm capacity expansion charging networks electric vehicle facility location logit choice model multistage stochastic integer programming

来源：评论

学校读者我要写书评

暂无评论

Finiteness theorems in stochastic integer programming

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2007年第2期7卷 183-227页

作者： Aschenbrenner, Matthias Hemmecke, Raymond Univ Illinois Dept Math Stat & Comp Sci Chicago IL 60607 USA Univ Magdeburg Inst Math Optimierung Fak Math D-39106 Magdeburg Germany

We study Graver test sets for families of linear multistage stochastic integer programs with a varying number of scenarios. We show that these test sets can be decomposed into finitely many "building blocks," independent of the number of scenarios, and we give an effective procedure to compute them. The paper includes an introduction to Nash-Williams' theory of better-quasi-orderings, which is used to show termination of our algorithm. We also apply this theory to finiteness results for Hilbert functions.

关键词： test sets Graver bases multistage stochastic integer programming decomposition methods well-quasi-orderings

来源：评论

学校读者我要写书评

暂无评论

A multistage risk-averse stochastic programming model for personal savings accrual: the evidence from Lithuania

引用

ANNALS OF OPERATIONS RESEARCH 2019年第1-2期279卷 43-70页

作者： Kabasinskas, Audrius Maggioni, Francesca Sutiene, Kristina Valakevicius, Eimutis Kaunas Univ Technol Dept Math Modeling Studentu 50-141 LT-51368 Kaunas Lithuania Univ Bergamo Dept Management Econ & Quantitat Methods Via Caniana 2 I-24127 Bergamo Italy

In this paper we consider the problem of choosing the optimal pension fund in the second pillar of Lithuanian pension system by providing some guidelines to individuals with defined contribution pension plans. A multistage risk-averse stochastic optimization model is proposed that can be used to plan a long-term pension accrual under two different cases: minimum and maximum accumulation plans as possible options in the system. The investment strategy of personal savings is based on the optimal solutions over possible scenario realizations generated for a particular participant. The concept of the risk-averse decision-maker is implemented by choosing the conditional value at risk as the risk measure defined by a nested formulation that guarantees the time consistency in the multistage model. The paper focuses on three important decision-making moments corresponding to the duration of periods to be modelled. The first period is a short-term accumulation, while the second period is a long-term accumulation with possibly high deviation of objective function value. The third period is designed to implement the concept of target date fund in the second pillar pension scheme as the subsequent need to protect against potential losses at risky pension funds. The experimental findings of this research provide insights for individuals as decision-makers to select pension funds, as well as for policy-makers by revealing the vulnerability of pension system.

关键词： Pension system modeling multistage stochastic integer programming Alpha-stable distribution Time consistency CVaR Target date funds

来源：评论

学校读者我要写书评

暂无评论

A Partial Nested Decomposition Approach for Remanufacturing Planning Under Uncertainty

A Partial Nested Decomposition Approach for Remanufacturing ...

引用

IFIP WG 5.7 International Conference on Advances in Production Management Systems (APMS)

作者： Quezada, Franco Gicquel, Celine Kedad-Sidhoum, Safia Sorbonne Univ LIP6 F-75005 Paris France Univ Santiago de Chile USACH Ind Engn Dept LDSPS Santiago Chile Univ Paris Saclay LRI F-91190 Gif Sur Yvette France CEDRIC CNAM F-75003 Paris France

ISBN: (纸本)9783030859022;9783030859015

We seek to optimize the production planning of a threee-chelon remanufacturing system under uncertain input data. We consider a multi-stage stochastic integer programming approach and use scenario trees to represent the uncertain information structure. We introduce a new dynamic programming formulation that relies on a partial nested decomposition of the scenario tree. We then propose a new extension of the recently published stochastic dual dynamic integer programming algorithm based on this partial decomposition. Our numerical results show that the proposed solution approach is able to provide near-optimal solutions for large-size instances with a reasonable computational effort.

关键词： stochastic lot-sizing with remanufacturing multistage stochastic integer programming stochastic dual dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Mature offshore oil field development: Solving a real options problem using stochastic dual dynamic integer programming

引用

COMPUTERS & OPERATIONS RESEARCH 2021年 136卷 105480-105480页

作者： Bakker, Steffen J. Kleiven, Andreas Fleten, Stein-Erik Tomasgard, Asgeir Norwegian Univ Sci & Technol Dept Ind Econ & Technol Management Alfred Getz Veg 3 NO-7491 Trondheim Norway

Oil and gas companies are facing low output prices and are forced to focus on the development of mature fields. Relevant investment decisions for operators include lifetime-enhancing activities, such as drilling new wells or permanent shutdown. We study the problem of optimal timing of investments in mature oil and gas fields in the presence of price uncertainty, which is an example of a complex real options problem consisting of a portfolio of interdependent options. We formulate a multistage stochastic integer programming model that incorporates a detailed representation of the uncertain oil price, and demonstrate how such a complex real options problem can be efficiently solved using the stochastic Dual Dynamic integer programming algorithm. The paper presents a numerical example based on realistic data and discusses our computational results. We find that only a small number of Markov states are required to represent the uncertain price process, while obtaining convergence of the lower and upper bounds of the objective function. The value of stochastic solution of 11% is considerable in this example. It is concluded that the shutdown decision tends to be postponed as a result of high decommissioning costs, high discount rates, high price uncertainty and low operational expenditures, while it generally is accelerated if the decommissioning costs increase over time.

关键词： SDDiP Real options Mature oil field development multistage stochastic integer programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：