StochOptFormat

StochOptFormat: a data structure for multistage stochastic programming

This repository describes a data structure and file-format for stochastic optimization problems called StochOptFormat, with the file extension .sof.json.

For convenience, we abbreviate StochOptFormat to SOF.

StochOptFormat is defined by the JSON schema https://odow.github.io/StochOptFormat/versions/sof-1.schema.json.

Authors

Contents

Motivation and design principles

Libraries of benchmark instances have been instrumental in driving progress in many areas of optimization. In stochastic programming, some effort has been made on this front (see, for example, https://www.stoprog.org/resources). However, the predominant file format for these problems, SMPS [4], does not scale to the types of problems we want to solve (large multistage stochastic programs), nor does it permit the variety of problem classes we want to study (for example, stochastic conic programs).

A more recent attempt to standardize a file format for stochastic programming is the stochastic extension to OSiL [3]. StochOptFormat utilizes many of the underlying ideas, but it has enough differences to justify the creation of a new file format. In particular, we use a different standard form for a stochastic program and we do not use XML.

Over the last few years, we (and the broader JuMP team) have set about reimagining how we formulate single period deterministic optimziation problems. The result is a data structure for optimization called MathOptInterface [2]. In addition, we have also set about standardizing how we formulate multistage stochastic programming problems. The result is a natural decomposition of the problem into the policy graph [1].

Those papers present the reasoning of behind many aspects of their design, along with the necessary historical context. However, most of the key ideas can be grasped from the example in the next section. In particular, the example contains all the details required to fully describe a two-stage stochastic linear program. However, you should note that our work naturally extends beyond two-stage to multistage.

MathOptInterface and the policy graph are synergistic with each other. We can use the policy graph to describe the high-level structure of a stochastic program, and we can use MathOptInterface to describe the low-level optimization problem faced by the agent within each node of the policy graphs. Putting these two concepts together leads to a natural data structure for multistage stochastic programs. StochOptFormat is a serialization of this data structure into the JSON file format.

StochOptFormat is inspired by our work on JuMP and SDDP.jl. However, it is not exclusive to Julia or stochastic dual dynamic programming. For example, our format would make it possible to read multistage stochastic programming problems into Python and solve them with the progressive hedging library PySP. We have not implemented the code yet because this is not our area of expertise.

When developing StochOptFormat, we set out to create:

Equally as important as the things that we set out to do, are the things that we did not set out to do:

Finally, StochOptFormat is not an algebraic modeling language for stochastic programming. Instead, it is an instance format [5].

You should not need to write StochOptFormat files by hand. Nor should you need to consider the exact layout of the file when formulating your model. The analog is the MPS file format. No one writes MPS files by hand, and most people are probably unaware of the exact structure and syntax of an MPS file. Instead, we use high-level algebraic modeling languages like JuMP to build models, and we expect our solvers to handle the difficulty of reading and writing the MPS files.

Example

There are a lot of concepts to unpack in StochOptFormat. We present a two-stage stochastic linear program example first, and then explain each section of the corresponding StochOptFormat file in detail.

Consider a two-stage newsvendor problem. In the first stage, the agent chooses x, the number of newspapers to buy at a cost $1/newspaper. In the second stage, the uncertain demand of d newspapers is realized, and the agent sells u newspapers at a price of $1.50/newspaper, with the constraint that u = min{x, d}. The demand is either 10 units with probability 0.4, or 14 units with probability 0.6.

Vocabulary

Here, we briefly summarize the important terms used by StochOptFormat; we direct the reader to [1] for more information. Note that some of our terms differ slightly from [1]. The act of formalizing a data structure has clarified some of our earlier ideas.

Graphical representation

One strength of the policy graph is that the structure can be easily visualized. For each node in the graph, we can draw a picture like the following.

node

Here, x is the incoming state variable, x' is the outgoing state variable, ω is the random variable observed before making a decision, u is the control variable, Tᵢ is transition function, and Cᵢ is the stage objective. πᵢ is the decision rule, which maps the incoming state variable x and realization of the random variable ω to a feasible control u. (The set of feasible controls u ∈ Uᵢ(x, ω) is not shown.)

From this basic building block, we can construct an arbitrary policy graph. Our example two-stage stochastic program can be visualized as follows:

2sp

Here, the first stage is deterministic, then there is a second stage in which the decision is taken after observing the uncertainty.

We encourage you to read the paper [1] which outlines the full complexity of problems that can be represented, including problems with Markovian structure and infinite horizon problems (that is, cyclic policy graphs).

Problem in StochOptFormat

Encoded in StochOptFormat, the newsvendor problem becomes:

{
  "author": "Oscar Dowson",
  "name": "newsvendor",
  "date": "2023-05-02",
  "description": "A StochOptFormat implementation of the classical two-stage newsvendor problem.",
  "version": {"major": 1, "minor": 0},
  "root": {
    "state_variables": {"x": 0.0},
    "successors": {"first_stage": 1.0}
  },
  "nodes": {
    "first_stage": {
      "subproblem": "first_stage_subproblem",
      "successors": {"second_stage": 1.0}
    },
    "second_stage": {
      "subproblem": "second_stage_subproblem",
      "realizations": [
        {"probability": 0.4, "support": {"d": 10.0}},
        {"probability": 0.6, "support": {"d": 14.0}}
      ]
    }
  },
  "subproblems": {
    "first_stage_subproblem": {
      "state_variables": {
        "x": {"in": "x_in", "out": "x_out"}
      },
      "subproblem": {
        "version": {"major": 1, "minor": 2},
        "variables": [{"name": "x_in"}, {"name": "x_out"}],
        "objective": {
          "sense": "max",
          "function": {
            "type": "ScalarAffineFunction",
            "terms": [{"variable": "x_out", "coefficient": -1.0}],
            "constant": 0.0
          }
        },
        "constraints": [{
          "function": {"type": "Variable", "name": "x_out"},
          "set": {"type": "GreaterThan", "lower": 0.0}
        }]
      }
    },
    "second_stage_subproblem": {
      "state_variables": {
        "x": {"in": "x_in", "out": "x_out"}
      },
      "random_variables": ["d"],
      "subproblem": {
        "version": {"major": 1, "minor": 2},
        "variables": [
          {"name": "x_in"}, {"name": "x_out"}, {"name": "u"}, {"name": "d"}
        ],
        "objective": {
          "sense": "max",
          "function": {
            "type": "ScalarAffineFunction",
            "terms": [{"variable": "u", "coefficient": 1.5}],
            "constant": 0.0
          }
        },
        "constraints": [{
          "function": {
            "type": "ScalarAffineFunction",
            "terms": [
              {"variable": "u", "coefficient": 1.0},
              {"variable": "x_in", "coefficient": -1.0}
            ],
            "constant": 0.0
          },
          "set": {"type": "LessThan", "upper": 0.0}
        }, {
          "function": {
            "type": "ScalarAffineFunction",
            "terms": [
              {"variable": "u", "coefficient": 1.0},
              {"variable": "d", "coefficient": -1.0}
            ],
            "constant": 0.0
          },
          "set": {"type": "LessThan", "upper": 0.0}
        }, {
          "function": {"type": "Variable", "name": "u"},
          "set": {"type": "GreaterThan", "lower": 0.0}
        }]
      }
    }
  },
  "validation_scenarios": [
    [
      {"node": "first_stage"},
      {"node": "second_stage", "support": {"d": 10.0}}
    ], [
      {"node": "first_stage"},
      {"node": "second_stage", "support": {"d": 14.0}}
    ], [
      {"node": "first_stage"},
      {"node": "second_stage", "support": {"d": 9.0}}
    ]
  ]
}

Explanation

A StochOptFormat file is a JSON document. The problem is stored as a single JSON object. JSON objects are key-value mappings enclosed by curly braces.

The file begins with four self-explanatory optional metadata keys: name::String, author::String, date::String, and description::String.

Note: In the following, name::String means that the key of an object is name and the value should be of type String. ::List{Object} means that the type is a List, and elements of the list are Objects.

After the optional metadata keys, there are four required keys:

There is also an optional key:

Testing a policy is a larger topic, so we expand on it in the next section, Problems, policies, and algorithms.

Problems, policies, and algorithms

Now that we know how problems are represented in StochOptFormat, we need to introduce some additional vocabulary.

Evaluating the policy

Comparing two solutions to a determinstic optimization problem is simple: check the feasibility of each solution, compare objective values, and possibly compare computation time.

In contrast, comparing two policies is not simple. First, a policy produces a distribution of outcomes, so ranking two policies requires a user-provided risk measure based on their risk preference. Moreover, two users may have different risk preferences, so there is no uniquely optimal policy.

Second, in many cases the policy is an infinite dimensional object, and the set of scenarios over which it should be evaluated is so large as to be intractable.

To overcome these two issues, we evaluate the policy by means of an out-of-sample simulation on a finite discrete set of scenarios provided in the validation_scenarios key of a StochOptFormat file.

Solution algorithms should evaluate their policy on each of these scenarios and report the following for each node in each scenario:

Solutions should be outputted to a JSON file that conforms to the schema available at https://odow.github.io/StochOptFormat/versions/sof-result.schema.json.

Most notably, the result file must include the SHA-256 checksum of the problem file used to generate the policy to ensure that the two files can be linked.

Evaluating the solution on a finite list of scenarios solves the intractability problem, but it does not solve the user’s risk perference problem. However, with the above mentioned report, it is possible to evaluate multiple metrics of the resulting policy, such as expected objective values, and various quantiles.

FAQ

Implementations

References

[1] Dowson, O. (2020). The policy graph decomposition of multistage stochastic programming problems. Networks, 71(1), 3-23. doi: 10.1002/net.21932 [preprint]

[2] Legat, B., Dowson, O., Garcia, J., Lubin, M. (2022). MathOptInterface: a data structure for mathematical optimization problems. INFORMS Journal on Computing. 34(2), 671–1304. [preprint] [repository]

[3] Fourer, R., Gassmann, H.I., Ma, J. and Martin, R.K. (2009). An XML-based schema for stochastic programs. Ann Oper Res, 166, 313-337. doi: 10.1007/s10479-008-0419-x

[4] Gassmann, H.I. and Kristjánsson, B. (2008). The SMPS format explained. IMA Journal of Management Mathematics, 19(4), 347-377. doi: 10.1093/imaman/dpm007

[5] Gassmann, H.I., Ma, J. and Martin, R.K. (2011). Instance Formats for Mathematical Optimization Models. In Wiley Encyclopedia of Operations Research and Management Science (eds J.J. Cochran, L.A. Cox, P. Keskinocak, J.P. Kharoufeh and J.C. Smith). doi: 10.1002/9780470400531.eorms0411

This site is open source. Improve this page.