Invited Session Wed.2.MA 144

Wednesday, 13:15 - 14:45 h, Room: MA 144

Cluster 22: Stochastic optimization [...]

Large-scale stochastic programming


Chair: Mihai Anitescu



Wednesday, 13:15 - 13:40 h, Room: MA 144, Talk 1

Andreas Grothey
Multiple-tree interior point method for stochastic programming


We present an interior point based multi-step solution approach for
stochastic programming problems, given by a sequence of scenario trees
of increasing sizes. These trees can be seen as successively more
accurate discretization of an underlying continuous probability
distribution. Each problems in the sequence is warmstarted from the
previous one. We analyse the resulting algorithm, argue that it yields
improved complexity over either the coldstart or a naive two-step
scheme, and give numerical results.



Wednesday, 13:45 - 14:10 h, Room: MA 144, Talk 2

Miles Lubin
Parallel and distributed solution methods for two-stage stochastic (MI)LPs

Coauthors: Mihai Anitescu, J. A. Julian Hall, Kipp Martin, Cosmin Petra, Burhaneddin Sandikçi


Large-scale linear and mixed-integer two-stage stochastic programming problems with recourse with a finite number of scenarios (typically arising from sample average approximation formulations) have been widely studied; however, many instances remain computationally challenging if not intractable on a modern desktop. For such instances, parallel computing holds great potential due to the decomposable nature of the problems. After reviewing the state of the art, we present our recent work on parallelizing the simplex algorithm for deterministic-equivalent form LP problems, thereby obtaining optimal bases for efficient hot starts for branch and bound or real-time control. We present as well a parallelization of a Lagrangian relaxation approach akin to Caroe and Schultz's dual decomposition algorithm with a novel treatment of combining subproblems to decrease the Lagrangian duality gap. Both approaches look towards solving two-stage mixed-integer problems on a massively parallel scale, and we will compare their effectiveness on a stochastic power grid unit commitment problem as well as problems from the literature.



Wednesday, 14:15 - 14:40 h, Room: MA 144, Talk 3

Werner Römisch
Are quasi-Monte Carlo methods efficient for two-stage stochastic programs?

Coauthors: Holger Heitsch, Hernan Leovey


Quasi-Monte Carlo algorithms are studied for designing discrete
approximations of two-stage linear stochastic programs. Their
integrands are piecewise linear, but neither smooth nor of bounded
variation in the sense of Hardy and Krause. We show that under some
weak geometric condition on the two-stage model all terms of their
ANOVA decomposition, except the one of highest order, are smooth
if the densities are smooth. Hence, Quasi-Monte Carlo algorithms may achieve the optimal rate of convergence O(n-1+δ) for
δ ∈ (0,1/2) and with a constant not depending on the dimension. The geometric condition is generically (i.e., almost everywhere) satisfied if the underlying distribution is normal. We also discuss sensitivity indices, efficient dimensions and suitable transformations to reduce the efficient dimension of two-stage integrands.


  quick loans . This is a permit to the world of pleasure and the lasting sex. Cialis Super Active online is a drug, the quality level of which is determined by its action speed.