example for concrete multi-stage model

[ibayer-ny]

Thanks for this great library!

I'm interested in modeling multi-stage problems as ConcreteModels so that I have full flexibility to modify
them in python.

Thanks to the examples I have been able to adjust newsvendor and farmer to my needs. However this are
only two-stage problems and I'm now stuck trying to convert the financial planning example to a direct model.

I have studied the docs but not everything is clear yet, an example for a concrete multi-stage model would help me a lot. Is there such a model in the examples that I overlooked or can someone share such an example?

Thanks

[ibayer-ny]

I was looking at the example from the pysp repo. :-/ I now found some examples that look relevant at mpi-sppy/examples.
The examples hydro and netdes seem to be very close to what I need. I'll try to use them as reference for converting the pysp financial planning example to a concrete mpi-sppy model.

[DLWoodruff]

The hydro example in mpi-sppy is multi-stage. Let me know if that helps. Dave

…

On Fri, May 21, 2021 at 2:31 AM ibayer-ny ***@***.***> wrote: Thanks for this great library! I'm interested in modeling multi-stage problems as ConcreteModels so that I have full flexibility to modify them in python. Thanks to the examples I have been able to adjust newsvendor and farmer to my needs. However this are only two-stage problems and I'm now stuck trying to convert the financial planning example to a direct model. I have studied the docs but not everything is clear yet, an example for a concrete multi-stage model would help me a lot. Is there such a model in the examples that I overlooked or can someone share such an example? Thanks — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#121>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AD4VTBH7NJSTOPWB7YPNPM3TOYSALANCNFSM45IZCC6Q> .

[ibayer-ny]

I finally had time to dig deeper. Yes, the hydro example is very helpful, thanks for the hint.
I'll keep the issue open a bit longer to report on my progress.

[ibayer-ny]

@DLWoodruff I'm a bit stuck at the moment. It would be great if you could give me an hint. :-)

Current Understanding: Scenario based EF optimization with mpi-sppy

The following illustrates on a abstract level my current understanding how stochastic programming problems can be solved with mpi-sppy. As a first step I only focus on the extended form (EF) representation that can be solved for simple and small problem with a standard pyomo solver.

• Each path from a square / leaf node to the root defines are scenario e.g. all blue nodes.
• Each scenario is a instance of the deterministic optimization problem.
• Each scenario occurs with a specific probability, which can be decomposed in a probability per node.

From a modeling and testing perspective it is very convenient to start with a single scenario setting. Without uncertainty we can solve and reason about a standard pyomo optimization problem of the following form:

def build_model(scenario):
    """scenario: Contains the realization of the random variables that we
       observe in this scenario."""

    model = pyo.ConcreteModel()
    # model specifc code goes here
    return model

model = build_model(scenario)
solve(model)

However, we are interested in a solution that is optimal in expectation across all scenarios.
We therefore need to create a problem instance that incorporates the full scenario tree. The mpi-sppy (sppy) library provides a few key functions to create the EF representation.

• ExtensiveForm(all_scenario_names, scenario_creator, all_nodenames,...)
  • Create an EF representation that can be optimized with ef.solve_extensive_form(tee=True).
• model._mpisppy_node_list(...)
  • Add a list of nodes [ScenarioNode] to the model that describe a specific scenario. The list represents a path from leaf to root, but excludes the leaf.
• scenario_tree.ScenarioNode(name, ..., parent_name)
  • Create a node in the scenario tree.
  • The key parameter describe:
    • The Nonanticipativity Constraints required for this node.
    • The node name name and parent_name are needed to position the node in the tree.

We now need to define the scenario_creator(...) function required by ExtensiveForm(...).

def scenario_creator(scenario_name, scenarios):
    model = build_model(scenarios[scenario_name])
    model._mpisppy_node_list = create_scenario_nodes(scenario_name, instance)
    return model

For readability and to simplify testing we can create a helper function to create the node list.

def create_scenario_nodes(name, instance):
    return [ScenarioNode(name='ROOT', ...), ScenarioNode(name='ROOT_0', ..., parent_name='ROOT'), ...]

Missing pieces

It seems that a very specific naming convention is required for the scenario and node names that I can't deduce from the sppy examples.

I found the following naming scheme in the pysp examples

set Nodes := RootNode 

             StockNode
             BondNode 

             StockStockNode
             StockBondNode
             BondStockNode
             BondBondNode

             StockStockStockNode
             StockStockBondNode
             StockBondStockNode
             StockBondBondNode

             BondStockStockNode
             BondStockBondNode
             BondBondStockNode
             BondBondBondNode ;

but I don't think this would be valid for sppy.

I found the following in the sppy docs https://mpi-sppy.readthedocs.io/en/latest/scenario_creator.html#scenario-creator-function

If there are other scenario tree nodes, their names, although strings, must either be a unique integer or end in a unique integer (e.g. “1” or “Node1”, etc.)

It would be really helpful to have a valid naming scheme example (scenario names and node names) for the financial planning problem (the diagram on top of this comment represents its scenario tree).

[ibayer-ny]

@bknueven Could you point me to the relevant library source files that could help me to understand the current naming conventions? I'll happy to provide a summary of my findings as reference for other users.

[ibayer-ny]

This seemed to work for me:

• ROOT is always used as prefix, node _1 -> ROOT_1.

[DLWoodruff]

I'm sorry I didn't respond earlier, for some reason I don't seem to get a notification of these issues.
Anyway, you seem to have figured out the node naming convention; however, you should know that a lot of work is being
done on multi-stage trees and there will be a new naming convention sometime next week. Luckily, it is almost the same: the only difference is that the leaf nodes will be included in the node list. We are also working to add support for unbalanced trees.

[ibayer-ny]

Thanks for the head up regarding the upcoming release. I'll make sure to update asap.

however, you should know that a lot of work is being
done on multi-stage trees and there will be a new naming convention sometime next week.

IMO adapting to the new naming convention is a cheap price to pay for better multi-stage support. :)

for some reason I don't seem to get a notification of these issues.

@DLWoodruff test ;)

[jialuw96]

@ibayer-ny Thank you for opening this issue. I found it very helpful. Are you willing to share the multi-stage example with concrete models you were working on?

@DLWoodruff @bknueven Have there been any updates to mpi-sppy about multi-stage problems during the last 12 months?

[bknueven]

One big change is mpi-sppy can now read a PySP-style model directly, including multistage. An example is here: https://github.com/Pyomo/mpi-sppy/blob/0.10/examples/hydro/hydro_cylinders_pysp.py.

A more minor change is we enabled the FWPH-spoke to work with multi-stage models. The release notes for 0.10 aren't a bad resource for this: https://github.com/Pyomo/mpi-sppy/releases/tag/0.10

[Edudiro]

@ibayer-ny Thank you for the nice summary for newcommers like me, would you mind sharing the financial investment example you worked on? I am currently trying to transform such setting into a battery dispatch optimization problem, but i am not sure it is doable.

@jialuw96 were you able to work out the multi-stage example?

[brunoks1]

@jialuw96 @ibayer-ny is any multistage example with a general description that we can easily reproduce?