Volume 2014
http://edoc.hu-berlin.de/18452/371
2024-04-22T19:48:53ZQuasi-Monte Carlo methods for linear two-stage stochastic programming problems
http://edoc.hu-berlin.de/18452/9096
Quasi-Monte Carlo methods for linear two-stage stochastic programming problems
Leövey, Hernan; Römisch, Werner
http://dx.doi.org/10.18452/8444
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 uncertainty
http://edoc.hu-berlin.de/18452/9095
Distribution shaping and scenario bundling for stochastic programs with endogenous uncertainty
Laumanns, Marco; Prestwich, Steven; Kawas, Ban
http://dx.doi.org/10.18452/8443
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 Trees
http://edoc.hu-berlin.de/18452/9094
Dynamic Generation of Scenario Trees
Pflug, Georg Ch.; Pichler, Alois
http://dx.doi.org/10.18452/8442
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 Optimization
http://edoc.hu-berlin.de/18452/9093
On Distributionally Robust Multiperiod Stochastic Optimization
Analui, Bita; Pflug, Georg Ch.
http://dx.doi.org/10.18452/8441
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:00ZMitigating Uncertainty via Compromise Decisions in Two-stage Stochastic Linear Programming
http://edoc.hu-berlin.de/18452/9092
Mitigating Uncertainty via Compromise Decisions in Two-stage Stochastic Linear Programming
Sen, Suvrajeet; Liu, Yifan
http://dx.doi.org/10.18452/8440
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Stochastic Programming (SP) has long been considered as a well-justified yet computationally challenging paradigm for practical applications. Computational studies in the literature often involve approximating a large number of scenarios by using a small number of scenarios to be processed via deterministic solvers, or running Sample Average Approximation on some genre of high performance machines so that statistically acceptable bounds can be obtained. In this paper we show that for a class of stochastic linear programming problems, an alternative approach known as Stochastic Decomposition (SD) can provide solutions of similar quality, in far less computational time using ordinary desktop or laptop machines of today. In addition to these compelling computational results, we also provide a stronger convergence result for SD, and introduce a new solution concept which we refer to as the compromise decision. This new concept is attractive for algorithms which call for multiple replications in sampling-based convex optimization algorithms. For such replicated optimization, we show that the difference between an average solution and a compromise decision provides a natural stopping rule. Finally our computational results cover a variety of instances from the literature, including a detailed study of SSN, a network planning instance which is known to be more challenging than other test instances in the literature.
2014-04-16T00:00:00ZMulti-Objective Probabilistically Constrained Programming with Variable Risk: New Models and Applications
http://edoc.hu-berlin.de/18452/9091
Multi-Objective Probabilistically Constrained Programming with Variable Risk: New Models and Applications
Lejeune, Miguel A.; Shen, Siqian
http://dx.doi.org/10.18452/8439
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We consider a class of multi-objective probabilistically constrained problems MOPCP with a joint chance constraint, a multi-row random technology matrix, and a risk parameter (i.e., the reliability level) defined as a decision variable. We propose a Boolean modeling framework and derive a series of new equivalent mixed-integer programming formulations. We demonstrate the computational efficiency of the formulations that contain a small number of binary variables. We provide modeling insights pertaining to the most suitable reformulation, to the trade-off between the conflicting cost/revenue and reliability objectives, and to the scalarization parameter determining the relative importance of the objectives. Finally, we propose several MOPCP variants of multi-portfolio financial optimization models that implement a downside risk measure and can be used in a centralized or decentralized investment context. We study the impact of the model parameters on the portfolios, show, via a cross-validation study, the robustness of the proposed models, and perform a comparative analysis of the optimal investment decisions.
2014-04-04T00:00:00Z