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.
-
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
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 returnedReturns: 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 locateReturns: 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 triangularization - con_block_map (
ComponentMap
) – Map from constraints to their diagonal blocks in a block triangularization
- var_block_map (
-
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
(nodes, 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:
-
property
row_block_map
DEPRECATED.
Deprecated since version 6.5.0: The
row_block_map
attribute is deprecated and will be removed.
-
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
- model (Pyomo BlockData or PyNumero PyomoNLP, default
-
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