SequentialDecomposition

(class from pyomo.network.decomposition)

class pyomo.network.decomposition.SequentialDecomposition(**kwds)

Bases: FOQUSGraph

A sequential decomposition tool for Pyomo Network models

The following parameters can be set upon construction of this class or via the options attribute.

Parameters:

• graph (MultiDiGraph) –

  A networkx graph representing the model to be solved.

  default=None (will compute it)

• tear_set (list) –

  A list of indexes representing edges to be torn. Can be set with a list of edge tuples via set_tear_set.

  default=None (will compute it)

• select_tear_method (str) –

  Which method to use to select a tear set, either “mip” or “heuristic”.

  default=”mip”

• run_first_pass (bool) –

  Boolean indicating whether or not to run through network before running the tear stream convergence procedure.

  default=True

• solve_tears (bool) –

  Boolean indicating whether or not to run iterations to converge tear streams.

  default=True

• guesses (ComponentMap) –

  ComponentMap of guesses to use for first pass (see set_guesses_for method).

  default=ComponentMap()

• default_guess (float) –

  Value to use if a free variable has no guess.

  default=None

• almost_equal_tol (float) –

  Difference below which numbers are considered equal when checking port value agreement.

  default=1.0E-8

• log_info (bool) –

  Set logger level to INFO during run.

  default=False

• tear_method (str) –

  Method to use for converging tear streams, either “Direct” or “Wegstein”.

  default=”Direct”

• iterLim (int) –

  Limit on the number of tear iterations.

  default=40

• tol (float) –

  Tolerance at which to stop tear iterations.

  default=1.0E-5

• tol_type (str) –

  Type of tolerance value, either “abs” (absolute) or “rel” (relative to current value).

  default=”abs”

• report_diffs (bool) –

  Report the matrix of differences across tear streams for every iteration.

  default=False

• accel_min (float) –

  Min value for Wegstein acceleration factor.

  default=-5

• accel_max (float) –

  Max value for Wegstein acceleration factor.

  default=0

• tear_solver (str) –

  Name of solver to use for select_tear_mip.

  default=”cplex”

• tear_solver_io (str) –

  Solver IO keyword for the above solver.

  default=None

• tear_solver_options (dict) –

  Keyword options to pass to solve method.

  default={}

__init__(**kwds)

Pass kwds to update the options attribute after setting defaults

Methods

__init__(**kwds)	Pass kwds to update the options attribute after setting defaults
adj_lists(G[, excludeEdges, nodes, multi])	Returns an adjacency list and a reverse adjacency list of node indexes for a MultiDiGraph.
all_cycles(G)	This function finds all the cycles in a directed graph.
arc_to_edge(G)	Returns a mapping from arcs to edges for a graph
cacher(key, fcn, *args)
calculation_order(G[, roots, nodes])	Rely on tree_order to return a calculation order of nodes
check_tear_set(G, tset)	Check whether the specified tear streams are sufficient.
check_value_fix(port, var, default, fixed, ...)	Try to fix the var at its current value or the default, else error
combine_and_fix(port, name, obj, evars, fixed)	For an extensive port member, combine the values of all expanded variables and fix the port member at their sum.
compute_err(svals, dvals, tol_type)	Compute the diff between svals and dvals for the given tol_type
create_graph(model)	Returns a networkx MultiDiGraph of a Pyomo network model
cycle_edge_matrix(G)	Return a cycle-edge incidence matrix, a list of list of nodes in each cycle, and a list of list of edge indexes in each cycle.
edge_to_idx(G)	Returns a mapping from edges to indexes for a graph
fixed_inputs()
generate_first_x(G, tears)
generate_gofx(G, tears)
idx_to_edge(G)	Returns a mapping from indexes to edges for a graph
idx_to_node(G)	Returns a mapping from indexes to nodes for a graph
indexes_to_arcs(G, lst)	Converts a list of edge indexes to the corresponding Arcs
load_guesses(guesses, port, fixed)
load_values(port, default, fixed, use_guesses)
node_to_idx(G)	Returns a mapping from nodes to indexes for a graph
pass_edges(G, edges)	Call pass values for a list of edge indexes
pass_single_value(port, name, member, val, fixed)	Fix the value of the port member and add it to the fixed set.
pass_tear_direct(G, tears)	Pass values across all tears in the given tear set
pass_tear_wegstein(G, tears, x)	Set the destination value of all tear edges to the corresponding value in the numpy array x.
pass_values(arc, fixed_inputs)	Pass the values from one unit to the next, recording only those that were not already fixed in the provided dict that maps blocks to sets.
run(model, function)	Compute a Pyomo Network model using sequential decomposition
run_order(G, order, function[, ignore, ...])	Run computations in the order provided by calling the function
scc_calculation_order(sccNodes, ie, oe)	This determines the order in which to do calculations for strongly connected components.
scc_collect(G[, excludeEdges])	This is an algorithm for finding strongly connected components (SCCs) in a graph.
select_tear_heuristic(G)	This finds optimal sets of tear edges based on two criteria.
select_tear_mip(G, solver[, solver_io, ...])	This finds optimal sets of tear edges based on two criteria.
select_tear_mip_model(G)	Generate a model for selecting tears from the given graph
set_guesses_for(port, guesses)	Set the guesses for the given port
set_tear_set(tset)	Set a custom tear set to be used when running the decomposition
solve_tear_direct(G, order, function, tears, ...)	Use direct substitution to solve tears.
solve_tear_wegstein(G, order, function, ...)	Use Wegstein to solve tears.
source_dest_peer(arc, name[, index])	Return the object that is the peer to the source port's member.
sub_graph_edges(G, nodes)	This function returns a list of edge indexes that are included in a subgraph given by a list of nodes.
tear_diff_direct(G, tears)	Returns numpy arrays of values for src and dest members for all edges in the tears list of edge indexes.
tear_set(G)
tear_set_arcs(G[, method])	Call the specified tear selection method and return a list of arcs representing the selected tear edges.
tear_upper_bound(G)	This function quickly finds a sub-optimal set of tear edges.
tree_order(adj, adjR[, roots])	This function determines the ordering of nodes in a directed tree.

