Volume 2013
http://edoc.hu-berlin.de/18452/370
Thu, 03 Oct 2024 14:39:45 GMT2024-10-03T14:39:45ZAncestral Benders' Cuts and Multi-term Disjunctions for Mixed-Integer Recourse Decisions in Stochastic Programming
http://edoc.hu-berlin.de/18452/9090
Ancestral Benders' Cuts and Multi-term Disjunctions for Mixed-Integer Recourse Decisions in Stochastic Programming
Qi, Yunwei; Sen, Suvrajeet
Buch
http://dx.doi.org/10.18452/8438
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
This paper focuses on solving two-stage stochastic mixed integer programs (SMIPs) with general mixed integer decision variables in both stages. We develop a decomposition algorithm in which the first stage approximation is solved using a branch-and-bound tree with nodes inheriting Benders' cuts that are valid for their ancestor nodes. In addition, we develop two closely related convexification schemes which use multi-term disjunctive cuts to obtain approximations of the second stagemixed-integer programs. We prove that the proposed methods are finitely convergent. One of the main advantages of our decomposition scheme is that we use a Benders-based branch-and-cut approach in which linear programming approximations are strengthened sequentially. Moreover as inmany decomposition schemes, these subproblems can be solved in parallel. We also illustrate thesealgorithms using several variants of an SMIP example from the literature, and present preliminary evidence of the scalability of these algorithms as the number of scenarios increases.
Tue, 17 Sep 2013 00:00:00 GMThttp://edoc.hu-berlin.de/18452/90902013-09-17T00:00:00ZQi, YunweiSen, SuvrajeetThis paper focuses on solving two-stage stochastic mixed integer programs (SMIPs) with general mixed integer decision variables in both stages. We develop a decomposition algorithm in which the first stage approximation is solved using a branch-and-bound tree with nodes inheriting Benders' cuts that are valid for their ancestor nodes. In addition, we develop two closely related convexification schemes which use multi-term disjunctive cuts to obtain approximations of the second stagemixed-integer programs. We prove that the proposed methods are finitely convergent. One of the main advantages of our decomposition scheme is that we use a Benders-based branch-and-cut approach in which linear programming approximations are strengthened sequentially. Moreover as inmany decomposition schemes, these subproblems can be solved in parallel. We also illustrate thesealgorithms using several variants of an SMIP example from the literature, and present preliminary evidence of the scalability of these algorithms as the number of scenarios increases.Conditioning of linear-quadratic two-stage stochastic optimization problems
http://edoc.hu-berlin.de/18452/9089
Conditioning of linear-quadratic two-stage stochastic optimization problems
Emich, Konstantin; Henrion, René; Römisch, Werner
Buch
http://dx.doi.org/10.18452/8437
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
In this paper a condition number for linear-quadratic two-stage stochastic optimization problemsis introduced as the Lipschitz modulus of the multifunction assigning to a (discrete) probabilitydistribution the solution set of the problem. Being the outer norm of the Mordukhovich coderivativeof this multifunction, the condition number can be estimated from above explicitly in terms of theproblem data by applying appropriate calculus rules. Here, a chain rule for the extended partialsecond-order subdifferential recently proved by Mordukhovich and Rockafellar plays a crucial role.The obtained results are illustrated for the example of two-stage stochastic optimization problemswith simple recourse.
Thu, 25 Jul 2013 00:00:00 GMThttp://edoc.hu-berlin.de/18452/90892013-07-25T00:00:00ZEmich, KonstantinHenrion, RenéRömisch, WernerIn this paper a condition number for linear-quadratic two-stage stochastic optimization problemsis introduced as the Lipschitz modulus of the multifunction assigning to a (discrete) probabilitydistribution the solution set of the problem. Being the outer norm of the Mordukhovich coderivativeof this multifunction, the condition number can be estimated from above explicitly in terms of theproblem data by applying appropriate calculus rules. Here, a chain rule for the extended partialsecond-order subdifferential recently proved by Mordukhovich and Rockafellar plays a crucial role.The obtained results are illustrated for the example of two-stage stochastic optimization problemswith simple recourse.Bidding in sequential electricity markets: The Nordic case
http://edoc.hu-berlin.de/18452/9088
Bidding in sequential electricity markets: The Nordic case
Boomsma, Trine Krogh; Juul, Nina; Fleten, Stein-Erik
Buch
http://dx.doi.org/10.18452/8436
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
For electricity market participants trading in sequential markets with differences in price levels and riskexposure, coordinated bidding is highly relevant. We consider a Nordic power producer who engages inthe day-ahead spot market and the near real-time balancing market. In both markets, clearing prices anddispatched volumes are unknown at the time of bidding. However, in the balancing market, the agent facesan additional risk of not being dispatched. Taking into account the sequential clearing of these marketsand the gradual realization of market prices, we formulate the bidding problem as a multi-stage stochasticprogram. We investigate whether higher risk exposure can explain the hesitation, often observed in practice,to bid into the balancing market, even in cases of higher expected price levels. Furthermore, we quantify thegain from coordinated bidding, and by deriving bounds on this gain, assess the performance of alternativebidding strategies used in practice.
Wed, 24 Jul 2013 00:00:00 GMThttp://edoc.hu-berlin.de/18452/90882013-07-24T00:00:00ZBoomsma, Trine KroghJuul, NinaFleten, Stein-ErikFor electricity market participants trading in sequential markets with differences in price levels and riskexposure, coordinated bidding is highly relevant. We consider a Nordic power producer who engages inthe day-ahead spot market and the near real-time balancing market. In both markets, clearing prices anddispatched volumes are unknown at the time of bidding. However, in the balancing market, the agent facesan additional risk of not being dispatched. Taking into account the sequential clearing of these marketsand the gradual realization of market prices, we formulate the bidding problem as a multi-stage stochasticprogram. We investigate whether higher risk exposure can explain the hesitation, often observed in practice,to bid into the balancing market, even in cases of higher expected price levels. Furthermore, we quantify thegain from coordinated bidding, and by deriving bounds on this gain, assess the performance of alternativebidding strategies used in practice.A mixed-integer stochastic nonlinear optimization problem with joint probabilistic constraints
http://edoc.hu-berlin.de/18452/9087
A mixed-integer stochastic nonlinear optimization problem with joint probabilistic constraints
Arnold, T.; Henrion, R.; Möller, A.; Vigerske, S.
Buch
http://dx.doi.org/10.18452/8435
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We illustrate the solution of a mixed-integer stochastic nonlinear optimization problem in an application of power management. In this application, a coupled system consisting of a hydro power station and a wind farm is considered. The objective is to satisfy the local energy demand and sell any surplus energy on a spot market for a short time horizon. Generation of wind energy is assumed to be random, so that demand satisfaction is modeled by a joint probabilistic constraint taking into accountthe multivariate distribution. The turbine is forced to either operate between given positive limits or to be shut down. This introduces additional binary decisions. The numerical solution procedure is presented and results are illustrated.
Tue, 14 May 2013 00:00:00 GMThttp://edoc.hu-berlin.de/18452/90872013-05-14T00:00:00ZArnold, T.Henrion, R.Möller, A.Vigerske, S.We illustrate the solution of a mixed-integer stochastic nonlinear optimization problem in an application of power management. In this application, a coupled system consisting of a hydro power station and a wind farm is considered. The objective is to satisfy the local energy demand and sell any surplus energy on a spot market for a short time horizon. Generation of wind energy is assumed to be random, so that demand satisfaction is modeled by a joint probabilistic constraint taking into accountthe multivariate distribution. The turbine is forced to either operate between given positive limits or to be shut down. This introduces additional binary decisions. The numerical solution procedure is presented and results are illustrated.Electricity Swing Option Pricing by Stochastic Bilevel Optimization: a Survey and New Approaches
http://edoc.hu-berlin.de/18452/9086
Electricity Swing Option Pricing by Stochastic Bilevel Optimization: a Survey and New Approaches
Kovacevic, Raimund M.; Pflug, Georg Ch.
Buch
http://dx.doi.org/10.18452/8434
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We demonstrate how the problem of determining the ask price for electricityswing options can be considered as a stochastic bilevel program with asymmetricinformation. Unlike as for financial options, there is no way for basingthe pricing method on no-arbitrage arguments. Two main situations are analyzed:if the seller has strong market power he/she might be able to maximizehis/her utility, while in fully competitive situations he/she will just look for aprice which makes profit and has acceptable risk. In both cases the seller hasto consider the decision problem of a potential buyer - the valuation problemof determining a fair value for a specific option contract - and anticipate thebuyer's optimal reaction to any proposed strike price. We also discuss somemethods for finding numerical solutions of stochastic bilevel problems witha special emphasis on using duality gap penalizations.
Mon, 13 May 2013 00:00:00 GMThttp://edoc.hu-berlin.de/18452/90862013-05-13T00:00:00ZKovacevic, Raimund M.Pflug, Georg Ch.We demonstrate how the problem of determining the ask price for electricityswing options can be considered as a stochastic bilevel program with asymmetricinformation. Unlike as for financial options, there is no way for basingthe pricing method on no-arbitrage arguments. Two main situations are analyzed:if the seller has strong market power he/she might be able to maximizehis/her utility, while in fully competitive situations he/she will just look for aprice which makes profit and has acceptable risk. In both cases the seller hasto consider the decision problem of a potential buyer - the valuation problemof determining a fair value for a specific option contract - and anticipate thebuyer's optimal reaction to any proposed strike price. We also discuss somemethods for finding numerical solutions of stochastic bilevel problems witha special emphasis on using duality gap penalizations.Computational aspects of risk-averse optimizationin two-stage stochastic models
http://edoc.hu-berlin.de/18452/9085
Computational aspects of risk-averse optimizationin two-stage stochastic models
Fábián, Csaba I.
Buch
http://dx.doi.org/10.18452/8433
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Computational studies on two-stage stochastic programming problems indicate that aggregate models have better scale-up properties than disaggregate ones, though the threshold of breaking even may be high. In this paper we attempt to explain this phenomenon, and to lower this threshold.We present the on-demand accuracy approach of Oliveira and Sagastizábal in a form which shows that this approach, when applied to two-stage stochastic programming problems, combines the advantages of the disaggregate and the aggregate models.Moreover, we generalize the on-demand accuracy approach to constrained convex problems, and showhow to apply it to risk-averse two-stage stochastic programming problems.
Tue, 09 Apr 2013 00:00:00 GMThttp://edoc.hu-berlin.de/18452/90852013-04-09T00:00:00ZFábián, Csaba I.Computational studies on two-stage stochastic programming problems indicate that aggregate models have better scale-up properties than disaggregate ones, though the threshold of breaking even may be high. In this paper we attempt to explain this phenomenon, and to lower this threshold.We present the on-demand accuracy approach of Oliveira and Sagastizábal in a form which shows that this approach, when applied to two-stage stochastic programming problems, combines the advantages of the disaggregate and the aggregate models.Moreover, we generalize the on-demand accuracy approach to constrained convex problems, and showhow to apply it to risk-averse two-stage stochastic programming problems.The Natural Banach Space for Version Independent Risk Measures
http://edoc.hu-berlin.de/18452/9084
The Natural Banach Space for Version Independent Risk Measures
Pichler, Alois
Buch
http://dx.doi.org/10.18452/8432
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Risk measures, or coherent measures of risk are often considered on the space $L^\infty$, andimportant theorems on risk measures build on that space. Other risk measures, among themthe most important risk measure – the Average Value-at-Risk – are well-defined on the largerspace $L^1$ and this seems to be the natural domain space for this risk measure. Spectral riskmeasures constitute a further class of risk measures of central importance, and they are oftenconsidered on some $L^p$ space. But in many situations this is possibly unnatural, because any$L^p$ with $p > p_0$, say, is suitable to define the spectral risk measure as well. In addition tothat risk measures have also been considered on Orlicz and Zygmund spaces. So it remains fordiscussion and clarification, what the natural domain to consider a risk measure is?This paper introduces a norm, which is built from the risk measure, and a Banach space,which carries the risk measure in a natural way. It is often strictly larger than its originaldomain, and obeys the key property that the risk measure is finite valued and continuous onthat space in an elementary and natural way.
Tue, 09 Apr 2013 00:00:00 GMThttp://edoc.hu-berlin.de/18452/90842013-04-09T00:00:00ZPichler, AloisRisk measures, or coherent measures of risk are often considered on the space $L^\infty$, andimportant theorems on risk measures build on that space. Other risk measures, among themthe most important risk measure – the Average Value-at-Risk – are well-defined on the largerspace $L^1$ and this seems to be the natural domain space for this risk measure. Spectral riskmeasures constitute a further class of risk measures of central importance, and they are oftenconsidered on some $L^p$ space. But in many situations this is possibly unnatural, because any$L^p$ with $p > p_0$, say, is suitable to define the spectral risk measure as well. In addition tothat risk measures have also been considered on Orlicz and Zygmund spaces. So it remains fordiscussion and clarification, what the natural domain to consider a risk measure is?This paper introduces a norm, which is built from the risk measure, and a Banach space,which carries the risk measure in a natural way. It is often strictly larger than its originaldomain, and obeys the key property that the risk measure is finite valued and continuous onthat space in an elementary and natural way.Convex approximations for totally unimodular integerrecourse models: A uniform error bound
http://edoc.hu-berlin.de/18452/9083
Convex approximations for totally unimodular integerrecourse models: A uniform error bound
Romeijnders, Ward; Vlerk, Maarten H. van der; Haneveld, Willem K. Klein
Buch
http://dx.doi.org/10.18452/8431
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We consider a class of convex approximations for totally unimodular (TU) integer recourse models and derive a uniform error bound by exploiting properties of the total variation of the probability density functions involved. For simple integer recourse models this error bound is tight and improves the existing one by a factor 2, whereas for TU integer recourse modelsthis is the first nontrivial error bound available. The bound ensures that theperformance of the approximations is good as long as the total variations of the densities of all random variables in the model are small enough.
Tue, 02 Apr 2013 00:00:00 GMThttp://edoc.hu-berlin.de/18452/90832013-04-02T00:00:00ZRomeijnders, WardVlerk, Maarten H. van derHaneveld, Willem K. KleinWe consider a class of convex approximations for totally unimodular (TU) integer recourse models and derive a uniform error bound by exploiting properties of the total variation of the probability density functions involved. For simple integer recourse models this error bound is tight and improves the existing one by a factor 2, whereas for TU integer recourse modelsthis is the first nontrivial error bound available. The bound ensures that theperformance of the approximations is good as long as the total variations of the densities of all random variables in the model are small enough.