Pyomo Interfaces

Utility functions and a utility class for interfacing Pyomo components with useful graph algorithms.

class pyomo.contrib.incidence_analysis.interface.IncidenceGraphInterface(model=None, active=True, include_inequality=True, **kwds)

An interface for applying graph algorithms to Pyomo variables and constraints

Parameters:

• model (Pyomo BlockData or PyNumero PyomoNLP, default None) – An object from which an incidence graph will be constructed.

• active (Bool, default True) – Whether only active constraints should be included in the incidence graph. Cannot be set to False if the model is provided as a PyomoNLP.

• include_fixed (Bool, default False) – Whether to include fixed variables in the incidence graph. Cannot be set to False if model is a PyomoNLP.

• include_inequality (Bool, default True) – Whether to include inequality constraints (those whose expressions are not instances of EqualityExpression) in the incidence graph. If a PyomoNLP is provided, setting to False uses the evaluate_jacobian_eq method instead of evaluate_jacobian rather than checking constraint expression types.

add_edge(variable, constraint)

Adds an edge between variable and constraint in the incidence graph

Parameters:

• variable (VarData) – A variable in the graph

• constraint (ConstraintData) – A constraint in the graph

block_triangularize(variables=None, constraints=None)

Compute an ordered partition of the provided variables and constraints such that their incidence matrix is block lower triangular

Subsets in the partition correspond to the strongly connected components of the bipartite incidence graph, projected with respect to a perfect matching.

Returns:

• var_partition (list of lists) – Partition of variables. The inner lists hold unindexed variables.

• con_partition (list of lists) – Partition of constraints. The inner lists hold unindexed constraints.

Example

>>> import pyomo.environ as pyo
>>> from pyomo.contrib.incidence_analysis import IncidenceGraphInterface
>>> m = pyo.ConcreteModel()
>>> m.x = pyo.Var([1, 2])
>>> m.eq1 = pyo.Constraint(expr=m.x[1]**2 == 7)
>>> m.eq2 = pyo.Constraint(expr=m.x[1]*m.x[2] == 3)
>>> igraph = IncidenceGraphInterface(m)
>>> vblocks, cblocks = igraph.block_triangularize()
>>> print([[v.name for v in vb] for vb in vblocks])
[['x[1]'], ['x[2]']]
>>> print([[c.name for c in cb] for cb in cblocks])
[['eq1'], ['eq2']]

Note

Breaking change in Pyomo 6.5.0

The pre-6.5.0 block_triangularize method returned maps from each variable or constraint to the index of its block in a block lower triangularization as the original intent of this function was to identify when variables do or don’t share a diagonal block in this partition. Since then, the dominant use case of block_triangularize has been to partition variables and constraints into these blocks and inspect or solve each block individually. A natural return type for this functionality is the ordered partition of variables and constraints, as lists of lists. This functionality was previously available via the get_diagonal_blocks method, which was confusing as it did not capture that the partition was the diagonal of a block triangularization (as opposed to diagonalization). The pre-6.5.0 functionality of block_triangularize is still available via the map_nodes_to_block_triangular_indices method.

property col_block_map

DEPRECATED.

Deprecated since version 6.5.0: The col_block_map attribute is deprecated and will be removed.

property con_index_map

DEPRECATED.

Deprecated since version 6.5.0: con_index_map is deprecated. Please use get_matrix_coord instead.

property constraints

The constraints participating in the incidence graph

dulmage_mendelsohn(variables=None, constraints=None)

Partition variables and constraints according to the Dulmage- Mendelsohn characterization of the incidence graph

Variables are partitioned into the following subsets:

• unmatched - Variables not matched in a particular maximum cardinality matching

• underconstrained - Variables that could possibly be unmatched in a maximum cardinality matching

• square - Variables in the well-constrained subsystem

• overconstrained - Variables matched with constraints that can possibly be unmatched

Constraints are partitioned into the following subsets:

• underconstrained - Constraints matched with variables that can possibly be unmatched

• square - Constraints in the well-constrained subsystem

• overconstrained - Constraints that can possibly be unmatched with a maximum cardinality matching

• unmatched - Constraints that were not matched in a particular maximum cardinality matching

While the Dulmage-Mendelsohn decomposition does not specify an order within any of these subsets, the order returned by this function preserves the maximum matching that is used to compute the decomposition. That is, zipping “corresponding” variable and constraint subsets yields pairs in this maximum matching. For example:

