𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A multistage stochastic programming algorithm suitable for parallel computing

✍ Scribed by Jörgen Blomvall

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
187 KB
Volume
29
Category
Article
ISSN
0167-8191

No coin nor oath required. For personal study only.

✦ Synopsis

In [Euro. J. Operat. Res. 143 (2002) 452; Opt. Meth. Software 17 (2002) 383] a Riccatibased primal interior point method for multistage stochastic programmes was developed. This algorithm has several interesting features. It can solve problems with a nonlinear node-separable convex objective, local linear constraints and global linear constraints. This paper demonstrates that the algorithm can be efficiently parallelized. The solution procedure in the algorithm allows for a simple but efficient method to distribute the computations. The parallel algorithm has been implemented on a low-budget parallel computer, where we experience almost perfect linear speedup and very good scalability of the algorithm.

📜 SIMILAR VOLUMES

Step decision rules for multistage stoch
Step decision rules for multistage stochastic programming: A heuristic approach
✍ J. Thénié; J.-Ph. Vial 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 947 KB

Stochastic programming with step decision rules (SPSDR) aims to produce efficient solutions to multistage stochastic optimization problems. SPSDR, like plain multistage Stochastic Programming (SP), operates on a Monte Carlo "computing sample" of moderate size that approximates the stochastic process

A Parallel Algorithm for Computing Minim
A Parallel Algorithm for Computing Minimum Spanning Trees
✍ D.B. Johnson; P. Metaxas 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 840 KB

We present a simple and implementable algorithm that computes a minimum spanning tree of an undirected weighted graph \(G=(V, E)\) of \(n=|V|\) vertices and \(m=|E|\) edges on an EREW PRAM in \(O\left(\log ^{3 / 2} n\right)\) time using \(n+m\) processors. This represents a substantial improvement i