Volume 2005
http://edoc.hu-berlin.de/18452/362
2021-05-10T18:45:53ZDecomposing CVaR minimization in two-stage stochastic models
http://edoc.hu-berlin.de/18452/9001
Decomposing CVaR minimization in two-stage stochastic models
Fabian, Csaba I.
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Based on the polyhedral representation of Künzi-Bay and Mayer (2005), we propose a decomposition framework for the minimization of CVaR in two-stage stochastic models.We show that the decomposed problems can be effectively solved by a special inexact-cut method.
2005-12-29T00:00:00ZA Comparative Study of Decomposition Algorithms for Stochastic Combinatorial Optimization
http://edoc.hu-berlin.de/18452/9000
A Comparative Study of Decomposition Algorithms for Stochastic Combinatorial Optimization
Ntaimo, Lewis; Sen, Suvrajeet
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
This paper presents comparative computational results using three decomposition algorithms on a battery of instances drawn from three different applications. In order to preserve the commonalities among the algorithms in our experiments, we have designed a testbed which is used to study instances arising in server location under uncertainty, strategic supply chain planning under uncertainty, and stochastic bipartitite matching. Insights related to alternative implementation issues leading to more efficient implementations, benchmarks for serial processing, and scalability of the methods are also presented. The computational experience demonstrates the promising potential of the disjunctive decomposition $(D^2)$ approach towards solving several large-scale problem instances from the three application areas. Furthermore, the study shows that convergence of the $D^2$ methods for stochastic combinatorial optimization (SCO) is in fact attainable since the methods scale well with the number of scenarios.
2005-12-29T00:00:00ZAggregation and Discretization in Multistage Stochastic Programming
http://edoc.hu-berlin.de/18452/8999
Aggregation and Discretization in Multistage Stochastic Programming
Kuhn, Daniel
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Multistage stochastic programs have applications in many areas and support policy makers in finding rational decisions that hedge against unforeseen neg- ative events. In order to ensure computational tractability, continuous-state stochastic programs are usually discretized; and frequently, the curse of dimensionality dictates that decision stages must be aggregated. In this article we construct two discrete, stage-aggregated stochastic programs which provide upper and lower bounds on the optimal value of the original problem. The approximate problems involve finitely many decisions and constraints, thus principally allowing for numerical solution.
2005-12-28T00:00:00ZAmbiguous chance constrained problems and robust optimization
http://edoc.hu-berlin.de/18452/8998
Ambiguous chance constrained problems and robust optimization
Erdogan, E.; Iyengar, G.
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
In this paper we study ambiguous chance constrained problems where the distributions of the random parameters in the problem are themselves uncertain. We focus primarily on the special case where the uncertainty set Q of the distributions is of the form $Q = {Q : \rho_p(Q;Q_0) \le \beta}$, where $\rho_p$ denotes the Prohorov metric. The ambiguous chance constrained problem is approximated by a robust sampled problem where each constraint is a robust constraint centered at a sample drawn according to the central measure $Q_0$. The main contribution of this paper is to show that the robust sampled problem is a good approximation for the ambiguous chance constrained problem with a high probability. This result is established using the Strassen-Dudley Representation Theorem that states that when the distributions of two random variables are close in the Prohorov metric one can construct a coupling of the random variables such that the samples are close with a high probability. We also show that the robust sampled problem can be solved efficiently both in theory and in practice.
2005-08-30T00:00:00Z