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

SAMPLING-BASED decomposition METHODS FOR MULTISTAGE STOCHASTIC PROGRAMS BASED ON EXTENDED POLYHEDRAL RISK MEASURES

SIAM JOURNAL ON OPTIMIZATION 2012年第2期22卷 286-312页

作者： Guigues, Vincent Roemisch, Werner IMPA Rio De Janeiro Brazil Humboldt Univ Inst Math D-10099 Berlin Germany

We define a risk-averse nonanticipative feasible policy for multistage stochastic programs and propose a methodology to implement it. The approach is based on dynamic programming equations written for a risk-averse formulation of the problem. This formulation relies on a new class of multiperiod risk functionals called extended polyhedral risk measures. Dual representations of such risk functionals are given and used to derive conditions of coherence. In the one-period case, conditions for convexity and consistency with second order stochastic dominance are also provided. The risk-averse dynamic programming equations are specialized considering convex combinations of one-period extended polyhedral risk measures such as spectral risk measures. To implement the proposed policy, the approximation of the risk-averse recourse functions for stochastic linear programs is discussed. In this context, we detail a stochastic dual dynamic programming algorithm which converges to the optimal value of the risk-averse problem.

关键词： convex risk measure coherent risk measure stochastic programming risk-averse optimization decomposition algorithms Monte-Carlo sampling spectral risk measure CVaR

来源：评论

学校读者我要写书评

暂无评论

AN ADVANCED IMPLEMENTATION OF THE DANTZIG-WOLFE decomposition ALGORITHM FOR LINEAR-PROGRAMMING

引用

MATHEMATICAL PROGRAMMING 1981年第3期20卷 303-326页

作者： HO, JK LOUTE, E CATHOLIC UNIV LOUVAIN COREB-1348 LOUVAIN LA NEUVEBELGIUM