Member Documentation

adj_lists(G, excludeEdges=None, nodes=None, multi=False)

Returns an adjacency list and a reverse adjacency list of node indexes for a MultiDiGraph.

Parameters:

• G – A networkx MultiDiGraph

• excludeEdges – List of edge indexes to ignore when considering neighbors

• nodes – List of nodes to form the adjacencies from

• multi – If True, adjacency lists will contains tuples of (node, key) for every edge between two nodes

Returns:

• i2n – Map from index to node for all nodes included in nodes

• adj – Adjacency list of successor indexes

• adjR – Reverse adjacency list of predecessor indexes

all_cycles(G)

This function finds all the cycles in a directed graph. The algorithm is based on Tarjan 1973 Enumeration of the elementary circuits of a directed graph, SIAM J. Comput. v3 n2 1973.

Returns:

• cycleNodes – List of lists of nodes in each cycle

• cycleEdges – List of lists of edge indexes in each cycle

arc_to_edge(G)

Returns a mapping from arcs to edges for a graph

calculation_order(G, roots=None, nodes=None)

Rely on tree_order to return a calculation order of nodes

Parameters:

• roots – List of nodes to consider as tree roots, if None then the actual roots are used

• nodes – Subset of nodes to consider in the tree, if None then all nodes are used

check_tear_set(G, tset)

Check whether the specified tear streams are sufficient. If the graph minus the tear edges is not a tree then the tear set is not sufficient to solve the graph.

check_value_fix(port, var, default, fixed, use_guesses, extensive=False)

Try to fix the var at its current value or the default, else error

combine_and_fix(port, name, obj, evars, fixed)

For an extensive port member, combine the values of all expanded variables and fix the port member at their sum. Assumes that all expanded variables are fixed.

compute_err(svals, dvals, tol_type)

Compute the diff between svals and dvals for the given tol_type

create_graph(model)

Returns a networkx MultiDiGraph of a Pyomo network model

The nodes are units and the edges follow Pyomo Arc objects. Nodes that get added to the graph are determined by the parent blocks of the source and destination Ports of every Arc in the model. Edges are added for each Arc using the direction specified by source and destination. All Arcs in the model will be used whether or not they are active (since this needs to be done after expansion), and they all need to be directed.

cycle_edge_matrix(G)

Return a cycle-edge incidence matrix, a list of list of nodes in each cycle, and a list of list of edge indexes in each cycle.

edge_to_idx(G)

Returns a mapping from edges to indexes for a graph

idx_to_edge(G)

