Volume 2008http://edoc.hu-berlin.de/18452/3652024-07-18T15:07:20Z2024-07-18T15:07:20ZStochastic Nash Equilibrium Problems: Sample Average Approximation and ApplicationsXu, HuifuZhang, Dalihttp://edoc.hu-berlin.de/18452/90502020-03-07T04:14:37Z2008-12-19T00:00:00ZStochastic Nash Equilibrium Problems: Sample Average Approximation and Applications
Xu, Huifu; Zhang, Dali
http://dx.doi.org/10.18452/8398
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
This paper presents a Nash equilibrium model where the underlying objective functionsinvolve uncertainties and nonsmoothness. The well known sample average approximationmethod is applied to solve the problem and the ﬁrst order equilibrium conditions are characterized in terms of Clarke generalized gradients. Under some moderate conditions, it is shown that with probability one, a statistical estimator obtained from sample average approximateequilibrium problem converges to its true counterpart. Moreover, under some calmness conditions of the generalized gradients and metric regularity of the set-valued mappings whichcharacterize the ﬁrst order equilibrium conditions, it is shown that with probability approaching one exponentially fast with the increase of sample size, the statistical estimatorconverge to its true counterparts. Finally, the model is applied to an equilibrium problem inelectricity market.
2008-12-19T00:00:00ZApproximations and contamination bounds for probabilistic programsBranda, MartinDupacova, Jitkahttp://edoc.hu-berlin.de/18452/90492020-03-07T04:14:37Z2008-09-16T00:00:00ZApproximations and contamination bounds for probabilistic programs
Branda, Martin; Dupacova, Jitka
http://dx.doi.org/10.18452/8397
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
In this paper we aim at output analysis with respect to changes of the probability distribution for problems with probabilistic (chance) constraints. The perturbations are modeled via contamination of the initial probability distribution. Dependence of the set of solutions on the probability distributionrules out the straightforward construction of the convexity-based global contamination bounds for the perturbed optimal value function whereas localresults can be still obtained. To get global bounds we shall explore several approximations and reformulations of stochastic programs with probabilistic constraints by stochastic programs with suitably chosen recourse or penaltytype objectives and ﬁxed constraints.
2008-09-16T00:00:00ZConvergence Analysis of a Weighted Barrier Decomposition Algorithm for Two Stage Stochastic ProgrammingMehrotra, SanjayOzevin, M. Gokhanhttp://edoc.hu-berlin.de/18452/90482020-03-07T04:14:36Z2008-07-05T00:00:00ZConvergence Analysis of a Weighted Barrier Decomposition Algorithm for Two Stage Stochastic Programming
Mehrotra, Sanjay; Ozevin, M. Gokhan
http://dx.doi.org/10.18452/8396
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Mehrotra and Ozevin [7] computationally found that a weighted primal barrier decomposition algorithm signiﬁcantly outperforms the barrier decomposition proposed and analyzed in [11; 6; 8]. Thispaper provides a theoretical foundation for the weighted barrier decomposition algorithm (WBDA)in [7]. Although the worst case analysis of the WBDA achieves a ﬁrst-stage iteration complexitybound that is worse than the bound shown for the decomposition algorithms of [11] and [6; 8],under a probabilistic assumption we show that the worst case iteration complexity of WBDA isindependent of the number of scenarios in the problem. The probabilistic assumption uses a novelconcept of self-concordant random variables.
2008-07-05T00:00:00ZNumerical Evaluation of Approximation Methods in Stochastic ProgrammingKüchler, ChristianVigerske, Stefanhttp://edoc.hu-berlin.de/18452/90472020-03-07T04:14:36Z2008-07-02T00:00:00ZNumerical Evaluation of Approximation Methods in Stochastic Programming
Küchler, Christian; Vigerske, Stefan
http://dx.doi.org/10.18452/8395
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We study an approach for the evaluation of approximation and solution methodsfor multistage linear stochastic programs by measuring the performance of the obtained solutions on a set of out-of-sample scenarios. The main point of the approachis to restore the feasibility of solutions to an approximated problem along the out-of-sample scenarios. For this purpose, we consider and compare different feasibilityand optimality based projection methods. With this at hand, we study the quality of solutions to different test models based on classical as well as recombiningscenario trees.
2008-07-02T00:00:00ZProcessing Second-Order Stochastic Dominance models using cutting-plane representationsFabian, Csaba I.Mitra, GautamRoman, Dianahttp://edoc.hu-berlin.de/18452/90462020-03-07T04:14:36Z2008-07-02T00:00:00ZProcessing Second-Order Stochastic Dominance models using cutting-plane representations
Fabian, Csaba I.; Mitra, Gautam; Roman, Diana
http://dx.doi.org/10.18452/8394
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Second-order stochastic dominance (SSD) is widely recognised as an important decision criteria in portfolio selection. Unfortunately, stochastic dominance models can be very demanding from a computational point of view. In this paper we consider two types of models which use SSD as a choice criterion. The ﬁrst, proposed by Dentcheva and Ruszczyski (2006), uses a SSD constraint, which can be written as a set of integrated chance constraints (ICCs). The second, proposed by Roman, Darby-Dowman, and Mitra (2006) usesSSD through a multi-objective formulation with CVaR objectives. Cutting plane representations andalgorithms were proposed by Klein Haneveld and van der Vlerk (2006) for ICCs, and by Künzi-Bay and Mayer (2006) for CVaR minimization. These concepts are taken into consideration to proposerepresentations and solution methods for the above class of SSD based models. We describe a cuttingplane based solution algorithm and give implementation details. A computational study is presented,which demonstrates the effectiveness and the scale-up properties of the solution algorithm, as applied tothe SSD model of Roman, Darby-Dowman, and Mitra (2006).
2008-07-02T00:00:00ZOn Stability of Multistage Stochastic ProgramsKüchler, Christianhttp://edoc.hu-berlin.de/18452/90452020-03-07T04:14:36Z2008-07-02T00:00:00ZOn Stability of Multistage Stochastic Programs
Küchler, Christian
http://dx.doi.org/10.18452/8393
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We study quantitative stability of linear multistage stochastic programs underperturbations of the underlying stochastic processes. It is shown that the optimalvalues behave Lipschitz continuous with respect to an $L_p$-distance. Therefore, wehave to make a crucial regularity assumption on the conditional distributions, thatallows to establish continuity of the recourse function with respect to the currentstate of the stochastic process. The main stability result holds for nonanticipativediscretizations of the underlying process and thus represents a rigorous justiﬁcationof established discretization techniques.
2008-07-02T00:00:00ZScenario tree reduction for multistage stochastic programsHeitsch, HolgerRömisch, Wernerhttp://edoc.hu-berlin.de/18452/90442020-03-07T04:14:36Z2008-04-05T00:00:00ZScenario tree reduction for multistage stochastic programs
Heitsch, Holger; Römisch, Werner
http://dx.doi.org/10.18452/8392
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
A framework for the reduction of scenario trees as inputs of (linear) multistage stochastic programs is provided such that optimal values and approximate solution sets remain close to each other. The argument is based on upper bounds of the $L_r$-distance and the ﬁltration distance, and on quantitative stability results for multistage stochastic programs. The important difference from scenario reduction in two-stage models consists in incorporating the ﬁltration distance. Analgorithm is presented for selecting and removing nodes of a scenario tree suchthat a prescribed error tolerance is met. Some numerical experience is reported.
2008-04-05T00:00:00ZEpi-convergent scenario generation method for stochastic problems via sparse gridChen, MichaelMehrotra, Sanjayhttp://edoc.hu-berlin.de/18452/90432020-03-07T04:14:35Z2008-04-05T00:00:00ZEpi-convergent scenario generation method for stochastic problems via sparse grid
Chen, Michael; Mehrotra, Sanjay
http://dx.doi.org/10.18452/8391
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
One central problem in solving stochastic programming problems is to generate moderate-sized scenario trees which represent well the risk faced by a decision maker. In this paper we propose an efﬁcient scenario generation method based on sparse grid, and prove it is epi-convergent. Furthermore, we show numerically that the proposed method converges to the true optimal value fast in comparisonwith Monte Carlo and Quasi Monte Carlo methods.
2008-04-05T00:00:00ZDelta-Hedging a Hydropower Plant Using Stochastic ProgrammingFleten, Stein-ErikStein, W.http://edoc.hu-berlin.de/18452/90422020-03-07T04:14:35Z2008-03-17T00:00:00ZDelta-Hedging a Hydropower Plant Using Stochastic Programming
Fleten, Stein-Erik; Stein, W.
http://dx.doi.org/10.18452/8390
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
An important challenge for hydropower producers is to optimize reservoir discharges, which is subject to uncertainty in inﬂow and electricity prices. Furthermore, the producers want to hedge the risk in the operating proﬁt. This article demonstrates how stochasticprogramming can be used to solve a multi-reservoir hydro scheduling case for a price-takingproducer, and how such a model can be employed in subsequent delta-hedging of the electric-ity portfolio.
2008-03-17T00:00:00ZDantzig-Wolfe decomposition for solving multi-stage stochastic capacity-planning problemsSing, Kavinesh J.Philpott, Andy B.Wood, R. Kevinhttp://edoc.hu-berlin.de/18452/90412020-03-07T04:14:35Z2008-03-07T00:00:00ZDantzig-Wolfe decomposition for solving multi-stage stochastic capacity-planning problems
Sing, Kavinesh J.; Philpott, Andy B.; Wood, R. Kevin
http://dx.doi.org/10.18452/8389
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We describe a multi-stage, stochastic, mixed-integer-programming model for planning discrete capacity expansion of production facilities. A scenario tree represents uncertainty in the model; a general mixed-integer program deﬁnes the operational submodel at each scenario-tree node; and capacity-expansion decisions link the stages. We apply “variable splitting” to two model variants, and solve those variants using Dantzig-Wolfe decomposition. The Dantzig-Wolfemaster problem can have a much stronger linear-programming relaxation than is possible without variable splitting, over 700% stronger in one case. The master problem solves easily and tends to yield integer solutions, obviating the need for a full branch-and-price solution procedure. For each scenario-tree node, the decomposition deﬁnes a subproblem that may be viewed as a single-period, deterministic, capacity-planning problem. An effective solution procedure results as long as the subproblems solve efficiently, and the procedure incorporates a good “duals stabilization scheme.” We present computational results for a model to plan the capacity expansion of an electricity distribution network in New Zealand, given uncertain future demand.The largest problem we solve to optimality has 6 stages and 243 scenarios, and corresponds to adeterministic equivalent with a quarter of a million binary variables.
2008-03-07T00:00:00ZOn the convergence of stochastic dual dynamic programming and related methodsPhilpott, A. B.Guan, Z.http://edoc.hu-berlin.de/18452/90402020-03-07T04:14:35Z2008-03-06T00:00:00ZOn the convergence of stochastic dual dynamic programming and related methods
Philpott, A. B.; Guan, Z.
http://dx.doi.org/10.18452/8388
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We discuss the almost-sure convergence of a broad class of sampling algorithms for multi-stage stochastic linear programs. We provide a convergence proof based on the ﬁniteness of the set of distinct cutcoefficients. This differs from existing published proofs in that it does not require a restrictive assumption.
2008-03-06T00:00:00ZStochastic optimization models for a single-sink transportation problemMaggioni, FrancescaKaut, MichalBertazzi, Lucahttp://edoc.hu-berlin.de/18452/90392020-03-07T04:14:35Z2008-03-06T00:00:00ZStochastic optimization models for a single-sink transportation problem
Maggioni, Francesca; Kaut, Michal; Bertazzi, Luca
http://dx.doi.org/10.18452/8387
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
In this paper we study a single-sink transportation problem in which the production capacity of the suppliers and the demand of the single customer are stochastic. Shipments are performed by capacitated vehicles, which have to be booked in advance, before the realization of the production capacity and the demand. Once the production capacity and the demand are revealed, there is an option to cancel some of the booked vehicles against a cancellation fee. If the quantity shipped from the suppliers using the booked vehicles is not enough to satisfy the demand, the residual quantity is purchased from an external company. The problem is to determine the number of vehicles to book in order to minimize the total cost.We formulate a two-stage and a multistage stochastic mixed integer linear programming models to solve this problem and test them on a real case provided by Italcementi, the primary Italian clinker producer and the 5th largest cement producer in the world. We test the inﬂuence of different scenario-tree structures on the solutions of the problem, as well as sensitivity of the results with respect to the cancellation fee.
2008-03-06T00:00:00ZA dynamic day-ahead paratransit planning problemCremers, Maria L.A.G.Haneveld, Willem K. KleinVlerk, Maarten H. van derhttp://edoc.hu-berlin.de/18452/90382020-03-07T04:14:34Z2008-03-06T00:00:00ZA dynamic day-ahead paratransit planning problem
Cremers, Maria L.A.G.; Haneveld, Willem K. Klein; Vlerk, Maarten H. van der
http://dx.doi.org/10.18452/8386
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We consider a dynamic planning problem for the transport of elderly and disabled people. The focus is on a decision to make one day ahead:which requests to serve with own vehicles, and which ones to assign to subcontractors, under uncertainty of late requests which are gradually revealed during the day of operation. We call this problem the Dynamic Day-ahead Paratransit Planning problem. The developed model is a non-standard two-stage recourse model in which ideas from stochastic programming and online optimization are combined: in the ﬁrst stage clustered requests are assigned to vehicles, and in the dynamic second-stage problem an event-driven approach is used to cluster the late requests once they are revealed and subsequently assign them to vehicles. A genetic algorithm is used to solve the model. Computational results are presented for randomly generated data sets. Furthermore, a comparison is made to a similar problem we studied earlier in which the simplifying but unrealistic assumption has been made that all late requests are revealed at the beginning of the day of operation.
2008-03-06T00:00:00ZDisjunctive decomposition for two-stage stochastic mixed-binary programs with random recourseNtaimo, Lewishttp://edoc.hu-berlin.de/18452/90372020-03-07T04:14:34Z2008-02-22T00:00:00ZDisjunctive decomposition for two-stage stochastic mixed-binary programs with random recourse
Ntaimo, Lewis
http://dx.doi.org/10.18452/8385
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
This paper introduces disjunctive decomposition for two-stage mixed 0-1 stochastic integer programs (SIPs) with random recourse. Disjunctive decomposition allows for cutting planes based on disjunctive programming to be generated for each scenario subproblem under a temporal decomposition setting of the SIP problem.A new class of valid inequalities for mixed 0-1 SIP with random recourse is presented. In particular, valid inequalities that allow for sharing cut coefficients among scenario subproblems for SIP with random recourse but deterministic technology matrix and righthand side vector are obtained. The valid inequalities are used to derive a disjunctive decomposition method whose derivation has been motivatedby real-life stochastic server location problems with random recourse, which ﬁnd many applications in operations research. Computational results with large-scaleinstances to demonstrate the potential of the method are reported.
2008-02-22T00:00:00Z