# Tag Info

19

If you have access to MATLAB, I can recommend Marietta (I am a developer of this toolbox), with which you can solve general risk-averse optimal control problems (a generalization of both stochastic and minimax problems), and impose risk constraints (which can serve as convex approximations of probabilistic constraints). As Larry commented above, PYOMO is ...

14

Disclaimer: I'm not a researcher in the area of stochastic programming software. But as a researcher in the area of stochastic programming, I've put some time into looking for stochastic programming software. So, the following is my own two cents. Dealing with stochastic programming models, usually, you reformulate the problem as a deterministic equivalent ...

12

In reference to the first question, I think it often comes down to the information you have about the underlying uncertainty. If you only have intervals or ranges, robust is the way to go. If you have all of the distributional information (or assume it), stochastic programming is an option. As @TheSimpliFire mentioned, you can include risk measures in ...

12

I think there is no single, uniformly accepted answer. But there are two main factors that distinguish them: In stochastic optimization, it is nearly always assumed that we know the probability distribution (possibly in the form of discrete probabilities of each scenario) of the random parameters. In robust optimization it is usually (but not always) ...

10

If you have historical data, you might use them as scenario inputs to a scenario reduction algorithm. Some references are available from here and here. Fitting a probability distribution does not prevent you from using a scenario approach to modeling uncertainty. In fact, the scenario approach is a popular and viable approach for handling uncertainty ...

10

The following papers discuss this extensively with numerical experiments, but they tackle specific examples. Emphasis is mine. Kazamzadeh et al. (2017) This is a comparison of the two techniques using the example of unit commitment, answering your first question. A popular impression has arisen that the robust approach, with its focus on the worst case, is ...

9

Regarding your first question, I think other answers have summed it up pretty good. Two things I would add are as follows: Stochastic programming models (besides chance constraint/probabilistic programming ones) allow you to correct your decision using the concept of recourse. In this idea, you have to make some decisions before the realization of uncertain ...

9

I don't know if it's really what you are asking for, but Julia has a few packages that implement algorithms for stochastic programming (on top of other LP solvers): StochDynamicProgramming.jl (seems more oriented towards control problems) StochasticPrograms.jl, rather complete modelling environment SDDP.jl, an implementation of SDDP and a modelling layer ...

9

The following is purely personal opinion. I would say a (substantial) majority of non-academic optimization problems do not involve any of the methods you listed, for a number of reasons. "Better is the enemy of good enough." Using fixed, plausible values for parameters and ignoring uncertainty often produce answers that are good enough for ...

8

Let me first distinguish between two-stage and multi-stage models by emphasizing on two issues, namely the type of uncertainty covered by each model and the sources of stochastic parameters. In two-stage models, you have to assume that stochastic parameters are stationary after being observed. On the other hand, multi-stage models assume a non-stationary ...

7

Since $\hat q_{N'}(\hat x)\approx\Bbb E[Q(\hat x,\xi)]$ and $\Bbb V[\hat q_{N'}(\hat x)]=\Bbb V[Q(\hat x,\xi)]/N'$, we have \begin{align}\hat\sigma_{N'}^2(\hat x)=\Bbb V[\hat q_{N'}(\hat x)]&=\frac1{N'}\cdot\frac1{N'-1}\sum_{j=1}^{N'}[Q(\hat x,\xi^j)-\Bbb E[Q(\hat x,\xi)]]^2\\&\approx\frac1{N'(N'-1)}\sum_{j=1}^{N'}[Q(\hat x,\xi^j)-\hat q_{N'}(\hat x)]...

6

As it is explained here, this problem is a portfolio selection problem. The player should select the first $n$ booths with the maximum $E(g_i)=p_i \times r_i$ in which $E(g_i)$ represents the expected value of gain, then among the selected $n$ booths, the player should start playing the games from the one with maximum $r_i$. In other words, the selected ...

6

SAA is a very widely used technique for stochastic optimization problems and as far as I can see there are two frequently used approaches for the implementation of SAA. Please check Homem-de-Mello's survey paper. I will give you some references on a very specific problem (Influence Maximization) where these approaches are applied. In Lee2015, Wu2017, ...

6

In the paper by Crainic et al.1, the authors stated that "Focusing on two-stage formulations, we show how and under which conditions the reduced costs associated to the variables in the deterministic formulation can be used as an indicator for excluding/retaining decision variables in the stochastic model. We introduce a new measure, the Loss of Reduced ...

6