Returns a mapping from indexes to edges for a graph

idx_to_node(G)

Returns a mapping from indexes to nodes for a graph

indexes_to_arcs(G, lst)

Converts a list of edge indexes to the corresponding Arcs

Parameters:

• G – A networkx graph corresponding to lst

• lst – A list of edge indexes to convert to tuples

Returns:

A list of arcs

node_to_idx(G)

Returns a mapping from nodes to indexes for a graph

pass_edges(G, edges)

Call pass values for a list of edge indexes

pass_single_value(port, name, member, val, fixed)

Fix the value of the port member and add it to the fixed set. If the member is an expression, appropriately fix the value of its free variable. Error if the member is already fixed but different from val, or if the member has more than one free variable.”

pass_tear_direct(G, tears)

Pass values across all tears in the given tear set

pass_tear_wegstein(G, tears, x)

Set the destination value of all tear edges to the corresponding value in the numpy array x.

pass_values(arc, fixed_inputs)

Pass the values from one unit to the next, recording only those that were not already fixed in the provided dict that maps blocks to sets.

run(model, function)

Compute a Pyomo Network model using sequential decomposition

Parameters:

• model – A Pyomo model

• function – A function to be called on each block/node in the network

run_order(G, order, function, ignore=None, use_guesses=False)

Run computations in the order provided by calling the function

Parameters:

• G – A networkx graph corresponding to order

• order – The order in which to run each node in the graph

• function – The function to be called on each block/node

• ignore – Edge indexes to ignore when passing values

• use_guesses – If True, will check the guesses dict when fixing free variables before calling function

scc_calculation_order(sccNodes, ie, oe)

This determines the order in which to do calculations for strongly connected components. It is used to help determine the most efficient order to solve tear streams to prevent extra iterations. This just makes an adjacency list with the SCCs as nodes and calls the tree order function.

Parameters:

• sccNodes – List of lists of nodes in each SCC

• ie – List of lists of in edge indexes to SCCs

• oe – List of lists of out edge indexes to SCCs

scc_collect(G, excludeEdges=None)

This is an algorithm for finding strongly connected components (SCCs) in a graph. It is based on Tarjan. 1972 Depth-First Search and Linear Graph Algorithms, SIAM J. Comput. v1 no. 2 1972

Returns:

• sccNodes – List of lists of nodes in each SCC

• sccEdges – List of lists of edge indexes in each SCC

• sccOrder – List of lists for order in which to calculate SCCs

• outEdges – List of lists of edge indexes leaving the SCC

select_tear_heuristic(G)

This finds optimal sets of tear edges based on two criteria. The primary objective is to minimize the maximum number of times any cycle is broken. The secondary criteria is to minimize the number of tears.

This function uses a branch and bound type approach.

Returns:

• tsets – List of lists of tear sets. All the tear sets returned are equally good. There are often a very large number of equally good tear sets.

• upperbound_loop – The max number of times any single loop is torn

• upperbound_total – The total number of loops

Improvements for the future

I think I can improve the efficiency of this, but it is good enough for now. Here are some ideas for improvement:

1. Reduce the number of redundant solutions. It is possible to find tears sets [1,2] and [2,1]. I eliminate redundant solutions from the results, but they can occur and it reduces efficiency.

2. Look at strongly connected components instead of whole graph. This would cut back on the size of graph we are looking at. The flowsheets are rarely one strongly connected component.

3. When you add an edge to a tear set you could reduce the size of the problem in the branch by only looking at strongly connected components with that edge removed.

4. This returns all equally good optimal tear sets. That may not really be necessary. For very large flowsheets, there could be an extremely large number of optimal tear edge sets.

select_tear_mip(G, solver, solver_io=None, solver_options={})

This finds optimal sets of tear edges based on two criteria. The primary objective is to minimize the maximum number of times any cycle is broken. The secondary criteria is to minimize the number of tears.

This function creates a MIP problem in Pyomo with a doubly weighted objective and solves it with the solver arguments.

select_tear_mip_model(G)

Generate a model for selecting tears from the given graph

Returns:

• model

• bin_list – A list of the binary variables representing each edge, indexed by the edge index of the graph

set_guesses_for(port, guesses)

Set the guesses for the given port

These guesses will be checked for all free variables that are encountered during the first pass run. If a free variable has no guess, its current value will be used. If its current value is None, the default_guess option will be used. If that is None, an error will be raised.

