University of St.Gallen
research platform alexandria
search publications
browse publications
by person
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
 
by year

Solving Sequences of Refined Multistage Stochastic Linear Programs

abstract Multistage stochastic programs with continuous underlying distributions involve the obstacle of high-dimensional integrals where the integrands' values again are given by solutions of stochastic programs. A common solution technique consists of discretizing the support of the original distributions leading to scenario trees and corresponding LPs which are ? up to a certain size ? easy to solve. In order to improve the accuracy of approximation, successive refinements of the support result in rapidly expanding scenario trees and associated LPs. Hence, the solvability of the multistage stochastic program is limited by the numerical solvability of sequences of such expanding LPs. This work describes an algorithmic technique for solving the large-scale LP of refinement ? based on the solutions at the previous ?-1 refinements. Numerical results are presented for practical problem statements within financial applications demonstrating significant speedup (depending on the size of the LP instances).
   
type journal paper
   
keywords discretization schemes, multistage stochastic linear programs, optimality condition, financial applications, barycentric approximation
   
language English
kind of paper journal article
date of appearance 1-11-2003
journal Annals of Operations Research
publisher Kluwer Academic Publishers (Dordrecht, NL)
ISSN 0254-5330
ISSN (online) 1572-9338
volume of journal 124
number of issue 1
page(s) 133-163
review not reviewed
   
citation Frauendorfer, K., & Haarbrücker, G. (2003). Solving Sequences of Refined Multistage Stochastic Linear Programs. Annals of Operations Research, 124(1), 133-163.