This problem is addressed in some detail in Section 2.1 of the paper Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems by Watson and Woodruff (a non-paywall version is given here). In general, proper selection can be quite tricky and is highly problem-specific. I recommend trying some of the tricks in the ...

5

Pantelis, It is a great detriment that no such collection of examples exists. One problem is that there is no established format for multistage problems like MPS. (There is SMPS [paper], but this doesn't scale to the types of problems we typically solve with $10^{40}$ leaf nodes in a scenario tree.) I have been collecting a number of examples in the SDDP....

5

"Ruszczynski, Andrzej, and Robert J. Vanderbei. "Frontiers of stochastically nondominated portfolios." Econometrica 71.4 (2003): 1287-1297". This paper provides a large number of test problems which for example were used for testing purpose in "Dentcheva, Darinka, and Andrzej Ruszczyński. "Portfolio optimization with stochastic dominance constraints." ...

5

You can check the Test Sets section of the Stochastic Programming Resources web site. It contains different types of problems—two-stage or multi-stage, mixed or pure IP, and even LP in the different stages. Hopefully, you should find something close to the problem type you are looking for.

4

This heavily depends on the application at hand and could vary all the way from milliseconds to months. It all comes down to rigorously defining the specs. Many parameters are in play: How long does your feedback loop need to be, i.e., how often does your system need to update? How high is the uncertainty and how does it grow over time? Do you know the ...

4

As Larry said, there is no single, uniformly accepted answer, so I'll make things even more interesting. In mechanical engineering, specifically in aircraft design where I used to work, we used the following terminology: Stochastic optimisation was to solve problems using any non-deterministic methods, e.g., particle swarm algorithms or evolutionary ...

4

I did a little research and found the paper that I have cited below. I think with 517 citations this paper and the reference therein can be a good source for you. Paper: Kaut, Michal, and Stein W. Wallace. "Evaluation of scenario-generation methods for stochastic programming." (2003).

4

To solve stochastic programming models with integer recourse, there are some methods. Most stochastic programming textbooks cover these methods. For example, chapter 7 of Introduction to Stochastic Programming by Birge and Louveux covers these techniques. In particular, I suggest either using the integer L-shaped method or the progressive hedging algorithm (...

4

Just to expand very slightly the comments by Mark: in general exact stochastic dynamic programming scales quite poorly. Value iteration complexity for each iteration is $O(A S^2)$ where $A$ is the number of actions and $S$ is the number of states. And the number of iterations goes up with the discount factor $\beta$ as the worse case number of iterations is $... 3 Given your emphasis on practical and implementation aspects, I think the following two lectures will interest you: Stochastic Programming Modeling by Jeff Linderoth (University of Wisconsin, Madison) Benders Decomposition for Solving Two-stage Stochastic Optimization Models by Jim Luedtke (University of Wisconsin, Madison) 3 To get$O(2^M M^2)$instead of$O(M!)$, you could modify the dynamic programming formulation of the traveling salesman problem, with a state for each subset of booths visited so far. 3 I hope to provide intuitively-appealing answers to both questions.$\textbf{Question 1:}$Infinite horizon MDP's do not care about the initial state. They attempt to be optimal in the sense that the policy is optimal for all given allowable initial states. Finite MDP's are computed as optimal for a given state. The policy is intended to be optimal only if ... 3 Markov decision problem theory and computation is based on using backward induction (dynamic programming) to recursively evaluate expected rewards. When we define a policy$\pi = (d_1, d_2,...,d_{N-1})$, we assume that$N$, the length of horizon or the number of epochs is given.While in the infinite horizon the policies can be defined as,$\nu = (d_1, d_2,......

3

How to generate a multivariate Gaussian? It must be answered somewhere on Cross Validated, but I cannot find it now, some comments at https://stats.stackexchange.com/questions/341805/are-mvrnorm-in-mass-r-package-and-rmvn-in-mgcv-r-package-equivalent/341808#341808. Let $X \sim \mathcal{N}(\mu, \Sigma)$ and $\epsilon \sim \mathcal{N}(0,I)$. Then we can ...

3

Whether maximizing expected winnings is an appropriate solution depends on the underlying problem and, crucially, the consumer of the solution (the problem "owner"). Two major considerations jump out at me. One is whether the owner requires a certain minimum payout with a certain probability, in which case you may need to use chance constrained ...

3

Yes. Assuming that $\alpha$, $\beta$ and $\gamma$ in the text are the same as $a$, $b$ and $g$ in the model, then $b_i$ should be $b_i y_i$.

Only top voted, non community-wiki answers of a minimum length are eligible