IncidenceGraphInterface

(class from pyomo.contrib.incidence_analysis.interface)

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

Bases: object

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.

__init__(model=None, active=True, include_inequality=True, **kwds)[source]: Construct an IncidenceGraphInterface object

Methods

`__init__`([model, active, include_inequality])	Construct an IncidenceGraphInterface object
`add_edge`(variable, constraint)	Adds an edge between variable and constraint in the incidence graph
`block_triangularize`([variables, constraints])	Compute an ordered partition of the provided variables and constraints such that their incidence matrix is block lower triangular
`dulmage_mendelsohn`([variables, constraints])	Partition variables and constraints according to the Dulmage- Mendelsohn characterization of the incidence graph
`get_adjacent_to`(component)	Return a list of components adjacent to the provided component in the cached bipartite incidence graph of variables and constraints
`get_connected_components`([variables, ...])	Partition variables and constraints into weakly connected components of the incidence graph
`get_diagonal_blocks`([variables, constraints])	DEPRECATED.
`get_matrix_coord`(component)	Return the row or column coordinate of the component in the incidence matrix of variables and constraints
`map_nodes_to_block_triangular_indices`([...])	Map variables and constraints to indices of their diagonal blocks in a block lower triangular permutation
`maximum_matching`([variables, constraints])	Return a maximum cardinality matching of variables and constraints.
`plot`([variables, constraints, title, show])	Plot the bipartite incidence graph of variables and constraints
`remove_nodes`([variables, constraints])	Removes the specified variables and constraints (columns and rows) from the cached incidence matrix.
`subgraph`(variables, constraints)	Extract a subgraph defined by the provided variables and constraints

Attributes

`col_block_map`	DEPRECATED.
`con_index_map`	DEPRECATED.
`constraints`	The constraints participating in the incidence graph
`incidence_matrix`	The structural incidence matrix of variables and constraints.
`n_edges`	The number of edges in the incidence graph, or the number of structural nonzeros in the incidence matrix
`row_block_map`	DEPRECATED.
`var_index_map`	DEPRECATED.
`variables`	The variables participating in the incidence graph

Member Documentation

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 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.

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 use IncidenceGraphInterface.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

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

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

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.

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 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

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.

property n_edges: The number of edges in the incidence graph, or the number of structural nonzeros in 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.

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