16

$\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.

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
Pantelis Sopasakis
  • 749
  • 4
  • 8
  • You mean something like the TSP (travelling salesman problem)? – Steven01123581321 Jun 03 '19 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. – Pantelis Sopasakis Jun 03 '19 at 16:26
  • 1
    ok. In inventory control, I recently come accross a paper that might fits your question. https://www.researchgate.net/publication/323102042_A_simulation-optimization_approach_for_a_service-_constrained_multi-echelon_distribution_network – Steven01123581321 Jun 03 '19 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.) – LarrySnyder610 Jun 04 '19 at 03: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. – LarrySnyder610 Jun 04 '19 at 03:14
  • And I suspect there are some that use scenarios to represent uncertainties in generator/line failures etc. – LarrySnyder610 Jun 04 '19 at 03:19
  • @PantelisSopasakis If I am interpreting correctly, linear multi-stage stochastic programming is a special case of the convex function you posted. Is that correct? And if so are you also looking for linear benchmarks, or only nonlinear convex ones? – LarrySnyder610 Jun 14 '19 at 02:25
  • @LarrySnyder610 Yes, I'm looking for convex, but not necessarily linear problems. For example, there can be quadratic terms, $x^\top Q x$, with $Q$ being a symmetric positive semi-definite matrix, or any other convex terms. Linear multi-stage problems indeed fall in the class of convex multistage problems. The problems in power grids you suggested look interesting. – Pantelis Sopasakis Jun 15 '19 at 10:18

3 Answers3

7

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.

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
Rahul Patel
  • 161
  • 6
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." 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.

Oguz Toragay
  • 8,652
  • 2
  • 13
  • 41
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.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.

odow
  • 51
  • 4
  • 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 03 '19 at 21:39
  • Thanks @EhsanK, I've edit the post to reflect your suggestions. – odow Jul 05 '19 at 13:47