15
$\begingroup$

$\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} \operatorname*{Minimize}_{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.

$\endgroup$
  • $\begingroup$ You mean something like the TSP (travelling salesman problem)? $\endgroup$ – Steven31415 Jun 3 at 13:56
  • $\begingroup$ 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. $\endgroup$ – Pantelis Sopasakis Jun 3 at 16:26
  • 1
    $\begingroup$ ok. In inventory control, I recently come accross a paper that might fits your question. researchgate.net/publication/… $\endgroup$ – Steven31415 Jun 3 at 16:29
  • $\begingroup$ @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.) $\endgroup$ – LarrySnyder610 Jun 4 at 3:12
  • $\begingroup$ @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. $\endgroup$ – LarrySnyder610 Jun 4 at 3:14
5
$\begingroup$

"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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This may be better suited as a comment, although you do not yet have enough reputation to do so. $\endgroup$ – TheSimpliFire Jun 21 at 15:26
  • $\begingroup$ I disagree, I think this is suited as an answer, but it might be good if @RahulPatel can flesh it out a little so it’s not primarily just a link. $\endgroup$ – LarrySnyder610 Jun 22 at 14:35
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – EhsanK Jul 3 at 21:39
  • $\begingroup$ Thanks @EhsanK, I've edit the post to reflect your suggestions. $\endgroup$ – odow Jul 5 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.