>>> igraph = IncidenceGraphInterface(model)
>>> var_dmpartition, con_dmpartition = igraph.dulmage_mendelsohn()
>>> vdmp = var_dmpartition
>>> cdmp = con_dmpartition
>>> matching = list(zip(
...     vdmp.underconstrained + vdmp.square + vdmp.overconstrained,
...     cdmp.underconstrained + cdmp.square + cdmp.overconstrained,
... ))
>>> # matching is a valid maximum matching of variables and constraints!

Returns:

• var_partition (ColPartition named tuple) – Partitions variables into square, underconstrained, overconstrained, and unmatched.

• con_partition (RowPartition named tuple) – Partitions constraints into square, underconstrained, overconstrained, and unmatched.

Example

>>> import pyomo.environ as pyo
>>> from pyomo.contrib.incidence_analysis import IncidenceGraphInterface
>>> m = pyo.ConcreteModel()
>>> m.x = pyo.Var([1, 2])
>>> m.eq1 = pyo.Constraint(expr=m.x[1]**2 == 7)
>>> m.eq2 = pyo.Constraint(expr=m.x[1]*m.x[2] == 3)
>>> m.eq3 = pyo.Constraint(expr=m.x[1] + 2*m.x[2] == 5)
>>> igraph = IncidenceGraphInterface(m)
>>> var_dmp, con_dmp = igraph.dulmage_mendelsohn()
>>> print([v.name for v in var_dmp.overconstrained])
['x[1]', 'x[2]']
>>> print([c.name for c in con_dmp.overconstrained])
['eq1', 'eq2']
>>> print([c.name for c in con_dmp.unmatched])
['eq3']

get_adjacent_to(component)

Return a list of components adjacent to the provided component in the cached bipartite incidence graph of variables and constraints

Parameters:

component (ComponentData) – The variable or constraint data object whose adjacent components are returned

Returns:

List of constraint or variable data objects adjacent to the provided component

Return type:

list of ComponentData

Example

>>> import pyomo.environ as pyo
>>> from pyomo.contrib.incidence_analysis import IncidenceGraphInterface
>>> m = pyo.ConcreteModel()
>>> m.x = pyo.Var([1, 2])
>>> m.eq1 = pyo.Constraint(expr=m.x[1]**2 == 7)
>>> m.eq2 = pyo.Constraint(expr=m.x[1]*m.x[2] == 3)
>>> m.eq3 = pyo.Constraint(expr=m.x[1] + 2*m.x[2] == 5)
>>> igraph = IncidenceGraphInterface(m)
>>> adj_to_x2 = igraph.get_adjacent_to(m.x[2])
>>> print([c.name for c in adj_to_x2])
['eq2', 'eq3']

get_connected_components(variables=None, constraints=None)

Partition variables and constraints into weakly connected components of the incidence graph

These correspond to diagonal blocks in a block diagonalization of the incidence matrix.

Returns:

• var_blocks (list of lists of variables) – Partition of variables into connected components

• con_blocks (list of lists of constraints) – Partition of constraints into corresponding connected components

get_diagonal_blocks(variables=None, constraints=None)

DEPRECATED.

Deprecated since version 6.5.0: IncidenceGraphInterface.get_diagonal_blocks is deprecated. Please use IncidenceGraphInterface.block_triangularize instead.

get_matrix_coord(component)

Return the row or column coordinate of the component in the incidence matrix of variables and constraints

Variables will return a column coordinate and constraints will return a row coordinate.

Parameters:

component (ComponentData) – Component whose coordinate to locate

Returns:

Column or row coordinate of the provided variable or constraint

Return type:

int

property incidence_matrix

The structural incidence matrix of variables and constraints.

Variables correspond to columns and constraints correspond to rows. All matrix entries have value 1.0.

map_nodes_to_block_triangular_indices(variables=None, constraints=None)

Map variables and constraints to indices of their diagonal blocks in a block lower triangular permutation

Returns:

• var_block_map (ComponentMap) – Map from variables to their diagonal blocks in a block triangularization

• con_block_map (ComponentMap) – Map from constraints to their diagonal blocks in a block triangularization

maximum_matching(variables=None, constraints=None)

Return a maximum cardinality matching of variables and constraints.

The matching maps constraints to their matched variables.

Returns:

A map from constraints to their matched variables.

Return type:

ComponentMap

property n_edges

The number of edges in the incidence graph, or the number of structural nonzeros in the incidence matrix

