Volume 2012
http://edoc.hu-berlin.de/18452/369
2024-09-07T18:30:18ZConvex hull approximation of TU integer recourse models:Counterexamples, sufficient conditions, and special cases
http://edoc.hu-berlin.de/18452/9082
Convex hull approximation of TU integer recourse models:Counterexamples, sufficient conditions, and special cases
Romeijnders, Ward; Vlerk, Maarten H. van der
Buch
http://dx.doi.org/10.18452/8430
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We consider a convex approximation for integer recourse models. In particular, we showthat the claim of Van der Vlerk (2004) that this approximation yields the convex hull of totallyunimodular (TU) integer recourse models is incorrect. We discuss counterexamples, indicate which step of its proof does not hold in general, and identify a class of random variables for which the claim in Van der Vlerk (2004) is not true. At the same time, we derive additional assumptions under which the claim does hold. In particular, if the random variables in the model are independently and uniformly distributed, then these assumptions are satisfied.
2012-12-21T00:00:00ZRomeijnders, WardVlerk, Maarten H. van derWe consider a convex approximation for integer recourse models. In particular, we showthat the claim of Van der Vlerk (2004) that this approximation yields the convex hull of totallyunimodular (TU) integer recourse models is incorrect. We discuss counterexamples, indicate which step of its proof does not hold in general, and identify a class of random variables for which the claim in Van der Vlerk (2004) is not true. At the same time, we derive additional assumptions under which the claim does hold. In particular, if the random variables in the model are independently and uniformly distributed, then these assumptions are satisfied.Threshold Boolean Form for Joint Probabilistic Constraints with Random Technology Matrix
http://edoc.hu-berlin.de/18452/9081
Threshold Boolean Form for Joint Probabilistic Constraints with Random Technology Matrix
Kogan, Alexander; Lejeune, Miguel A.
Buch
http://dx.doi.org/10.18452/8429
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We develop a new modeling and exact solution method for stochastic programming problems thatinclude a joint probabilistic constraint in which the multi-row random technology matrix is discretely distributed. We binarize the probability distribution of the random variables in such a way that we can extract a threshold partially defined Boolean function (pdBf) representing the probabilistic constraint.We then construct a tight threshold Boolean minorant for the pdBf. Any separating structureof the tight threshold Boolean minorant defines sufficient conditions for the satisfaction of the probabilistic constraint and takes the form of a system of linear constraints. We use the separating structure to derive three new deterministic formulations equivalent to the studied stochastic problem. We derivea set of strengthening valid inequalities for the reformulated problems. A crucial feature ofthe new integer formulations is that the number of integer variables does not depend on the numberof scenarios used to represent uncertainty. The computational study, based on instances of thestochastic capital rationing problem, shows that the MIP reformulations are much easier and ordersof magnitude faster to solve than the MINLP formulation. The method integrating the derived valid inequalities in a branch-and-bound algorithm has the best performance.
2012-11-23T00:00:00ZKogan, AlexanderLejeune, Miguel A.We develop a new modeling and exact solution method for stochastic programming problems thatinclude a joint probabilistic constraint in which the multi-row random technology matrix is discretely distributed. We binarize the probability distribution of the random variables in such a way that we can extract a threshold partially defined Boolean function (pdBf) representing the probabilistic constraint.We then construct a tight threshold Boolean minorant for the pdBf. Any separating structureof the tight threshold Boolean minorant defines sufficient conditions for the satisfaction of the probabilistic constraint and takes the form of a system of linear constraints. We use the separating structure to derive three new deterministic formulations equivalent to the studied stochastic problem. We derivea set of strengthening valid inequalities for the reformulated problems. A crucial feature ofthe new integer formulations is that the number of integer variables does not depend on the numberof scenarios used to represent uncertainty. The computational study, based on instances of thestochastic capital rationing problem, shows that the MIP reformulations are much easier and ordersof magnitude faster to solve than the MINLP formulation. The method integrating the derived valid inequalities in a branch-and-bound algorithm has the best performance.Optimizing existing railway timetables by means of stochastic programming
http://edoc.hu-berlin.de/18452/9080
Optimizing existing railway timetables by means of stochastic programming
Vekas, Peter; Vlerk, Maarten H. van der; Haneveld, Willem K. Klein
Buch
http://dx.doi.org/10.18452/8428
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We present some models to find the best allocation of a limited amount of so-called runningtime supplements (extra minutes added to a timetable to reduce delays) on a railway line. Bythe best allocation, we mean the solution under which the sum of expected delays is minimal.Instead of trying to invent a completely new timetable, our aim is to finely adjust an alreadyexisting and well-functioning one. We model this inherently stochastic optimization problemby using two-stage recourse models from stochastic programming, following Vromans [9]. Wepresent an improved formulation, allowing for an efficient solution using a standard algorithmfor recourse models. We include a case study that we managed to solve about 180 times fasterthan it was solved in [9]. By comparing our solution with other, seemingly intuitive solutions,we show that finding the best allocation is not obvious, and implementing it in practicepromises a significant improvement in the punctuality of trains. A technique to estimate themodel parameters from empirical data and an approximating deterministic problem are alsopresented, along with some practical ideas that are meant to enhance the applicability of ourmodels.
2012-10-31T00:00:00ZVekas, PeterVlerk, Maarten H. van derHaneveld, Willem K. KleinWe present some models to find the best allocation of a limited amount of so-called runningtime supplements (extra minutes added to a timetable to reduce delays) on a railway line. Bythe best allocation, we mean the solution under which the sum of expected delays is minimal.Instead of trying to invent a completely new timetable, our aim is to finely adjust an alreadyexisting and well-functioning one. We model this inherently stochastic optimization problemby using two-stage recourse models from stochastic programming, following Vromans [9]. Wepresent an improved formulation, allowing for an efficient solution using a standard algorithmfor recourse models. We include a case study that we managed to solve about 180 times fasterthan it was solved in [9]. By comparing our solution with other, seemingly intuitive solutions,we show that finding the best allocation is not obvious, and implementing it in practicepromises a significant improvement in the punctuality of trains. A technique to estimate themodel parameters from empirical data and an approximating deterministic problem are alsopresented, along with some practical ideas that are meant to enhance the applicability of ourmodels.Introduction to convex optimization in financial markets
http://edoc.hu-berlin.de/18452/9079
Introduction to convex optimization in financial markets
Pennanen, Teemu
Buch
http://dx.doi.org/10.18452/8427
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Convexity arises quite naturally in financial risk management. In riskpreferences concerning random cash-flows, convexity corresponds to thefundamental diversification principle. Convexity is a basic property alsoof budget constraints both in classical linear models as well as in morerealistic models with transaction costs and constraints. Moreover, modern securities markets are based on trading protocols that result in convextrading costs. The first part of this paper gives an introduction to certain basic concepts and principles of financial risk management in simpleoptimization terms. The second part reviews some convex optimizationtechniques used in mathematical and numerical analysis of financial optimization problems.
2012-06-08T00:00:00ZPennanen, TeemuConvexity arises quite naturally in financial risk management. In riskpreferences concerning random cash-flows, convexity corresponds to thefundamental diversification principle. Convexity is a basic property alsoof budget constraints both in classical linear models as well as in morerealistic models with transaction costs and constraints. Moreover, modern securities markets are based on trading protocols that result in convextrading costs. The first part of this paper gives an introduction to certain basic concepts and principles of financial risk management in simpleoptimization terms. The second part reviews some convex optimizationtechniques used in mathematical and numerical analysis of financial optimization problems.Quantitative Stability Analysis of Stochastic Generalized Equations
http://edoc.hu-berlin.de/18452/9078
Quantitative Stability Analysis of Stochastic Generalized Equations
Liu, Yongchao; Römisch, Werner; Xu, Huifu
Buch
http://dx.doi.org/10.18452/8426
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We consider the solution of a system of stochastic generalized equations (SGE) where theunderlying functions are mathematical expectation of random set-valued mappings. SGE hasmany applications such as characterizing optimality conditions of a nonsmooth stochastic optimization problem and a stochastic equilibrium problem. We derive quantitative continuityof expected value of the set-valued mapping with respect to the variation of the underlyingprobability measure in a metric space. This leads to the subsequent qualitative and quantitative stability analysis of solution set mappings of the SGE. Under some metric regularityconditions, we derive Aubin’s property of the solution set mapping with respect to the changeof probability measure. The established results are applied to stability analysis of stationary points of classical one stage and two stage stochastic minimization problems, two stagestochastic mathematical programs with equilibrium constraints and stochastic programs withsecond order dominance constraints.
2012-10-13T00:00:00ZLiu, YongchaoRömisch, WernerXu, HuifuWe consider the solution of a system of stochastic generalized equations (SGE) where theunderlying functions are mathematical expectation of random set-valued mappings. SGE hasmany applications such as characterizing optimality conditions of a nonsmooth stochastic optimization problem and a stochastic equilibrium problem. We derive quantitative continuityof expected value of the set-valued mapping with respect to the variation of the underlyingprobability measure in a metric space. This leads to the subsequent qualitative and quantitative stability analysis of solution set mappings of the SGE. Under some metric regularityconditions, we derive Aubin’s property of the solution set mapping with respect to the changeof probability measure. The established results are applied to stability analysis of stationary points of classical one stage and two stage stochastic minimization problems, two stagestochastic mathematical programs with equilibrium constraints and stochastic programs withsecond order dominance constraints.Are Quasi-Monte Carlo algorithms efficient for two-stage stochastic programs?
http://edoc.hu-berlin.de/18452/9077
Are Quasi-Monte Carlo algorithms efficient for two-stage stochastic programs?
Heitsch, Holger; Leövey, Hernan; Römisch, Werner
Buch
http://dx.doi.org/10.18452/8425
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Quasi-Monte Carlo algorithms are studied for designing discrete approximationsof two-stage linear stochastic programs. Their integrands are piecewiselinear, but neither smooth nor lie in the function spaces considered for QMC erroranalysis. We show that under some weak geometric condition on the two-stagemodel all terms of their ANOVA decomposition, except the one of highest order,are smooth. Hence, Quasi-Monte Carlo algorithms may achieve the optimal rateof convergence $O(n^{-1+\delta}$ with $\delta \in (0,\frac{1}{2}]$ and a constant not depending on the dimension. The geometric condition is shown to be generically satisfied if the underlyingdistribution is normal. We discuss sensitivity indices, effective dimensionsand dimension reduction techniques for two-stage integrands. Numerical experimentsshow that indeed convergence rates close to the optimal rate are achievedwhen using randomly scrambled Sobol' point sets and randomly shifted latticerules accompanied with suitable dimension reduction techniques.
2012-09-24T00:00:00ZHeitsch, HolgerLeövey, HernanRömisch, WernerQuasi-Monte Carlo algorithms are studied for designing discrete approximationsof two-stage linear stochastic programs. Their integrands are piecewiselinear, but neither smooth nor lie in the function spaces considered for QMC erroranalysis. We show that under some weak geometric condition on the two-stagemodel all terms of their ANOVA decomposition, except the one of highest order,are smooth. Hence, Quasi-Monte Carlo algorithms may achieve the optimal rateof convergence $O(n^{-1+\delta}$ with $\delta \in (0,\frac{1}{2}]$ and a constant not depending on the dimension. The geometric condition is shown to be generically satisfied if the underlyingdistribution is normal. We discuss sensitivity indices, effective dimensionsand dimension reduction techniques for two-stage integrands. Numerical experimentsshow that indeed convergence rates close to the optimal rate are achievedwhen using randomly scrambled Sobol' point sets and randomly shifted latticerules accompanied with suitable dimension reduction techniques.SDDP for multistage stochastic linear programs based on spectral risk measures
http://edoc.hu-berlin.de/18452/9076
SDDP for multistage stochastic linear programs based on spectral risk measures
Guiges, Vincent; Römisch, Werner
Buch
http://dx.doi.org/10.18452/8424
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We consider risk-averse formulations of multistage stochastic linear programs. Forthese formulations, based on convex combinations of spectral risk measures, risk-averse dynamicprogramming equations can be written. As a result, the Stochastic Dual Dynamic Programming(SDDP) algorithm can be used to obtain approximations of the corresponding risk-averse recoursefunctions. This allows us to deﬁne a risk-averse nonanticipative feasible policy for the stochasticlinear program. Formulas for the cuts that approximate the recourse functions are given.
2012-04-09T00:00:00ZGuiges, VincentRömisch, WernerWe consider risk-averse formulations of multistage stochastic linear programs. Forthese formulations, based on convex combinations of spectral risk measures, risk-averse dynamicprogramming equations can be written. As a result, the Stochastic Dual Dynamic Programming(SDDP) algorithm can be used to obtain approximations of the corresponding risk-averse recoursefunctions. This allows us to deﬁne a risk-averse nonanticipative feasible policy for the stochasticlinear program. Formulas for the cuts that approximate the recourse functions are given.Multistage Stochastic Decomposition: A Bridge between Stochastic Programming and Approximate Dynamic Programming
http://edoc.hu-berlin.de/18452/9075
Multistage Stochastic Decomposition: A Bridge between Stochastic Programming and Approximate Dynamic Programming
Sen, Suvrajeet; Zhou, Zhihong
Buch
http://dx.doi.org/10.18452/8423
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Multi-stage stochastic programs (MSP) pose some of the more challenging optimizationproblems. Because such models can become rather intractable in general, it is important todesign algorithms that can provide approximations which, in the long run, yield solutions that arearbitrarily close to an optimum. In this paper, we propose a statistically motivated sequentialsampling method that is applicable to multi-stage stochastic linear programs, and we refer to it asthe multistage stochastic decomposition (MSD) algorithm. As with earlier SD methods for two-stage stochastic linear programs, this approach preserves one of the most attractive features ofSD: asymptotic convergence of the solutions can be proven (with probability one) without anyiteration requiring more than a small sample-size. This data-driven approach also allows us tosequentially update value function approximations, and the computations themselves can beorganized in a manner that decomposes the scenario generation (stochastic) process from theoptimization computations. As a by-product of this study, we also show that SD algorithms areessentially approximate dynamic programming algorithms for SP. Our asymptotic analysis alsoreveals conceptual connections between multiple SP algorithms.
2012-03-19T00:00:00ZSen, SuvrajeetZhou, ZhihongMulti-stage stochastic programs (MSP) pose some of the more challenging optimizationproblems. Because such models can become rather intractable in general, it is important todesign algorithms that can provide approximations which, in the long run, yield solutions that arearbitrarily close to an optimum. In this paper, we propose a statistically motivated sequentialsampling method that is applicable to multi-stage stochastic linear programs, and we refer to it asthe multistage stochastic decomposition (MSD) algorithm. As with earlier SD methods for two-stage stochastic linear programs, this approach preserves one of the most attractive features ofSD: asymptotic convergence of the solutions can be proven (with probability one) without anyiteration requiring more than a small sample-size. This data-driven approach also allows us tosequentially update value function approximations, and the computations themselves can beorganized in a manner that decomposes the scenario generation (stochastic) process from theoptimization computations. As a by-product of this study, we also show that SD algorithms areessentially approximate dynamic programming algorithms for SP. Our asymptotic analysis alsoreveals conceptual connections between multiple SP algorithms.Measures of information in multi-stage stochastic programming(Bounds in Multistage Linear Stochastic Programming)
http://edoc.hu-berlin.de/18452/9074
Measures of information in multi-stage stochastic programming(Bounds in Multistage Linear Stochastic Programming)
Maggioni, Francesca; Allevi, Elisabetta; Bertocchi, Marida
Buch
http://dx.doi.org/10.18452/8422
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Multistage stochastic programs, which involve sequences of decisions over time, areusually hard to solve in realistically sized problems. In the two-stage case, several approaches basedon different levels of available information has been adopted in literature such as the Expected ValueProblem, EV , the Sum of Pairs Expected Values, SP EV , the Expectation of Pairs Expected Value,EP EV, solving series of sub-problems more computationally tractable than the initial one, or the Expected Skeleton Solution Value, ESSV and the Expected Input Value, EIV which evaluate thequality of the deterministic solution in term of its structure and upgradeability.In this paper we generalize the deﬁnition of the above quantities to the multistage stochastic for-mulation when the right hand side of constraints are stochastic: we introduce the Multistage ExpectedValue of the Reference Scenario, M EV RS, the Multistage Sum of Pairs Expected Values, M SP EVand the Multistage Expectation of Pairs Expected Value, M EP EV by means of the new concept ofauxiliary scenario and redeﬁnition of pairs subproblems probability. We show that theorems provedin [2] and [3] for two stage case are valid also in the multi-stage case. Measures of quality of theaverage solution such as the Multistage Loss Using Skeleton Solution, M LU SSt and the MultistageLoss of Upgrading the Deterministic Solution, M LU DSt are introduced and related to the standard Value of Stochastic Solution, V SSt at stage t.A set of theorems providing chains of inequalities among the new quantities are proved. Thesebounds may help in evaluating whether it is worth the additional computations for the stochasticprogram versus the simpliﬁed approaches proposed. Numerical results on a case study related to asimple transportation problem are shown.
2012-03-19T00:00:00ZMaggioni, FrancescaAllevi, ElisabettaBertocchi, MaridaMultistage stochastic programs, which involve sequences of decisions over time, areusually hard to solve in realistically sized problems. In the two-stage case, several approaches basedon different levels of available information has been adopted in literature such as the Expected ValueProblem, EV , the Sum of Pairs Expected Values, SP EV , the Expectation of Pairs Expected Value,EP EV, solving series of sub-problems more computationally tractable than the initial one, or the Expected Skeleton Solution Value, ESSV and the Expected Input Value, EIV which evaluate thequality of the deterministic solution in term of its structure and upgradeability.In this paper we generalize the deﬁnition of the above quantities to the multistage stochastic for-mulation when the right hand side of constraints are stochastic: we introduce the Multistage ExpectedValue of the Reference Scenario, M EV RS, the Multistage Sum of Pairs Expected Values, M SP EVand the Multistage Expectation of Pairs Expected Value, M EP EV by means of the new concept ofauxiliary scenario and redeﬁnition of pairs subproblems probability. We show that theorems provedin [2] and [3] for two stage case are valid also in the multi-stage case. Measures of quality of theaverage solution such as the Multistage Loss Using Skeleton Solution, M LU SSt and the MultistageLoss of Upgrading the Deterministic Solution, M LU DSt are introduced and related to the standard Value of Stochastic Solution, V SSt at stage t.A set of theorems providing chains of inequalities among the new quantities are proved. Thesebounds may help in evaluating whether it is worth the additional computations for the stochasticprogram versus the simpliﬁed approaches proposed. Numerical results on a case study related to asimple transportation problem are shown.Gradient estimates for Gaussian distribution functions: Application to probabilistically constrained optimization problems
http://edoc.hu-berlin.de/18452/9073
Gradient estimates for Gaussian distribution functions: Application to probabilistically constrained optimization problems
Henrion, René
Buch
http://dx.doi.org/10.18452/8421
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We provide lower estimates for the norm of gradients of Gaussian distribution functions and apply the results obtained to a special class ofprobabilistically constrained optimization problems. In particular, it is shown how the precision of computing gradients in such problems can be controlled by the precision of function values for Gaussian distribution functions. Moreover, a sensitivity result for optimal values with respect to perturbations of theunderlying random vector is derived. It is shown that the so-called maximal increasing slope of the optimal value with respect to the Kolmogorov distance between original and perturbed distribution can be estimated explicitly fromthe input data of the problem.
2012-02-20T00:00:00ZHenrion, RenéWe provide lower estimates for the norm of gradients of Gaussian distribution functions and apply the results obtained to a special class ofprobabilistically constrained optimization problems. In particular, it is shown how the precision of computing gradients in such problems can be controlled by the precision of function values for Gaussian distribution functions. Moreover, a sensitivity result for optimal values with respect to perturbations of theunderlying random vector is derived. It is shown that the so-called maximal increasing slope of the optimal value with respect to the Kolmogorov distance between original and perturbed distribution can be estimated explicitly fromthe input data of the problem.