# Benchmark problems for scenario-based stochastic optimization

$$\newcommand{\E}{\mathbb{E}}$$I am working on numerical algorithms for solving convex large-scale multistage scenario-based problems and I am looking for some standard benchmarks problems. I have so far worked with scenario trees generated from data, but I wonder whether there are some standard problems. I would be particularly interested in problems in the general area of economics or some interesting engineering application.

I am referring to problems in the general form

\begin{align} \min_{u_0 \in U_0} \E_{\mid 0} \bigg[\ell_0(x_0, u_0, w_0) +& \inf_{u_1 \in U_1} \E_{\mid 1}\Big[\ell_0(x_1, u_1, w_1) + \ldots \\ +&\inf_{u_{N-1}\in U_{N-1}} \E_{\mid N-1}[\ell_{N}(x_N)]\cdots \Big]\bigg], \end{align}

subject to $$x_{t+1} = f(x_t, u_t, w_t)$$, where $$f$$ is linear in $$x$$ and $$u$$, $$\ell$$ is convex in its first two arguments, $$(w_t)$$ is a random process whose evolution is described by a scenario tree (I will omit a detailed description here) and $$\E_{|t}$$ denotes the conditional expectation which is conditioned with the information that is available up to stage (time) $$t$$ [this is properly defined using the natural filtration of $$(w_t)_t$$].

I have seen such problems in the area of energy distribution management, but in most cases these involve binary variables (which correspond to the switching of generators), but I'm looking for problems without binaries.

• You mean something like the TSP (travelling salesman problem)? Jun 3, 2019 at 13:56
• No, the TSP is not a multistage scenario-based stochastic OCP. I'm referring to problems such as the ones in this book. I will update my question to clarify this. Jun 3, 2019 at 16:26
• ok. In inventory control, I recently come accross a paper that might fits your question. researchgate.net/publication/… Jun 3, 2019 at 16:29
• @FromTheoryToPractice That paper assumes the demand (the r.v. in question) has a normal distribution -- not the scenario-tree-based approach the OP was looking for. (But the supply chain in that paper is a tree -- maybe that's what caught your eye.) Jun 4, 2019 at 3:12
• @PantelisSopasakis There are electricity grid optimization problems without binary variables too, like multi-period OPF problems. We already know the on/off state of generators so those aren't represented by binary variables. Jun 4, 2019 at 3:14

You can check the Test Sets section of the Stochastic Programming Resources website. 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.

"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." Journal of Banking & Finance 30.2 (2006): 433-451."

The following may or may not help to provide some benchmark problems but definitely worth a short glance:

In the paper, "PySP: modeling and solving stochastic programs in Python", by "Jean-Paul Watson, David L. Woodruff, and William E. Hart", the authors explained the third party software and packages related to PySP. One of those packages, "DET2STO", provide a script taking an augmented AMPL model as input and generating the extensive form via an SMPS output file.

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.jl library. These are mostly small, but there are some large-scale problems such as a simplified model of the Brazilian electricity system.

There is also this medium-sized example from pastoral agriculture.

The python package msppy has some other examples, but these are mainly focused on binary problems.

• By following some of SE rules, you can improve the quality of your answer. e.g: hyperlink your references like other answers, use latex formatting for your number (e.g. $10^{40}$), and spell out the abbreviations you use for the first time (e.g. what is MPS or SMPS?). Or what is "msppy"? Is it a folder? (which seems to be)
– EhsanK
Jul 3, 2019 at 21:39
• Thanks @EhsanK, I've edit the post to reflect your suggestions.
– odow
Jul 5, 2019 at 13:47