plot(variables=None, constraints=None, title=None, show=True)

Plot the bipartite incidence graph of variables and constraints

remove_nodes(nodes, constraints=None)

Removes the specified variables and constraints (columns and rows) from the cached incidence matrix.

This is a “projection” of the variable and constraint vectors, rather than something like a vertex elimination. For the puropse of this method, there is no need to distinguish between variables and constraints. However, we provide the “constraints” argument so a call signature similar to other methods in this class is still valid.

Parameters:

• nodes (list) – VarData or ConData objects whose columns or rows will be removed from the incidence matrix.

• constraints (list) – VarData or ConData objects whose columns or rows will be removed from the incidence matrix.

property row_block_map

DEPRECATED.

Deprecated since version 6.5.0: The row_block_map attribute is deprecated and will be removed.

subgraph(variables, constraints)

Extract a subgraph defined by the provided variables and constraints

Underlying data structures are copied, and constraints are not reinspected for incidence variables (the edges from this incidence graph are used).

Returns:

A new incidence graph containing only the specified variables and constraints, and the edges between pairs thereof.

Return type:

IncidenceGraphInterface

property var_index_map

DEPRECATED.

Deprecated since version 6.5.0: var_index_map is deprecated. Please use get_matrix_coord instead.

property variables

The variables participating in the incidence graph

pyomo.contrib.incidence_analysis.interface.extract_bipartite_subgraph(graph, nodes0, nodes1)

Return the bipartite subgraph of a graph.

Two lists of nodes to project onto must be provided. These will correspond to the “bipartite sets” in the subgraph. If the two sets provided have M and N nodes, the subgraph will have nodes 0 through M+N-1, with the first M corresponding to the first set provided and the last N corresponding to the second set.

Parameters:

• graph (NetworkX Graph) – The graph from which a subgraph is extracted

• nodes0 (list) – A list of nodes in the original graph that will form the first bipartite set of the projected graph (and have bipartite=0)

• nodes1 (list) – A list of nodes in the original graph that will form the second bipartite set of the projected graph (and have bipartite=1)

Returns:

subgraph – Graph containing integer nodes corresponding to positions in the provided lists, with edges where corresponding nodes are adjacent in the original graph.

Return type:

networkx.Graph

pyomo.contrib.incidence_analysis.interface.get_bipartite_incidence_graph(variables, constraints, **kwds)

Return the bipartite incidence graph of Pyomo variables and constraints.

Each node in the returned graph is an integer. The convention is that, for a graph with N variables and M constraints, nodes 0 through M-1 correspond to constraints and nodes M through M+N-1 correspond to variables. Nodes correspond to variables and constraints in the provided orders. For consistency with NetworkX’s “convention”, constraint nodes are tagged with bipartite=0 while variable nodes are tagged with bipartite=1, although these attributes are not used.

Parameters:

• variables (List of Pyomo VarData objects) – Variables that will appear in incidence graph

• constraints (List of Pyomo ConstraintData objects) – Constraints that will appear in incidence graph

• include_fixed (Bool) – Flag for whether fixed variable should be included in the incidence

Return type:

networkx.Graph

pyomo.contrib.incidence_analysis.interface.get_numeric_incidence_matrix(variables, constraints)

Return the “numeric incidence matrix” (Jacobian) of Pyomo variables and constraints.

Each matrix value is the derivative of a constraint body with respect to a variable. Rows correspond to constraints and columns correspond to variables. Entries are included even if the value of the derivative is zero. Only active constraints and unfixed variables that participate in these constraints are included.

Parameters:

• variables (List of Pyomo VarData objects) –

• constraints (List of Pyomo ConstraintData objects) –

Returns:

COO matrix. Rows are indices into the user-provided list of constraints, columns are indices into the user-provided list of variables.

Return type:

scipy.sparse.coo_matrix

pyomo.contrib.incidence_analysis.interface.get_structural_incidence_matrix(variables, constraints, **kwds)

Return the incidence matrix of Pyomo constraints and variables

Parameters:

• variables (List of Pyomo VarData objects) –

• constraints (List of Pyomo ConstraintData objects) –

• include_fixed (Bool) – Flag for whether fixed variables should be included in the matrix nonzeros

Returns:

COO matrix. Rows are indices into the user-provided list of constraints, columns are indices into the user-provided list of variables. Entries are 1.0.

Return type:

scipy.sparse.coo_matrix