Dulmage-Mendelsohn Partition

class pyomo.contrib.incidence_analysis.dulmage_mendelsohn.ColPartition(unmatched, underconstrained, overconstrained, square)

Named tuple containing the subsets of the Dulmage-Mendelsohn partition when applied to matrix columns (variables).

overconstrained: Alias for field number 2

square: Alias for field number 3

underconstrained: Alias for field number 1

unmatched: Alias for field number 0

class pyomo.contrib.incidence_analysis.dulmage_mendelsohn.RowPartition(unmatched, overconstrained, underconstrained, square)

Named tuple containing the subsets of the Dulmage-Mendelsohn partition when applied to matrix rows (constraints).

overconstrained: Alias for field number 1

square: Alias for field number 3

underconstrained: Alias for field number 2

unmatched: Alias for field number 0

pyomo.contrib.incidence_analysis.dulmage_mendelsohn.dulmage_mendelsohn(matrix_or_graph, top_nodes=None, matching=None)[source]

Partition a bipartite graph or incidence matrix according to the Dulmage-Mendelsohn characterization

The Dulmage-Mendelsohn partition tells which nodes of the two bipartite sets can possibly be unmatched after a maximum cardinality matching. Applied to an incidence matrix, it can be interpreted as partitioning rows and columns into under-constrained, over-constrained, and well-constrained subsystems.

As it is often useful to explicitly check the unmatched rows and columns, dulmage_mendelsohn partitions rows into the subsets:

underconstrained - The rows matched with possibly unmatched columns (unmatched and underconstrained columns)
square - The well-constrained rows, which are matched with well-constrained columns
overconstrained - The matched rows that can possibly be unmatched in some maximum cardinality matching
unmatched - The unmatched rows in a particular maximum cardinality matching

and partitions columns into the subsets:

unmatched - The unmatched columns in a particular maximum cardinality matching
underconstrained - The columns that can possibly be unmatched in some maximum cardinality matching
square - The well-constrained columns, which are matched with well-constrained rows
overconstrained - The columns matched with possibly unmatched rows (unmatched and overconstrained rows)

Parameters:

matrix_or_graph (scipy.sparse.coo_matrix or networkx.Graph) – The incidence matrix or bipartite graph to be partitioned
top_nodes (list) – List of nodes in one bipartite set of the graph. Must be provided if a graph is provided.
matching (dict) – A maximum cardinality matching in the form of a dict mapping from “top nodes” to their matched nodes and from the matched nodes back to the “top nodes”.

Returns:

row_dmp (RowPartition) – The Dulmage-Mendelsohn partition of rows
col_dmp (ColPartition) – The Dulmage-Mendelsohn partition of columns