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)[source]
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 toFalse
if themodel
is provided as a PyomoNLP.include_fixed (Bool, default
False
) – Whether to include fixed variables in the incidence graph. Cannot be set toFalse
ifmodel
is a PyomoNLP.include_inequality (Bool, default
True
) – Whether to include inequality constraints (those whose expressions are not instances ofEqualityExpression
) in the incidence graph. If a PyomoNLP is provided, setting toFalse
uses theevaluate_jacobian_eq
method instead ofevaluate_jacobian
rather than checking constraint expression types.
- add_edge(variable, constraint)[source]
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)[source]
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 ofblock_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 theget_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 ofblock_triangularize
is still available via themap_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 useget_matrix_coord
instead.
- property constraints
The constraints participating in the incidence graph
- dulmage_mendelsohn(variables=None, constraints=None)[source]
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)[source]
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)[source]
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)[source]
DEPRECATED.
Deprecated since version 6.5.0:
IncidenceGraphInterface.get_diagonal_blocks
is deprecated. Please useIncidenceGraphInterface.block_triangularize
instead.
- get_matrix_coord(component)[source]
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)[source]
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 triangularizationcon_block_map (
ComponentMap
) – Map from constraints to their diagonal blocks in a block triangularization
- maximum_matching(variables=None, constraints=None)[source]
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)[source]
Plot the bipartite incidence graph of variables and constraints
- remove_nodes(variables=None, constraints=None)[source]
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:
variables (list) – VarData objects whose nodes will be removed from the incidence graph
constraints (list) – ConData objects whose nodes will be removed from the incidence graph
note:: (..) –
Deprecation in Pyomo v6.7.2
The pre-6.7.2 implementation of
remove_nodes
allowed variables and constraints to remove to be specified in a single list. This made error checking difficult, and indeed, if invalid components were provided, we carried on silently instead of throwing an error or warning. As part of a fix to raise an error if an invalid component (one that is not part of the incidence graph) is provided, we now require variables and constraints to be specified separately.
- 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)[source]
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 useget_matrix_coord
instead.
- property variables
The variables participating in the incidence graph
- pyomo.contrib.incidence_analysis.interface.extract_bipartite_subgraph(graph, nodes0, nodes1)[source]
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)[source]
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 withbipartite=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)[source]
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)[source]
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