StochAdmmWrapper

Decomposition using consensus ADMM can be used to allow paral- lelization efficiencies or for reasons related to information security. In either case, the input data may be uncertain and we give a decomposi- tion algorithm based on Progressive Hedging.

A technical report is available at ool < https://optimization-online.org/2024/08/consensus-admm-under-uncertainty >

StochAdmmWrapper uses progressive hedging implemented in mpi-sppy to solve a stochastic problem by breaking them into subproblems.

It is similar in many points to admmWrapper, but the key differences are the labelling of scenarios, the definition of consensus_vars and of scenario_creator.

An example of usage is given below. At the time of this writing, in order to use the system you should probably make your own copy of the driver file and the module file for this example and then modify them for this problem. Note: this particular example makes use a helper module to process data (mpisppy.tests.examples.distr.distr_data). There is no requirement to do that, it was just helpful for this example.

Example Driver file

The driver stoch_distr_admm_cylinders.py calls stoch_admmWrapper.py, using the model provided by the model file (in the example examples.stoch_distr.stoch_distr.py). Under the hood (so to speak), the file stoch_admmWrapper.py returns data structures (making use of so-called “variable probabilities”) that can be used in the driver to create the PH (or APH) object which will solve the subproblems in the usual, parallel way, while ensuring that consensus constraints are respected as well as non-anticipativity constraints.

Functions needed in the module by the driver

Various functions are supplied by the module file: stoch_distr.py, which is imported by the driver.

The driver file requires the scenario_creator function which creates the model for each scenario.

distr_data.scenario_creator(admm_stoch_subproblem_scenario_name)

Creates the model, which should include the consensus variables. However, the scenario_creator function shouldn’t include the consensus variables in the list of stochastic variables. (E.g., for a two-stage problem, they should not be in the list supplied to attach_root_node. The consensus variables

are supplied to admm_wrapper in the driver in a list passed to the stoch_admmWrapper constructor.)

Therefore, for multi-stage stochastics, only the stochastic tree as it would be represented without the admm decomposition needs to be created by the scenario_creator function.

Args:

admm_stoch_subproblem_scenario_name (str): the name of the extended scenario that will be created.

Returns:

Pyomo ConcreteModel: the instantiated model

The driver file also requires helper arguments that are used in mpi-sppy. They are detailed in helper_functions and in the example below. Here is a summary of helper functions:

• scenario_creator_kwargs (dict[str]): key words arguments needed in scenario_creator

• A function that is called at termination in some modules (e.g. PH)

  distr_data.scenario_denouement()

  Args:

  rank (int): rank in the cylinder

  admm_stoch_subproblem_scenario_name (str): name of the extended scenario

  scenario (Pyomo ConcreteModel): the instantiated model

• stoch_scenario_names, admm_subproblem_names and all_admm_stoch_subproblem_scenario_names (lists of str)

The driver also needs global information to link the subproblems. It should be provided in consensus_vars.

Two types of consensus variables should be added: those that were already appearing as non-anticipative variables (with their stage), and consensus variables linking the ADMM subproblems with a stage n if the stochastic problem is orginally a n-stage problem.

consensus_vars (dictionary):

• Keys are the subproblems

• Values are thelist of pairs (consensus_variable_name (str), stage (int))

Note

Every variable in consensus_vars[subproblem] should also appear as a variable in the pyomo model of the subproblem.

Labelling the scenarios

In StochAdmmWrapper, stochastic_scenarios precedes the decomposition into subproblems. These scenarios are then decomposed in each admm_subproblem to create an admm_stoch_subproblem_scenario, also called extended scenario.

For instance, in the stochastic distribution example, in a stochastic_scenario: StochasticScenario1, in the admm_subproblem: Region2, the admm_stoch_subproblem_scenario is ADMM_STOCH_Region2_StochasticScenario1.

All these names are required in the driver file stoch_distr_admm_cylinders.py to create the wrapper file stoch_admmWrapper.py. The function split_admm_stoch_subproblem_scenario_name is also needed to obtain the admm_subproblem and stochastic_scenarios from the admm_stoch_subproblem_scenario.

Direct solution of the extensive form

stoch_distr_ef.py can be used as a verification or debugging tool for small instances. It directly solves the extensive form using the wrapper scenario_creator from stoch_admmWrapper. It has the advantage of requiring the same arguments as stoch_distr_admm_cylinders because both solve the extensive form.

This method offers a verification for small instances, but doesn’t decompose the problem.

Note

stoch_admmWrapper doesn’t collect yet instanciation time.

Stochastic distribution example