All port variables that are downstream of a non-tear edge will already be fixed. If there is a guess for a fixed variable, it will be silently ignored.

The guesses should be a dict that maps the following:

Port Member Name -> Value

Or, for indexed members, multiple dicts that map:

Port Member Name -> Index -> Value

For extensive members, “Value” must be a list of tuples of the form (arc, value) to guess a value for the expanded variable of the specified arc. However, if the arc connecting this port is a 1-to-1 arc with its peer, then there will be no expanded variable for the single arc, so a regular “Value” should be provided.

This dict cannot be used to pass guesses for variables within expression type members. Guesses for those variables must be assigned to the variable’s current value before calling run.

While this method makes things more convenient, all it does is:

self.options[“guesses”][port] = guesses

set_tear_set(tset)

Set a custom tear set to be used when running the decomposition

The procedure will use this custom tear set instead of finding its own, thus it can save some time. Additionally, this will be useful for knowing which edges will need guesses.

Parameters:

tset – A list of Arcs representing edges to tear

While this method makes things more convenient, all it does is:

self.options[“tear_set”] = tset

solve_tear_direct(G, order, function, tears, outEdges, iterLim, tol, tol_type, report_diffs)

Use direct substitution to solve tears. If multiple tears are given they are solved simultaneously.

Parameters:

• order – List of lists of order in which to calculate nodes

• tears – List of tear edge indexes

• iterLim – Limit on the number of iterations to run

• tol – Tolerance at which iteration can be stopped

Returns:

List of lists of diff history, differences between input and output values at each iteration

Return type:

list

solve_tear_wegstein(G, order, function, tears, outEdges, iterLim, tol, tol_type, report_diffs, accel_min, accel_max)

Use Wegstein to solve tears. If multiple tears are given they are solved simultaneously.

Parameters:

• order – List of lists of order in which to calculate nodes

• tears – List of tear edge indexes

• iterLim – Limit on the number of iterations to run

• tol – Tolerance at which iteration can be stopped

• accel_min – Minimum value for Wegstein acceleration factor

• accel_max – Maximum value for Wegstein acceleration factor

• tol_type – Type of tolerance value, either “abs” (absolute) or “rel” (relative to current value)

Returns:

List of lists of diff history, differences between input and output values at each iteration

Return type:

list

source_dest_peer(arc, name, index=None)

Return the object that is the peer to the source port’s member. This is either the destination port’s member, or the variable on the arc’s expanded block for Extensive properties. This will return the appropriate index of the peer.

sub_graph_edges(G, nodes)

This function returns a list of edge indexes that are included in a subgraph given by a list of nodes.

Returns:

• edges – List of edge indexes in the subgraph

• inEdges – List of edge indexes starting outside the subgraph and ending inside

• outEdges – List of edge indexes starting inside the subgraph and ending outside

tear_diff_direct(G, tears)

Returns numpy arrays of values for src and dest members for all edges in the tears list of edge indexes.

tear_set_arcs(G, method='mip', **kwds)

Call the specified tear selection method and return a list of arcs representing the selected tear edges.

The kwds will be passed to the method.

tear_upper_bound(G)

This function quickly finds a sub-optimal set of tear edges. This serves as an initial upperbound when looking for an optimal tear set. Having an initial upper bound improves efficiency.

This works by constructing a search tree and just makes a tear set out of all the back edges.

tree_order(adj, adjR, roots=None)

This function determines the ordering of nodes in a directed tree. This is a generic function that can operate on any given tree represented by the adjaceny and reverse adjacency lists. If the adjacency list does not represent a tree the results are not valid.

In the returned order, it is sometimes possible for more than one node to be calculated at once. So a list of lists is returned by this function. These represent a bredth first search order of the tree. Following the order, all nodes that lead to a particular node will be visited before it.

Parameters:

• adj – An adjeceny list for a directed tree. This uses generic integer node indexes, not node names from the graph itself. This allows this to be used on sub-graphs and graps of components more easily.

• adjR – The reverse adjacency list coresponing to adj

• roots – List of node indexes to start from. These do not need to be the root nodes of the tree, in some cases like when a node changes the changes may only affect nodes reachable in the tree from the changed node, in the case that roots are supplied not all the nodes in the tree may appear in the ordering. If no roots are supplied, the roots of the tree are used.