Volume 2009
http://edoc.hu-berlin.de/18452/366
Fri, 13 Sep 2024 09:09:21 GMT2024-09-13T09:09:21ZUncertainties in minimax stochastic programs
http://edoc.hu-berlin.de/18452/9059
Uncertainties in minimax stochastic programs
Dupacová, J.
Buch
http://dx.doi.org/10.18452/8407
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
When using the minimax approach one tries to hedge against the worst possible distribution belonging to a speciﬁed class P. A suitable stability analysis of results with respect to the choice of this class is an important issue. It has to be tailored to the type of the minimax problem, to the considered class of probability distributions and to the anticipated input perturbations. We shall focus on the effect of changes in input information for classes of probability distributions with support belonging to a given set and deﬁned by (possibly perturbed) generalized moments values.
Fri, 16 Oct 2009 00:00:00 GMThttp://edoc.hu-berlin.de/18452/90592009-10-16T00:00:00ZDupacová, J.When using the minimax approach one tries to hedge against the worst possible distribution belonging to a speciﬁed class P. A suitable stability analysis of results with respect to the choice of this class is an important issue. It has to be tailored to the type of the minimax problem, to the considered class of probability distributions and to the anticipated input perturbations. We shall focus on the effect of changes in input information for classes of probability distributions with support belonging to a given set and deﬁned by (possibly perturbed) generalized moments values.Day-Ahead Market Bidding for a NordicHydropower Producer: Taking the ElbasMarket into Account
http://edoc.hu-berlin.de/18452/9058
Day-Ahead Market Bidding for a NordicHydropower Producer: Taking the ElbasMarket into Account
Faria, E.; Fleten, St..-E.
Buch
http://dx.doi.org/10.18452/8406
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
In many power markets around the world the energy generation decisions result from two-sidedauctions in which producing and consuming agents submit their price-quantity bids. Thedetermination of optimal bids in power markets is a complicated task that has to be undertakenevery day. In the present work, we propose an optimization model for a price-taker hydropowerproducer in Nord Pool that takes into account the uncertainty in market prices and both productionand physical trading aspects. The day-ahead bidding takes place a day before the actual operation and energy delivery. After this round of bidding, but before actual operation, some adjustments in the dispatched power (accepted bids) have to be done, due to uncertainty in prices, inflow and load. Such adjustments can be done in the Elbas market, which allows for trading physical electricity up to one hour before the operation hour. This paper uses stochastic programming to determine the optimal bidding strategy and the impact of the possibility to participate in the Elbas.ARMAX and GARCH techniques are used to generate realistic market price scenarios taking intoaccount both day-ahead price and Elbas price uncertainty. The results show that considering Elbas when bidding in the day-ahead market does not significantly impact neither the profit nor the recommended bids of a typical hydro producer.
Fri, 16 Oct 2009 00:00:00 GMThttp://edoc.hu-berlin.de/18452/90582009-10-16T00:00:00ZFaria, E.Fleten, St..-E.In many power markets around the world the energy generation decisions result from two-sidedauctions in which producing and consuming agents submit their price-quantity bids. Thedetermination of optimal bids in power markets is a complicated task that has to be undertakenevery day. In the present work, we propose an optimization model for a price-taker hydropowerproducer in Nord Pool that takes into account the uncertainty in market prices and both productionand physical trading aspects. The day-ahead bidding takes place a day before the actual operation and energy delivery. After this round of bidding, but before actual operation, some adjustments in the dispatched power (accepted bids) have to be done, due to uncertainty in prices, inflow and load. Such adjustments can be done in the Elbas market, which allows for trading physical electricity up to one hour before the operation hour. This paper uses stochastic programming to determine the optimal bidding strategy and the impact of the possibility to participate in the Elbas.ARMAX and GARCH techniques are used to generate realistic market price scenarios taking intoaccount both day-ahead price and Elbas price uncertainty. The results show that considering Elbas when bidding in the day-ahead market does not significantly impact neither the profit nor the recommended bids of a typical hydro producer.Risk-Averse Two-Stage Stochastic LinearProgramming: Modeling and Decomposition
http://edoc.hu-berlin.de/18452/9057
Risk-Averse Two-Stage Stochastic LinearProgramming: Modeling and Decomposition
Miller, N.; Ruszczynski, A.
Buch
http://dx.doi.org/10.18452/8405
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We formulate a risk-averse two-stage stochastic linear programming problem in which unresolved uncertainty remains after the second stage. The objective function is formulated as a composition of conditional risk measures.We analyze properties of the problem and derive necessary and sufﬁcientoptimality conditions. Next, we construct two decomposition methods forsolving the problem. The ﬁrst method is based on the generic cutting planeapproach, while the second method exploits the composite structure of the objective function. We illustrate their performance on a portfolio optimization problem.
Fri, 16 Oct 2009 00:00:00 GMThttp://edoc.hu-berlin.de/18452/90572009-10-16T00:00:00ZMiller, N.Ruszczynski, A.We formulate a risk-averse two-stage stochastic linear programming problem in which unresolved uncertainty remains after the second stage. The objective function is formulated as a composition of conditional risk measures.We analyze properties of the problem and derive necessary and sufﬁcientoptimality conditions. Next, we construct two decomposition methods forsolving the problem. The ﬁrst method is based on the generic cutting planeapproach, while the second method exploits the composite structure of the objective function. We illustrate their performance on a portfolio optimization problem.On probabilistic constraints induced by rectangular sets and multivariate normal distributions
http://edoc.hu-berlin.de/18452/9056
On probabilistic constraints induced by rectangular sets and multivariate normal distributions
Ackooij, W. Van; Henrion, R.; Möller, A.; Zorgati, R.
Buch
http://dx.doi.org/10.18452/8404
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
In this paper, we consider optimization problems under probabilistic constraints which aredeﬁned by two-sided inequalities for the underlying normally distributed random vector. Asa main step for an algorithmic solution of such problems, we derive a derivative formula for(normal) probabilities of rectangles as functions of their lower or upper bounds. This formulaallows to reduce the calculus of such derivatives to the calculus of (normal) probabilitiesof rectangles themselves thus generalizing a similar well-known statement for multivariatenormal distribution functions. As an application, we consider a problem from water reservoirmanagement. One of the outcomes of the problem solution is that the (still frequentlyencountered) use of simple individual probabilistic can completely fail. In contrast, the (more diﬃcult) use of joint probabilistic constraints which heavily depends on the derivative formula mentioned before yields very reasonable and robust solutions over the whole time horizon considered.
Fri, 16 Oct 2009 00:00:00 GMThttp://edoc.hu-berlin.de/18452/90562009-10-16T00:00:00ZAckooij, W. VanHenrion, R.Möller, A.Zorgati, R.In this paper, we consider optimization problems under probabilistic constraints which aredeﬁned by two-sided inequalities for the underlying normally distributed random vector. Asa main step for an algorithmic solution of such problems, we derive a derivative formula for(normal) probabilities of rectangles as functions of their lower or upper bounds. This formulaallows to reduce the calculus of such derivatives to the calculus of (normal) probabilitiesof rectangles themselves thus generalizing a similar well-known statement for multivariatenormal distribution functions. As an application, we consider a problem from water reservoirmanagement. One of the outcomes of the problem solution is that the (still frequentlyencountered) use of simple individual probabilistic can completely fail. In contrast, the (more diﬃcult) use of joint probabilistic constraints which heavily depends on the derivative formula mentioned before yields very reasonable and robust solutions over the whole time horizon considered.The role of information in multi-period risk measurement
http://edoc.hu-berlin.de/18452/9055
The role of information in multi-period risk measurement
Pflug, G. Ch.; Römisch, Werner
Buch
http://dx.doi.org/10.18452/8403
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Multi-period risk functionals assign a risk value to a discrete-time stochasticprocess $Y = (Y_1 , . . . , Y_T )$. While convexity and monotonicity properties extend ina natural way from the single-period case and several types of translation properties may be deﬁned, the role of information becomes crucial in the multi-period situation. In this paper, we deﬁne multi-period functionals in a generic way, such that the available information (expressed as a ﬁltration) enters explicitly the deﬁnition of the functional. This allows to study the information monotonicity property,which comes as the counterpart of value monotonicity. We discuss several ways ofconstructing concrete and computable functionals out of conditional risk mappingsand single-period risk functionals. Some of them appear as value functions of multistage stochastic programs, where the ﬁltration appears in the non-anticipativity constraint. This approach leads in a natural way to information monotonicity. Thesubclass of polyhedral multi-period risk functionals becomes important for theiremployment in practical dynamic decision making and risk management. On the other hand, several functionals described in literature are not information-monotone, which limits their practical use.
Fri, 24 Jul 2009 00:00:00 GMThttp://edoc.hu-berlin.de/18452/90552009-07-24T00:00:00ZPflug, G. Ch.Römisch, WernerMulti-period risk functionals assign a risk value to a discrete-time stochasticprocess $Y = (Y_1 , . . . , Y_T )$. While convexity and monotonicity properties extend ina natural way from the single-period case and several types of translation properties may be deﬁned, the role of information becomes crucial in the multi-period situation. In this paper, we deﬁne multi-period functionals in a generic way, such that the available information (expressed as a ﬁltration) enters explicitly the deﬁnition of the functional. This allows to study the information monotonicity property,which comes as the counterpart of value monotonicity. We discuss several ways ofconstructing concrete and computable functionals out of conditional risk mappingsand single-period risk functionals. Some of them appear as value functions of multistage stochastic programs, where the ﬁltration appears in the non-anticipativity constraint. This approach leads in a natural way to information monotonicity. Thesubclass of polyhedral multi-period risk functionals becomes important for theiremployment in practical dynamic decision making and risk management. On the other hand, several functionals described in literature are not information-monotone, which limits their practical use.Fenchel Decomposition for Stochastic Mixed-IntegerProgramming
http://edoc.hu-berlin.de/18452/9054
Fenchel Decomposition for Stochastic Mixed-IntegerProgramming
Ntaimo, L.
Buch
http://dx.doi.org/10.18452/8402
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
This paper introduces a new cutting plane method for two-stage stochastic mixed-integer programming (SMIP) called Fenchel decomposition (FD). FD usesa class of valid inequalities termed, FD cuts, which are derived based on Fenchel cutting planes from integer programming. We derive FD cuts based on both the ﬁrst and second stage variables, and devise an FD algorithm for SMIP with binary ﬁrst stage and establish ﬁnite convergence for mixed-binary second stage. We also derive alternative FD cuts based on the second stage variables only and use an idea from disjunctive programming to lift the cuts to the higher dimension space including the ﬁrst stage variables. We then devise an FD-L algorithm based on the lifted FD cuts. Finally, we report on preliminary computational results based on example instances from the literature. The results are promising and show the lifted FD cuts to have better performance than the regular FD cuts. Furthermore, both the FD and FD-L algorithms outperform a standard solver on large-scaleinstances.
Fri, 22 May 2009 00:00:00 GMThttp://edoc.hu-berlin.de/18452/90542009-05-22T00:00:00ZNtaimo, L.This paper introduces a new cutting plane method for two-stage stochastic mixed-integer programming (SMIP) called Fenchel decomposition (FD). FD usesa class of valid inequalities termed, FD cuts, which are derived based on Fenchel cutting planes from integer programming. We derive FD cuts based on both the ﬁrst and second stage variables, and devise an FD algorithm for SMIP with binary ﬁrst stage and establish ﬁnite convergence for mixed-binary second stage. We also derive alternative FD cuts based on the second stage variables only and use an idea from disjunctive programming to lift the cuts to the higher dimension space including the ﬁrst stage variables. We then devise an FD-L algorithm based on the lifted FD cuts. Finally, we report on preliminary computational results based on example instances from the literature. The results are promising and show the lifted FD cuts to have better performance than the regular FD cuts. Furthermore, both the FD and FD-L algorithms outperform a standard solver on large-scaleinstances.A computational study of a solver system for processing two-stage stochastic linear programming problems
http://edoc.hu-berlin.de/18452/9053
A computational study of a solver system for processing two-stage stochastic linear programming problems
Zverovich, V.; Fábièn, C.; Ellison, F.; Mitra, G.
Buch
http://dx.doi.org/10.18452/8401
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Formulation of stochastic optimisation problems and computational algorithms for their solution continue to make steady progress as can be seenfrom an analysis of many developments in this ﬁeld. The edited volume by Wallace and Ziemba (2005) outlines both the SP modelling systems andmany applications in diverse domains.More recently, Fabozzi (2008) has considered the application of SP models to challenging ﬁnancial engineering problems. The tightly knit yet highlyfocused group of researchers COSP: Committee on Stochastic Programming, their triennial international SP conference, and their active website points to the progressive acceptance of SP as a valuable decision tool. At the same time many of the major software vendors, namely, XPRESS, AIMMS, and MAXIMAL GAMS have started offering SP extensions to their optimisation suites.Our analysis of the modelling and algorithmic solver requirements reveals that (a) modelling support (b) scenario generation and (c) solutionmethods are three important aspects of a working SP system. Our research is focussed on all three aspects and we refer the readers to Valente et al.(2009) for modelling and Mitra et al. (2007) and Di Domenica et al. (2009) for scenario generation. In this paper we are concerned entirely with com-putational solution methods. Given the tremendous advance in LP solver algorithms there is certain amount of complacency that by constructing a”deterministic equivalent” problems it is possible to process most realistic instances of SP problems. In this paper we highlight the shortcoming of this line of argument. We describe the implementation and reﬁnement of established algorithmic methods and report a computational study which clearly underpins the superior scale up properties of the solution methods which aredescribed in this paper.A taxonomy of the important class of SP problems may be found in Valente et al. (2008, 2009). The most important class of problems with manyapplications is the two-stage stochastic programming model with recourse, which originated from the early research of Dantzig (1955), Beale (1955) and Wets (1974).A comprehensive treatment of the model and solution methods can be found in Kall and Wallace (1994), Prekopa (1995), Birge and Louveaux (1997), Mayer (1998), Ruszczynski and Shapiro (2003), and Kall and Mayer (2005). Some of these monographs contain generalisations of the originalmodel. Colombo et al. (2006) and Gassmann and Wallace (1996) describe computational studies which are based on interior point method and simplex based methods respectively.The rest of this paper is organised in the following way. In section 2 we introduce the model setting of the two stage stochastic programming problem, in section 3 we consider a selection of solution methods for processing this class of problems. The established approaches of processing the deterministic equivalent LP form, the decomposition approach of Benders, the needfor regularisation are also discussed. We also introduce the concept of level decomposition and explain how it ﬁts into the concept of regularisation. In section 4 we set out the computational study and in section 5 we summariseour conclusions.
Tue, 19 May 2009 00:00:00 GMThttp://edoc.hu-berlin.de/18452/90532009-05-19T00:00:00ZZverovich, V.Fábièn, C.Ellison, F.Mitra, G.Formulation of stochastic optimisation problems and computational algorithms for their solution continue to make steady progress as can be seenfrom an analysis of many developments in this ﬁeld. The edited volume by Wallace and Ziemba (2005) outlines both the SP modelling systems andmany applications in diverse domains.More recently, Fabozzi (2008) has considered the application of SP models to challenging ﬁnancial engineering problems. The tightly knit yet highlyfocused group of researchers COSP: Committee on Stochastic Programming, their triennial international SP conference, and their active website points to the progressive acceptance of SP as a valuable decision tool. At the same time many of the major software vendors, namely, XPRESS, AIMMS, and MAXIMAL GAMS have started offering SP extensions to their optimisation suites.Our analysis of the modelling and algorithmic solver requirements reveals that (a) modelling support (b) scenario generation and (c) solutionmethods are three important aspects of a working SP system. Our research is focussed on all three aspects and we refer the readers to Valente et al.(2009) for modelling and Mitra et al. (2007) and Di Domenica et al. (2009) for scenario generation. In this paper we are concerned entirely with com-putational solution methods. Given the tremendous advance in LP solver algorithms there is certain amount of complacency that by constructing a”deterministic equivalent” problems it is possible to process most realistic instances of SP problems. In this paper we highlight the shortcoming of this line of argument. We describe the implementation and reﬁnement of established algorithmic methods and report a computational study which clearly underpins the superior scale up properties of the solution methods which aredescribed in this paper.A taxonomy of the important class of SP problems may be found in Valente et al. (2008, 2009). The most important class of problems with manyapplications is the two-stage stochastic programming model with recourse, which originated from the early research of Dantzig (1955), Beale (1955) and Wets (1974).A comprehensive treatment of the model and solution methods can be found in Kall and Wallace (1994), Prekopa (1995), Birge and Louveaux (1997), Mayer (1998), Ruszczynski and Shapiro (2003), and Kall and Mayer (2005). Some of these monographs contain generalisations of the originalmodel. Colombo et al. (2006) and Gassmann and Wallace (1996) describe computational studies which are based on interior point method and simplex based methods respectively.The rest of this paper is organised in the following way. In section 2 we introduce the model setting of the two stage stochastic programming problem, in section 3 we consider a selection of solution methods for processing this class of problems. The established approaches of processing the deterministic equivalent LP form, the decomposition approach of Benders, the needfor regularisation are also discussed. We also introduce the concept of level decomposition and explain how it ﬁts into the concept of regularisation. In section 4 we set out the computational study and in section 5 we summariseour conclusions.An enhanced model for portfolio choice with SSD criteria: a constructive approach
http://edoc.hu-berlin.de/18452/9052
An enhanced model for portfolio choice with SSD criteria: a constructive approach
Fábián, C.; Mitra, G.; Roman, D.; Zverovich, V.
Buch
http://dx.doi.org/10.18452/8400
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We formulate a portfolio planning model which is based on Second-order Stochastic Dominance as the choice criterion. This model is an enhanced version of the multi-objective model proposed by Roman, Darby-Dowman, and Mitra (2006); the model compares the scaled values of the different objectives, representing tails at different conﬁdence levels of the resulting distribution. The proposed model can be formulated asrisk minimisation model where the objective function is a convex risk measure; we characterise this risk measure and the resulting optimisation problem. Moreover, our formulation oﬀers a natural generalisation of the SSD-constrained model of Dentcheva and Ruszczynski (2006). A cutting plane-based solution method for the proposed model is outlined. We present a computational study showing: (a) the effectiveness of thesolution methods and (b) the improved modelling capabilities: the resulting portfolios have superior return distributions.
Wed, 22 Apr 2009 00:00:00 GMThttp://edoc.hu-berlin.de/18452/90522009-04-22T00:00:00ZFábián, C.Mitra, G.Roman, D.Zverovich, V.We formulate a portfolio planning model which is based on Second-order Stochastic Dominance as the choice criterion. This model is an enhanced version of the multi-objective model proposed by Roman, Darby-Dowman, and Mitra (2006); the model compares the scaled values of the different objectives, representing tails at different conﬁdence levels of the resulting distribution. The proposed model can be formulated asrisk minimisation model where the objective function is a convex risk measure; we characterise this risk measure and the resulting optimisation problem. Moreover, our formulation oﬀers a natural generalisation of the SSD-constrained model of Dentcheva and Ruszczynski (2006). A cutting plane-based solution method for the proposed model is outlined. We present a computational study showing: (a) the effectiveness of thesolution methods and (b) the improved modelling capabilities: the resulting portfolios have superior return distributions.A model for dynamic chance constraints in hydro power reservoir management
http://edoc.hu-berlin.de/18452/9051
A model for dynamic chance constraints in hydro power reservoir management
Andrieu, L.; Henrion, R.; Römisch, W.
Buch
http://dx.doi.org/10.18452/8399
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
In this paper, a model for (joint) dynamic chance constraints is proposed and applied to an optimization problem in water reservoir management. The model relies on discretization of the decision variables but keeps the probability distribution continuous. Our approach relies on calculating probabilities of rectangles, which isparticularly useful in the presence of independent random variables but works for a moderate number of stages equally well in case of correlated variables. Numerical results are provided for two and three stages.
Sun, 05 Apr 2009 00:00:00 GMThttp://edoc.hu-berlin.de/18452/90512009-04-05T00:00:00ZAndrieu, L.Henrion, R.Römisch, W.In this paper, a model for (joint) dynamic chance constraints is proposed and applied to an optimization problem in water reservoir management. The model relies on discretization of the decision variables but keeps the probability distribution continuous. Our approach relies on calculating probabilities of rectangles, which isparticularly useful in the presence of independent random variables but works for a moderate number of stages equally well in case of correlated variables. Numerical results are provided for two and three stages.