Volume 2014http://edoc.hu-berlin.de/18452/3712022-01-19T13:18:39Z2022-01-19T13:18:39ZQuasi-Monte Carlo methods for linear two-stage stochastic programming problemsLeövey, HernanRömisch, Wernerhttp://edoc.hu-berlin.de/18452/90962020-03-07T04:14:46Z2014-12-30T00:00:00ZQuasi-Monte Carlo methods for linear two-stage stochastic programming problems
Leövey, Hernan; Römisch, Werner
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Quasi-Monte Carlo algorithms are studied for generating scenarios to solve two-stage linear stochastic programming problems. Their integrands are piecewise linear-quadratic, but do not belong to the function spaces consideredfor QMC error analysis. 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 continuously differentiable and second order mixed derivativesexist almost everywhere and belong to $L_2$. This implies that randomly shifted latticerules may achieve the optimal rate of convergence $O(n^{-1+\delta})$ with $\delta \in (0,\frac{1}{2}]$ and a constant not depending on the dimension if the effective superposition dimension is less than or equal to two. The geometric condition is shown to be satisfied for almost all covariance matrices if the underlying probability distribution isnormal. We discuss effective dimensions and techniques for dimension reduction.Numerical experiments for a production planning model with normal inputs showthat indeed convergence rates close to the optimal rate are achieved when usingrandomly shifted lattice rules or scrambled Sobol' point sets accompanied withprincipal component analysis for dimension reduction.
2014-12-30T00:00:00ZDistribution shaping and scenario bundling for stochastic programs with endogenous uncertaintyLaumanns, MarcoPrestwich, StevenKawas, Banhttp://edoc.hu-berlin.de/18452/90952020-03-07T04:14:46Z2014-12-30T00:00:00ZDistribution shaping and scenario bundling for stochastic programs with endogenous uncertainty
Laumanns, Marco; Prestwich, Steven; Kawas, Ban
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Stochastic programs are usually formulated with probability distributions that are exogenously given. Modeling and solving problems withendogenous uncertainty, where decisions can influence the probabilities, has remained a largely unresolved challenge. In this paper we develop a new approach to handle decision-dependent probabilities based on the ideaof distribution shaping. It uses a sequence of distributions, successively conditioned on the influencing decision variables, and characterizes these by linear inequalities. We demonstrate the approach on a pre-disaster planning problem of finding optimal investments to strengthen links ina transportation network, given that the links are subject to stochastic failure. Our new approach solves a recently considered instance of the Istanbul highway network to optimality within seconds, for which only approximate solutions had been known so far.
2014-12-30T00:00:00ZDynamic Generation of Scenario TreesPflug, Georg Ch.Pichler, Aloishttp://edoc.hu-berlin.de/18452/90942020-03-07T04:14:46Z2014-10-16T00:00:00ZDynamic Generation of Scenario Trees
Pflug, Georg Ch.; Pichler, Alois
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We present new algorithms for the dynamic generation of scenario trees for multistagestochastic optimization. The different methods described are based on random vectors, whichare drawn from conditional distributions given the past and on sample trajectories.The structure of the tree is not determined beforehand, but dynamically adapted to meeta distance criterion, which insures the quality of the approximation. The criterion is built ontransportation theory, which is extended to stochastic processes.
2014-10-16T00:00:00ZOn Distributionally Robust Multiperiod Stochastic OptimizationAnalui, BitaPflug, Georg Ch.http://edoc.hu-berlin.de/18452/90932020-03-07T04:14:46Z2014-05-07T00:00:00ZOn Distributionally Robust Multiperiod Stochastic Optimization
Analui, Bita; Pflug, Georg Ch.
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
This paper considers model uncertainty for multistage stochastic programs. The data and information structure of the baseline model is a tree, on which the decision problem is defined. We consider ambiguity neighborhoods around this tree as alternative models which are close to the baseline model. Closeness is defined in terms of a distance for probability trees, called the nested distance. This distance is appropriate for scenario models of multistage stochastic optimization problems as was demonstrated in (Pflug and Pichler, 2012). The ambiguity model is formulated as a minimax problem, where the optimal decision is to be found, which minimizes the maximal objective function, within the ambiguity set. We give a setup for studying saddle point properties of the minimax problem. Moreover, we present solution algorithms for finding the minimax decisions at least asymptotically. As an example, we consider a multiperiod stochastic production/inventory control problem with weekly ordering. The stochastic scenario process is given by the random demands for two products. We find the worst trees within the ambiguity set and determine a solution which is robust w.r.t. model uncertainty. It turns out that the probability weights of the worst case trees are concentrated on few very bad scenarios.
2014-05-07T00:00:00Z