Since the original work of Dantzig and Wolfe in 1960, the idea of decomposition has persisted as an attractive approach to large-scale linear programming. However, empirical experience reported in the literature over the years has not been encouraging enough to stimulate practical application. Recent experiments indicate that much improvement is possible through advanced implementations and careful selection of computational strategies. This paper describes such an effort based on state-of-the-art, modular linear programming software (IBM's MPSX/370).

关键词： Large-Scale Systems decomposition algorithms Structured Linear Programs Optimization Software

来源：评论

学校读者我要写书评

暂无评论

Innovative Approaches to Stochastic Dual Dynamic Programming: Two-Period decomposition and Parallelization in a Hydrothermal Scheduling Case Study

引用

JOURNAL OF WATER RESOURCES PLANNING AND MANAGEMENT 2024年第12期150卷 05024014-05024014页

作者： Pedrini, Renata Beltran, Felipe Finardi, Erlon C. Univ Fed Santa Catarina Dept Elect & Elect Engn BR-88040900 Florianopolis SC Brazil Norus 2055 Lauro Linhares StRoom 801Flora Tower BR-88036003 Florianopolis SC Brazil Inst Engn Syst & Comp Res & Dev BR-11055300 Santos Brazil

Stochastic dual dynamic programming (SDDP) is a cutting-edge methodology for addressing the challenges related to the uncertainties in the generation scheduling of hydrodominant power systems. This problem is formulated as a multistage stochastic programming problem spanning a multiyear planning horizon. To efficiently navigate this complexity, SDDP decomposes the multistage linear problem into one-period subproblems, which are iteratively solved via forward and backward steps. Recognizing SDDP's pivotal role, this paper introduces enhancements to boost its computational performance. Firstly, we propose a novel approach, decomposing the scenario tree into two-period subproblems. Although this increases the computational burden of solving larger subproblems, it also increases the quality of resulting future cost functions. Secondly, the paper explores synergy among different decompositions and parallelization techniques. This integrated approach aims to maintain speed in solving smaller one-period subproblems while capitalizing on the improved quality of future cost functions resulting from aggregating periods within the same subproblem. We use Brazilian power system data to show the proposed framework's efficacy in a long-term generation scheduling problem. The results underscore the advantages of the two-period subproblem approach, which yields superior out-of-sample performance compared with the standard SDDP when policies are computed using the same number of iterations. When comparing in-sample confidence intervals, the proposed decomposition approach demonstrates a 26% reduction compared with the conventional one-period SDDP, all within the same execution time. Furthermore, combining decomposition techniques in an asynchronous framework results in a 17% improvement in the confidence interval compared with an asynchronous strategy without this combination. In summary, this paper provides valuable insights into enhancing SDDP's computational efficiency, presentin

关键词： Stochastic dual dynamic programming (SDDP) decomposition algorithms Parallelization Hydrothermal scheduling

来源：评论

学校读者我要写书评

暂无评论

Solving variational inequality problems with linear constraints by a proximal decomposition algorithm

引用

JOURNAL OF GLOBAL OPTIMIZATION 2004年第1期28卷 97-113页

作者： Han, DR Lo, HK Nanjing Normal Univ Sch Math & Comp Sci Nanjing 210097 Peoples R China Hong Kong Univ Sci & Technol Dept Civil Engn Clear Water Bay Hong Kong Peoples R China

The alternating direction method solves large scale variational inequality problems with linear constraints via solving a series of small scale variational inequality problems with simple constraints. The algorithm is attractive if the subproblems can be solved efficiently and exactly. However, the subproblem is itself variational inequality problem, which is structurally also difficult to solve. In this paper, we develop a new decomposition algorithm, which, at each iteration, just solves a system of well-conditioned linear equations and performs a line search. We allow to solve the subproblem approximately and the accuracy criterion is the constructive one developed recently by Solodov and Svaiter. Under mild assumptions on the problem's data, the algorithm is proved to converge globally. Some preliminary computational results are also reported to illustrate the efficiency of the algorithm.

关键词： decomposition algorithms global convergence inexact method monotone mappings variational inequality problems

来源：评论

学校读者我要写书评

暂无评论

Integer Programming, Constraint Programming, and Hybrid decomposition Approaches to Discretizable Distance Geometry Problems

引用

INFORMS JOURNAL ON COMPUTING 2022年第1期34卷 297-314页

作者： MacNeil, Moira Bodur, Merve Univ Toronto Dept Mech & Ind Engn Toronto ON M5S 3G8 Canada

Given an integer dimension K and a simple, undirected graph G with positive edge weights, the Distance Geometry Problem (DGP) aims to find a realization function mapping each vertex to a coordinate in R-K such that the distance between pairs of vertex coordinates is equal to the corresponding edge weights in G. The so-called discretization assumptions reduce the search space of the realization to a finite discrete one, which can be explored via the branch-and-prune (BP) algorithm. Given a discretization vertex order in G, the BP algorithm constructs a binary tree where the nodes at a layer provide all possible coordinates of the vertex corresponding to that layer. The focus of this paper is on finding optimal BP trees for a class of discretizable DGPs. More specifically, we aim to find a discretization vertex order in G that yields a BP tree with the least number of branches. We propose an integer programming formulation and three constraint programming formulations that all significantly outperform the state-of-the-art cutting-plane algorithm for this problem. Moreover, motivated by the difficulty in solving instances with a large and low-density input graph, we develop two hybrid decomposition algorithms, strengthened by a set of valid inequalities, which further improve the solvability of the problem. Summary of Contribution: We present a new model to solve a combinatorial optimization problem on graphs, MIN DOUBLE, which comes from the highly active area of distance geometry and has applications in a wide variety of fields. We use integer programming (IP) and present the first constraint programming(CP) models and hybrid decomposition methods, implemented as a branch-and-cut procedure, for MIN DOUBLE. Through an extensive computational study, we show that our approaches advance the state of the art for MIN DOUBLE. We accomplish this by not only combining generic techniques from IP and CP but also exploring the structure of the problem in developing valid inequal

关键词： distance geometry discretization order integer programming constraint programming decomposition algorithms

来源：评论

学校读者我要写书评

暂无评论

A proximal decomposition algorithm for variational inequality problems

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2003年第1期161卷 231-244页

作者： Han, DR Nanjing Normal Univ Sch Math & Comp Sci Nanjing 210097 Peoples R China

In this paper, we propose a new decomposition algorithm for solving monotone variational inequality problems with linear constraints. The algorithm utilizes the problem's structure conductive to decomposition. At each iteration, the algorithm solves a system of nonlinear equations, which is structurally much easier to solve than variational inequality problems, the subproblems of classical decomposition methods, and then performs a projection step to update the multipliers. We allow to solve the subproblems approximately and we prove that under mild assumptions on the problem's data, the algorithm is globally convergent. We also report some preliminary computational results, which show that the algorithm is encouraging. (C) 2003 Elsevier B.V. All rights reserved.

关键词： variational inequality problems decomposition algorithms global convergence monotone mappings

来源：评论

学校读者我要写书评

暂无评论

Performance analysis of a parallel Dantzig-Wolfe decomposition algorithm for linear programming

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 2002年第10-11期44卷 1431-1437页

作者： Lyu, J Luh, H Lee, MC Natl Cheng Kung Univ Dept Ind Management Sci Tainan Taiwan Natl Chengchi Univ Tainan Taiwan

This paper employs the Dantzig-Wolfe decomposition principle to solve linear programming models in a parallel-computing environment. Adopting the queuing discipline, we showed that under very general conditions, the proposed algorithm speedup trends toward a limiting value as the number of processors increases. (C) 2002 Elsevier Science Ltd. All rights reserved.

关键词： linear programming decomposition algorithms parallel processing

来源：评论

学校读者我要写书评

暂无评论

A unified convergence framework for nonmonotone inexact decomposition methods

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2020年第1期75卷 113-144页

作者： Galli, Leonardo Galligari, Alessandro Sciandrone, Marco Univ Florence Dept Informat Engn Via Santa Marta 3 I-50139 Florence Italy

In this work we propose a general framework that provides a unified convergence analysis for nonmonotone decomposition algorithms. The main motivation to embed nonmonotone strategies within a decomposition approach lies in the fact that enforcing the reduction of the objective function could be unnecessarily expensive, taking into account that groups of variables are individually updated. We define different search directions and line searches satisfying the conditions required by the presented nonmonotone decomposition framework to obtain global convergence. We employ a set of large-scale network equilibrium problems as a computational example to show the advantages of a nonmonotone algorithm over its monotone counterpart. In conclusion, a new smart implementation for decomposition methods has been derived to solve numerical issues on large-scale partially separable functions.

关键词： decomposition algorithms Nonmonotone techniques Global convergence Gauss-Seidel rule Large-scale problems Numerical issues

来源：评论

学校读者我要写书评

暂无评论

Minimal path decomposition of complete bipartite graphs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2018年第3期35卷 684-702页

作者： Constantinou, Costas K. Ellinas, Georgios Univ Cyprus KIOS Res Ctr Kallipoleos 75 CY-1678 Nicosia Cyprus Univ Cyprus Dept Elect & Comp Engn Kallipoleos 75 CY-1678 Nicosia Cyprus

This paper deals with the subject of minimal path decomposition of complete bipartite graphs. A path decomposition of a graph is a decomposition of it into simple paths such that every edge appears in exactly one path. If the number of paths is the minimum possible, the path decomposition is called minimal. algorithms that derive such decompositions are presented, along with their proof of correctness, for the three out of the four possible cases of a complete bipartite graph.

关键词： Graphs Complete bipartite graphs decomposition algorithms Minimal path decomposition

来源：评论

学校读者我要写书评

暂无评论

decomposition Branching for Mixed Integer Programming

引用

OPERATIONS RESEARCH 2022年第3期000卷 1854-1872页

作者： Yildiz, Baris Boland, Natashia Savelsbergh, Martin Koc Univ Dept Ind Engn TR-34450 Istanbul Turkey Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta GA 30332 USA

We introduce a novel and powerful approach for solving certain classes of mixed integer programs (MIPs): decomposition branching. Two seminal and widely used techniques for solving MIPs, branch-and-bound and decomposition, form its foundation. Computational experiments with instances of a weighted set covering problem and a regionalized p-median facility location problem with assignment range constraints demonstrate its efficacy: it explores far fewer nodes and can be orders of magnitude faster than a commercial solver and an automatic Dantzig-Wolfe approach.

关键词： mixed integer programming combinatorial optimization branch-and-bound decomposition algorithms set covering facility location

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：