This example consists in solving a stochastic distribution model by decomposing it into regions and ensuring the flow balance with consensus variables in PH.

The model is stochastic because in a first stage the production at factory nodes need to be determined, it is the originale non-anticipative variable, later the stochastic parameter of the production loss is known. Finally everything else can be determined.

To decompose it in ADMM subproblems, an extra stage is added in stoch_admmWrapper.py.

examples.stoch_distr.stoch_distr.py is an example of model creator in stoch_admmWrapper for a (linear) inter-region minimal cost distribution problem. stoch_distr_admm_cylinders.py is the driver.

Original data dictionaries

The data is created in distr_data.py. Some models are hardwired for 2, 3 and 4 regions. Other models are created pseudo-randomly thanks to parameters defined in data_params.json.

In the example the inter_region_dict_creator (or scalable_inter_region_dict_creator) creates the inter-region information.

distr_data.inter_region_dict_creator(num_scens)

Creates the oriented arcs between the regions, with their capacities and costs.

This dictionary represents the inter-region constraints and flows. It indicates where to add dummy nodes.

Parameters:

num_scens (int) – select the number of scenarios (regions) wanted

Returns:

Each arc is presented as a pair (source, target) with source and target containing (scenario_name, node_name)

The arcs are used as keys for the dictionaries of costs and capacities

Return type:

dict

The region_dict_creator (or scalable_region_dict_creator) creates the information specific to a region, regardless of the other regions.

distr_data.region_dict_creator(scenario_name)

Create a scenario for the inter-region max profit distribution example.

The convention for node names is:

Symbol + number of the region (+ _ + number of the example if needed), with symbols DC for distribution centers, F for factory nodes, B for buyer nodes.

For instance: F3_1 is the 1st factory node of region 3.

Parameters:

scenario_name (str) – Name of the scenario to construct.

Returns:

contains all the information in the given region to create the model. It is composed of:

”nodes” (list of str): all the nodes. The following subsets are also nodes: “factory nodes”, “buyer nodes”, “distribution center nodes”,

”arcs” (list of 2 tuples of str) : (node, node) pairs

”supply” (dict[n] of float): supply; keys are nodes (negative for demand)

”production costs” (dict of float): at each factory node

”revenues” (dict of float): at each buyer node

”flow costs” (dict[a] of float) : costs per unit flow on each arc

”flow capacities” (dict[a] of floats) : upper bound capacities of each arc

Return type:

region_dict (dict)

Adapting the data to create the model

To solve the regions independantly we must make sure that the constraints (in our example flow balance) would still be respected if the models were merged. To impose this, consensus variables are introduced.

In our example a new consensus variable is the flow among regions. Indeed, in each regional model we introduce the inter-region arcs for which either the source or target is in the region to impose the flow balance rule inside the region. But at this stage, nothing ensures that the flow from DC1 to DC2 represented in Region 1 is the same as the flow from DC1 to DC2 represented in Region 2. That is why the flow flow["DC1DC2"] is a consensus variable in both regions: to ensure it is the same.

The purpose of examples.stoch_distr.stoch_distr.inter_arcs_adder is to do that.

stoch_distr.inter_arcs_adder(region_dict, inter_region_dict)

This function adds to the region_dict the inter-region arcs

Parameters:

• region_dict (dict) – dictionary for the current scenario

• inter_region_dict (dict) – dictionary of the inter-region relations

Returns:

This dictionary copies region_dict, completes the already existing fields of region_dict to represent the inter-region arcs and their capcities and costs

Return type:

local_dict (dict)

Note

In the example the cost of transport is chosen to be split equally in the region source and the region target. the only thing needed is that the sum of the costs is the original cost.

We here represent the flow problem with a directed graph. If, in addition to the flow from DC1 to DC2 represented by flow["DC1DC2"], a flow from DC2 to DC1 were to be authorized we would also have flow["DC2DC1"] in both regions.

Once the local_dict is created, the Pyomo model can be created thanks to min_cost_distr_problem.

stoch_distr.min_cost_distr_problem(local_dict, cfg, stoch_scenario_name, sense=ObjectiveSense.minimize, max_revenue=None)

Create an arcs formulation of network flow for the region and stochastic scenario considered.

Parameters:

• local_dict (dict) – dictionary representing a region including the inter region arcs

• () (cfg) – config argument used here for the random parameters

• stoch_scenario_name (str) – name of the stochastic scenario. In each region, the model is scenario dependant

• sense (=pyo.minimize) – we aim to minimize the cost, this should always be minimize

