AdmmWrapper

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

An example of usage is given below.

Usage

The driver (in the example distr_admm_cylinders.py) calls admmWrapper.py, using the model provided by the model file (in the example examples.distr.distr.py). The file admmWrapper.py returns variable probabilities that can be used in the driver to create the PH (or APH) object which will solve the subproblems in a parallel way, insuring that merging conditions are respected.

Data needed in the driver

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

distr_data.scenario_creator(scenario_name)

Creates the model, which should include the consensus variables. However, this function should not create any tree.

Args:

scenario_name (str): the name of the 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:

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

• all_scenario_names (list of str): the subproblem names

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

  distr_data.scenario_denouement()

  Args:

  rank (int): rank in the cylinder

  scenario_name (str): name of the scenario

  scenario (Pyomo ConcreteModel): the instantiated model

Note

Subproblems will be represented in mpi-sppy by scenarios. Consensus variables ensure the problem constraints are respected, they are represented in mpi-sppy by non-anticipative variables. The following terms are associated: subproblems = scenarios (= regions in the example), and nonants = consensus-vars (=flow among regions in the example)

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

consensus_vars (dictionary):

• Keys are the subproblems

• Values are the list of consensus variables

Note

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

Using the config system

In addition to the previously presented data, the driver also requires arguments to create the PH Model and solve it. Some arguments may be passed to the user via config, but the cylinders need to be added.

Direct solver of the extensive form

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 admmWrapper. It has the advantage of requiring the same arguments as distr_admm_cylinders because both solve the extensive form.

This method offers a verification for small instances, but is slower than admmWrapper as it doesn’t decompose the problem.

Note

admmWrapper doesn’t collect yet instanciation time.

Distribution example

examples.distr.distr.py is an example of model creator in admmWrapper for a (linear) inter-region minimal cost distribution problem. 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 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.distr.distr.inter_arcs_adder is to do that.

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.

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.

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

Create an arcs formulation of network flow

Parameters:

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

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

Returns:

the instantiated model

Return type:

model (Pyomo ConcreteModel)

Transforming data for the driver

The driver requires five elements given by the model: all_scenario_names, scenario_creator, scenario_creator_kwargs, inparser_adder and consensus_vars.

all_scenario_names (see above) is given by scenario_names_creator

scenario_creator is created thanks to the previous functions.

distr.scenario_creator(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 to root nodes, as it is done in admmWrapper.

Parameters:

• scenario_name (str) – the name of the scenario that will be created. Here is of the shape f”Region{i}” with 1<=i<=num_scens

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

Returns:

the instantiated model

Return type:

Pyomo ConcreteModel

The dictionary scenario_creator_kwargs is created with

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

Parameters:

cfg (config) – specifications for the problem. We only look at the number of scenarios

Returns:

the kwargs that are used in distr.scenario_creator, here {“num_scens”: num_scens}

Return type:

dict (str)

The function inparser_adder requires the user to give num_scens (the number of regions) during the configuration.

distr.inparser_adder(cfg)

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

distr.consensus_vars_creator(num_scens, inter_region_dict, all_scenario_names)

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

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

Parameters:

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

Returns:

dictionary which keys are the regions and values are the list of consensus variables present in the region

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 distr, because the changes for consensus-vars are neglectible. However, in general, this file may be difficultly adapted and inefficient.

• distr_ef.py

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