• max_revenue (float, opt) – higher than all the possible revenues, this value allows to add a penalty slack making sure that the optimal value of the new model is obtained with a 0 slack

Returns:

the instantiated model

Return type:

model (Pyomo ConcreteModel)

Transforming data for the driver

The driver requires elemnts given by the model.

all_admm_stoch_subproblem_scenario_names, split_admm_stoch_subproblem_scenario_name, admm_subproblem_names, stoch_scenario_names are explained above

scenario_creator is created thanks to the previous functions.

stoch_distr.scenario_creator(admm_stoch_subproblem_scenario_name, inter_region_dict=None, cfg=None, data_params=None, all_nodes_dict=None)

Creates the model, which should include the consensus variables.

However, this function shouldn’t attach the consensus variables for the admm subproblems as it is done in stoch_admmWrapper. Therefore, only the stochastic tree as it would be represented without the decomposition needs to be created.

Parameters:

• admm_stoch_subproblem_scenario_name (str) – the name given to the admm problem for the stochastic scenario.

• inter_region_dict (dict) – contains all the links between the regions

• num_scens (int) – number of scenarios (regions). Useful to create the corresponding inter-region dictionary

• scenario_creator (other parameters are key word arguments for)

Returns:

the instantiated model

Return type:

Pyomo ConcreteModel

The dictionary scenario_creator_kwargs is created with

stoch_distr.kw_creator(all_nodes_dict, cfg, inter_region_dict, data_params)

Parameters:

cfg (config) – specifications for the problem given on the command line

Returns:

the kwargs that are used in distr.scenario_creator, which are included in cfg.

Return type:

dict (str)

In this example the original model is a two-stage problem. Therefore it doesn’t require branching factors BFs. If the original model had more than two stages, branching factors would need to be added.

The function inparser_adder requires the user to give num_stoch_scens (the number of stochastic scenarios), num_admm_subproblems (the number of regions) during the configuration. Optional model specific config arguments are added:

• The stochastic parameters spm, cv and initial_seed for the Gaussian generation of the production loss stochastic.

• If scalable is used in the command line, a stochastic model with each region of “size” mnpr is generated

• ensure_xhat_feas is a boolean. If true, slacks are added to the distribution centers (with high penalty costs), so that the xhatter always finds a solution, which gives a best incumbent.

stoch_distr.inparser_adder(cfg)

Adding to the config argument, specific elements to our problems. In this case the numbers of stochastic scenarios and admm subproblems which are required + elements used for random number generation + possibility to scale

Parameters:

cfg (config) – specifications for the problem given on the command line

Contrary to the other helper functions, consensus_vars_creator is specific to stoch_admmWrapper. The function consensus_vars_creator creates the required consensus_vars dictionary.

stoch_distr.consensus_vars_creator(admm_subproblem_names, stoch_scenario_name, inter_region_dict=None, cfg=None, data_params=None, all_nodes_dict=None)

The following function creates the consensus variables dictionary thanks to the inter-region dictionary.

This dictionary has redundant information, but is useful for admmWrapper.

Parameters:

• admm_subproblem_names (list of str) – name of the admm subproblems (regions)

• stoch_scenario_name (str) – name of any stochastic_scenario, it is only used

• to (in this example to access the non anticipative variables (which are common)

• stage. (every stochastic scenario) and their)

• kwargs (opt) – necessary in this example to call the scenario creator

Returns:

dictionary which keys are the subproblems and values are the list of pairs (consensus_variable_name (str), stage (int)).

Return type:

dict

Understanding the driver

In the example the driver gets argument from the command line through the function _parse_args

distr_data._parse_args()

Gets argument from the command line and add them to a config argument. Some arguments are required.

Note

Some arguments, such as cfg.run_async and all the methods creating new cylinders not only need to be added in the _parse_args() method, but also need to be called later in the driver.

Non local solvers

The file globalmodel.py and distr_ef.py are used for debugging or learning. They don’t rely on ph or admm, they simply solve the problem without decomposition.

• globalmodel.py

  In globalmodel.py, global_dict_creator merges the data into a global dictionary thanks to the inter-region dictionary, without creating inter_region_arcs. Then model is created (as if there was only one region without arcs leaving it) and solved.

  However this file depends on the structure of the problem and doesn’t decompose the problems. Luckily in this example, the model creator is the same as in stoch_distr, because the changes for consensus-vars are neglectible. However, in general, this file may be difficultly adapted and inefficient.

• stoch_distr_ef.py

  As presented previously solves the extensive form. The arguments are the same as stoch_distr_admm_cylinders.py, the method doesn’t need to be adapted with the model.