Community Detection for Pyomo models
This package separates model components (variables, constraints, and objectives) into different communities distinguished by the degree of connectivity between community members.
Description of Package and detect_communities
function
The community detection package allows users to obtain a community map of a Pyomo model  a Python dictionarylike object that maps sequential integer values to communities within the Pyomo model. The package takes in a model, organizes the model components into a graph of nodes and edges, then uses Louvain community detection (Blondel et al, 2008) to determine the communities that exist within the model.
In graph theory, a community is defined as a subset of nodes that have a greater degree of connectivity within themselves than they do with the rest of the nodes in the graph. In the context of Pyomo models, a community represents a subproblem within the overall optimization problem. Identifying these subproblems and then solving them independently can save computational work compared with trying to solve the entire model at once. Thus, it can be very useful to know the communities that exist in a model.
The manner in which the graph of nodes and edges is constructed from the model directly affects the community detection. Thus, this package provides the user with a lot of control over the construction of the graph. The function we use for this community detection is shown below:
 pyomo.contrib.community_detection.detection.detect_communities(model, type_of_community_map='constraint', with_objective=True, weighted_graph=True, random_seed=None, use_only_active_components=True)[source]
Detects communities in a Pyomo optimization model
This function takes in a Pyomo optimization model and organizes the variables and constraints into a graph of nodes and edges. Then, by using Louvain community detection on the graph, a dictionary (community_map) is created, which maps (arbitrary) community keys to the detected communities within the model.
 Parameters:
model (Block) – a Pyomo model or block to be used for community detection
type_of_community_map (str, optional) – a string that specifies the type of community map to be returned, the default is ‘constraint’. ‘constraint’ returns a dictionary (community_map) with communities based on constraint nodes, ‘variable’ returns a dictionary (community_map) with communities based on variable nodes, ‘bipartite’ returns a dictionary (community_map) with communities based on a bipartite graph (both constraint and variable nodes)
with_objective (bool, optional) – a Boolean argument that specifies whether or not the objective function is included in the model graph (and thus in ‘community_map’); the default is True
weighted_graph (bool, optional) – a Boolean argument that specifies whether community_map is created based on a weighted model graph or an unweighted model graph; the default is True (type_of_community_map=’bipartite’ creates an unweighted model graph regardless of this parameter)
random_seed (int, optional) – an integer that is used as the random seed for the (heuristic) Louvain community detection
use_only_active_components (bool, optional) – a Boolean argument that specifies whether inactive constraints/objectives are included in the community map
 Returns:
The CommunityMap object acts as a Python dictionary, mapping integer keys to tuples containing two lists (which contain the components in the given community)  a constraint list and variable list. Furthermore, the CommunityMap object stores relevant information about the given community map (dict), such as the model used to create it, its networkX representation, etc.
 Return type:
CommunityMap object (dictlike object)
As stated above, the characteristics of the NetworkX graph of the Pyomo model are very important to the community detection. The main graph features the user can specify are the type of community map, whether the graph is weighted or unweighted, and whether the objective function(s) is included in the graph generation. Below, the significance and reasoning behind including each of these options are explained in greater depth.
 Type of Community Map (type_of_community_map)
In this package’s main function (
detect_communities
), the user can select'bipartite'
,'constraint'
, or'variable'
as an input for the ‘type_of_community_map’ argument, and these result in a community map based on a bipartite graph, a constraint node graph, or a variable node graph (respectively).If the user sets
type_of_community_map='constraint'
, then each entry in the community map (which is a dictionary) contains a list of all the constraints in the community as well as all the variables contained in those constraints. For the model graph, a node is created for every active constraint in the model, an edge between two constraint nodes is created only if those two constraint equations share a variable, and the weight of each edge is equal to the number of variables the two constraint equations have in common.If the user sets
type_of_community_map='variable'
, then each entry in the community map (which is a dictionary) contains a list of all the variables in the community as well as all the constraints that contain those variables. For the model graph, a node is created for every variable in the model, an edge between two variable nodes is created only if those two variables occur in the same constraint equation, and the weight of each edge is equal to the number of constraint equations in which the two variables occur together.If the user sets
type_of_community_map='bipartite'
, then each entry in the community map (which is a dictionary) is simply all of the nodes in the community but split into a list of constraints and a list of variables. For the model graph, a node is created for every variable and every constraint in the model. An edge is created between a constraint node and a variable node only if the constraint equation contains the variable. (Edges are not drawn between nodes of the same type in a bipartite graph.) And as for the edge weights, the edges in the bipartite graph are unweighted regardless of what the user specifies for theweighted_graph
parameter. (This is because for our purposes, the number of times a variable appears in a constraint is not particularly useful.) Weighted Graph/Unweighted Graph (weighted_graph)
The Louvain community detection algorithm takes edge weights into account, so depending on whether the graph is weighted or unweighted, the communities that are found will vary. This can be valuable depending on how the user intends to use the community detection information. For example, if a user plans on feeding that information into an algorithm, the algorithm may be better suited to the communities detected in a weighted graph (or vice versa).
 With/Without Objective in the Graph (with_objective)
This argument determines whether the objective function(s) will be included when creating the graphical representation of the model and thus whether the objective function(s) will be included in the community map. Some models have an objective function that contains so many of the model variables that it obscures potential communities within a model. Thus, it can be useful to call
detect_communities(model, with_objective=False)
on such a model to see whether isolating the other components of the model provides any new insights.
External Packages
NetworkX
PythonLouvain
The community detection package relies on two external packages, the NetworkX package and the Louvain community detection package. Both of these packages can be installed at the following URLs (respectively):
https://pypi.org/project/networkx/
https://pypi.org/project/pythonlouvain/
The pip install and conda install commands are included below as well:
pip install networkx
pip install pythonlouvain
conda install c anaconda networkx
conda install c condaforge pythonlouvain
Usage Examples
Let’s start off by taking a look at how we can use detect_communities
to create a CommunityMap object.
We’ll first use a model from Allman et al, 2019 :
Required Imports
>>> from pyomo.contrib.community_detection.detection import detect_communities, CommunityMap, generate_model_graph
>>> from pyomo.contrib.mindtpy.tests.eight_process_problem import EightProcessFlowsheet
>>> from pyomo.core import ConcreteModel, Var, Constraint
>>> import networkx as nx
Let's define a model for our use
>>> def decode_model_1():
... model = m = ConcreteModel()
... m.x1 = Var(initialize=3)
... m.x2 = Var(initialize=1)
... m.x3 = Var(initialize=3)
... m.x4 = Var(initialize=1)
... m.c1 = Constraint(expr=m.x1 + m.x2 <= 0)
... m.c2 = Constraint(expr=m.x1  3 * m.x2 <= 0)
... m.c3 = Constraint(expr=m.x2 + m.x3 + 4 * m.x4 ** 2 == 0)
... m.c4 = Constraint(expr=m.x3 + m.x4 <= 0)
... m.c5 = Constraint(expr=m.x3 ** 2 + m.x4 ** 2  10 == 0)
... return model
>>> model = m = decode_model_1()
>>> seed = 5 # To be used as a random seed value for the heuristic Louvain community detection
Let's create an instance of the CommunityMap class (which is what gets returned by the
function detect_communities):
>>> community_map_object = detect_communities(model, type_of_community_map='bipartite', random_seed=seed)
This community map object has many attributes that contain the relevant information about the community map itself (such as the parameters used to create it, the networkX representation, and other useful information).
An important point to note is that the community_map attribute of the CommunityMap class is the actual dictionary that maps integers to the communities within the model. It is expected that the user will be most interested in the actual dictionary itself, so dictlike usage is permitted.
If a user wishes to modify the actual dictionary (the community_map attribute of the CommunityMap object),
creating a deep copy is highly recommended (or else any destructive modifications could
have unintended consequences): new_community_map = copy.deepcopy(community_map_object.community_map)
Let’s take a closer look at the actual community map object generated by detect_communities:
>>> print(community_map_object)
{0: (['c1', 'c2'], ['x1', 'x2']), 1: (['c3', 'c4', 'c5'], ['x3', 'x4'])}
Printing a community map object is made to be userfriendly (by showing the community map with components replaced by their strings). However, if the default Pyomo representation of components is desired, then the community_map attribute or the repr() function can be used:
>>> print(community_map_object.community_map)
{0: ([<pyomo.core.base.constraint.ScalarConstraint object at ...>, <pyomo.core.base.constraint.ScalarConstraint object at ...>], [<pyomo.core.base.var.ScalarVar object at ...>, <pyomo.core.base.var.ScalarVar object at ...>]), 1: ([<pyomo.core.base.constraint.ScalarConstraint object at ...>, <pyomo.core.base.constraint.ScalarConstraint object at ...>, <pyomo.core.base.constraint.ScalarConstraint object at ...>], [<pyomo.core.base.var.ScalarVar object at ...>, <pyomo.core.base.var.ScalarVar object at ...>])}
>>> print(repr(community_map_object))
{0: ([<pyomo.core.base.constraint.ScalarConstraint object at ...>, <pyomo.core.base.constraint.ScalarConstraint object at ...>], [<pyomo.core.base.var.ScalarVar object at ...>, <pyomo.core.base.var.ScalarVar object at ...>]), 1: ([<pyomo.core.base.constraint.ScalarConstraint object at ...>, <pyomo.core.base.constraint.ScalarConstraint object at ...>, <pyomo.core.base.constraint.ScalarConstraint object at ...>], [<pyomo.core.base.var.ScalarVar object at ...>, <pyomo.core.base.var.ScalarVar object at ...>])}
 generate_structured_model method of CommunityMap objects
It may be useful to create a new model based on the communities found in the model  we can use the
generate_structured_model
method of the CommunityMap class to do this. Calling this method on a CommunityMap object returns a new model made up of blocks that correspond to each of the communities found in the original model. Let’s take a look at the example below:Use the CommunityMap object made from the first code example >>> structured_model = community_map_object.generate_structured_model() >>> structured_model.pprint() 2 Set Declarations b_index : Size=1, Index=None, Ordered=Insertion Key : Dimen : Domain : Size : Members None : 1 : Any : 2 : {0, 1} equality_constraint_list_index : Size=1, Index=None, Ordered=Insertion Key : Dimen : Domain : Size : Members None : 1 : Any : 1 : {1,} 1 Var Declarations x2 : Size=1, Index=None Key : Lower : Value : Upper : Fixed : Stale : Domain None : None : None : None : False : True : Reals 1 Constraint Declarations equality_constraint_list : Equality Constraints for the different forms of a given variable Size=1, Index=equality_constraint_list_index, Active=True Key : Lower : Body : Upper : Active 1 : 0.0 : b[0].x2  x2 : 0.0 : True 1 Block Declarations b : Size=2, Index=b_index, Active=True b[0] : Active=True 2 Var Declarations x1 : Size=1, Index=None Key : Lower : Value : Upper : Fixed : Stale : Domain None : None : None : None : False : True : Reals x2 : Size=1, Index=None Key : Lower : Value : Upper : Fixed : Stale : Domain None : None : None : None : False : True : Reals 2 Constraint Declarations c1 : Size=1, Index=None, Active=True Key : Lower : Body : Upper : Active None : Inf : b[0].x1 + b[0].x2 : 0.0 : True c2 : Size=1, Index=None, Active=True Key : Lower : Body : Upper : Active None : Inf : b[0].x1  3*b[0].x2 : 0.0 : True 4 Declarations: x1 x2 c1 c2 b[1] : Active=True 2 Var Declarations x3 : Size=1, Index=None Key : Lower : Value : Upper : Fixed : Stale : Domain None : None : None : None : False : True : Reals x4 : Size=1, Index=None Key : Lower : Value : Upper : Fixed : Stale : Domain None : None : None : None : False : True : Reals 3 Constraint Declarations c3 : Size=1, Index=None, Active=True Key : Lower : Body : Upper : Active None : 0.0 : x2 + b[1].x3 + 4*b[1].x4**2 : 0.0 : True c4 : Size=1, Index=None, Active=True Key : Lower : Body : Upper : Active None : Inf : b[1].x3 + b[1].x4 : 0.0 : True c5 : Size=1, Index=None, Active=True Key : Lower : Body : Upper : Active None : 0.0 : b[1].x3**2 + b[1].x4**2  10 : 0.0 : True 5 Declarations: x3 x4 c3 c4 c5 5 Declarations: b_index b x2 equality_constraint_list_index equality_constraint_list
We see that there is an equality constraint list (equality_constraint_list) that has been created. This is due to the fact that the
detect_communities
function can return a community map that has Pyomo components (variables, constraints, or objectives) in more than one community, and thus, an equality_constraint_list is created to ensure that the new model still corresponds to the original model. This is explained in more detail below.Consider the case where community detection is done on a constraint node graph  this would result in communities that are made up of the corresponding constraints as well as all the variables that occur in the given constraints. Thus, it is possible for certain Pyomo components to be in multiple communities (and a similar argument exists for community detection done on a variable node graph). As a result, our structured model (the model returned by the
generate_structured_model
method) may need to have several “copies” of a certain component. For example, a variable original_model.x1 that exists in the original model may have corresponding forms structured_model.b[0].x1, structured_model.b[0].x1, structured_model.x1. In order for these components to meaningfully correspond to their counterparts in the original model, they must be bounded by equality constraints. Thus, we use an equality_constraint_list to bind different forms of a component from the original model.The last point to make about this method is that variables will be created outside of blocks if (1) an objective is not inside a block (for example if the community detection is done with_objective=False) or if (2) an objective/constraint contains a variable that is not in the same block as the given objective/constraint.
 visualize_model_graph method of CommunityMap objects
If we want a visualization of the communities within the Pyomo model, we can use
visualize_model_graph
to do so. Let’s take a look at how this can be done in the following example:Create a CommunityMap object (so we can demonstrate the visualize_model_graph method) >>> community_map_object = cmo = detect_communities(model, type_of_community_map='bipartite', random_seed=seed) Generate a matplotlib figure (left_figure)  a constraint graph of the community map >>> left_figure, _ = cmo.visualize_model_graph(type_of_graph='constraint') Now, we will generate the figure on the right (a bipartite graph of the community map) >>> right_figure, _ = cmo.visualize_model_graph(type_of_graph='bipartite')
 An example of the two separate graphs created for these two function calls is shown below:

These graph drawings very clearly demonstrate the communities within this model. The constraint graph (which is colored using the bipartite community map) shows a very simple illustration  one node for each constraint, with only one edge connecting the two communities (which represents the variable m.x2 common to m.c2 and m.c3 in separate communities) The bipartite graph is slightly more complicated and we can see again how there is only one edge between the two communities and more edges within each community. This is an ideal situation for breaking a model into separate communities since there is little connectivity between the communities. Also, note that we can choose different graph types (such as a variable node graph, constraint node graph, or bipartite graph) for a given community map.
Let’s try a more complicated model (taken from Duran & Grossmann, 1986)  this example will demonstrate how the same graph can be illustrated using different community maps (in the previous example we illustrated different graphs with a single community map):
Define the model >>> model = EightProcessFlowsheet() Now, we follow steps similar to the example above (see above for explanations) >>> community_map_object = cmo = detect_communities(model, type_of_community_map='constraint', random_seed=seed) >>> left_fig, pos = cmo.visualize_model_graph(type_of_graph='variable') As we did before, we will use the returned 'pos' to create a consistent graph layout >>> community_map_object = cmo = detect_communities(model, type_of_community_map='bipartite') >>> middle_fig, _ = cmo.visualize_model_graph(type_of_graph='variable', pos=pos) >>> community_map_object = cmo = detect_communities(model, type_of_community_map='variable') >>> right_fig, _ = cmo.visualize_model_graph(type_of_graph='variable', pos=pos)
 We can see an example for the three separate graphs created by these three function calls below:

The three graphs above are all variable graphs  which means the nodes represent variables in the model, and the edges represent constraint equations. The coloring differs because the three graphs rely on community maps that were created based on a constraint node graph, a bipartite graph, and a variable node graph (from left to right). For example, the community map that was generated from a constraint node graph (
type_of_community_map='constraint'
) resulted in three communities (as seen by the purple, yellow, and blue nodes).  generate_model_graph function
Now, we will take a look at
generate_model_graph
 this function can be used to create a NetworkX graph for a Pyomo model (and is used in detect_communities). Here, we will create a NetworkX graph from the model in our first example and then create the edge and adjacency list for the graph.generate_model_graph
returns three things:a NetworkX graph of the given model
a dictionary that maps the numbers used to represent the model components to the actual components (because Pyomo components cannot be directly added to a NetworkX graph)
a dictionary that maps constraints to the variables in them.
For this example, we will only need the NetworkX graph of the model and the numbertocomponent mapping.
Define the model >>> model = decode_model_1() See above for the description of the items returned by 'generate_model_graph' >>> model_graph, number_component_map, constr_var_map = generate_model_graph(model, type_of_graph='constraint') The next two lines create and implement a mapping to change the node values from numbers into strings. The second line uses this mapping to create string_model_graph, which has the relabeled nodes (strings instead of numbers). >>> string_map = dict((number, str(comp)) for number, comp in number_component_map.items()) >>> string_model_graph = nx.relabel_nodes(model_graph, string_map) Now, we print the edge list and the adjacency list: Edge List: >>> for line in nx.generate_edgelist(string_model_graph): print(line) c1 c2 {'weight': 2} c1 c3 {'weight': 1} c2 c3 {'weight': 1} c3 c5 {'weight': 2} c3 c4 {'weight': 2} c4 c5 {'weight': 2} Adjacency List: >>> print(list(nx.generate_adjlist(string_model_graph))) ['c1 c2 c3', 'c2 c3', 'c3 c5 c4', 'c4 c5', 'c5']
It’s worth mentioning that in the code above, we do not have to create
string_map
to create an edge list or adjacency list, but for the sake of having an easily understandable output, it is quite helpful. (Without relabeling the nodes, the output below would not have the strings of the components but instead would have integer values.) This code will hopefully make it easier for a user to do the same.
Functions in this Package
Main module for community detection integration with Pyomo models.
This module separates model components (variables, constraints, and objectives) into different communities distinguished by the degree of connectivity between community members.
Original implementation developed by Rahul Joglekar in the Grossmann research group.
 class pyomo.contrib.community_detection.detection.CommunityMap(community_map, type_of_community_map, with_objective, weighted_graph, random_seed, use_only_active_components, model, graph, graph_node_mapping, constraint_variable_map, graph_partition)[source]
This class is used to create CommunityMap objects which are returned by the detect_communities function. Instances of this class allow dictlike usage and store relevant information about the given community map, such as the model used to create them, their networkX representation, etc.
The CommunityMap object acts as a Python dictionary, mapping integer keys to tuples containing two lists (which contain the components in the given community)  a constraint list and variable list.
Methods: generate_structured_model visualize_model_graph
 generate_structured_model()[source]
Using the community map and the original model used to create this community map, we will create structured_model, which will be based on the original model but will place variables, constraints, and objectives into or outside of various blocks (communities) based on the community map.
 Returns:
structured_model – a Pyomo model that reflects the nature of the community map
 Return type:
 visualize_model_graph(type_of_graph='constraint', filename=None, pos=None)[source]
This function draws a graph of the communities for a Pyomo model.
The type_of_graph parameter is used to create either a variablenode graph, constraintnode graph, or bipartite graph of the Pyomo model. Then, the nodes are colored based on the communities they are in  which is based on the community map (self.community_map). A filename can be provided to save the figure, otherwise the figure is illustrated with matplotlib.
 Parameters:
type_of_graph (str, optional) – a string that specifies the types of nodes drawn on the model graph, the default is ‘constraint’. ‘constraint’ draws a graph with constraint nodes, ‘variable’ draws a graph with variable nodes, ‘bipartite’ draws a bipartite graph (with both constraint and variable nodes)
filename (str, optional) – a string that specifies a path for the model graph illustration to be saved
pos (dict, optional) – a dictionary that maps node keys to their positions on the illustration
 Returns:
fig (matplotlib figure) – the figure for the model graph drawing
pos (dict) – a dictionary that maps node keys to their positions on the illustration  can be used to create consistent layouts for graphs of a given model
 pyomo.contrib.community_detection.detection.detect_communities(model, type_of_community_map='constraint', with_objective=True, weighted_graph=True, random_seed=None, use_only_active_components=True)[source]
Detects communities in a Pyomo optimization model
This function takes in a Pyomo optimization model and organizes the variables and constraints into a graph of nodes and edges. Then, by using Louvain community detection on the graph, a dictionary (community_map) is created, which maps (arbitrary) community keys to the detected communities within the model.
 Parameters:
model (Block) – a Pyomo model or block to be used for community detection
type_of_community_map (str, optional) – a string that specifies the type of community map to be returned, the default is ‘constraint’. ‘constraint’ returns a dictionary (community_map) with communities based on constraint nodes, ‘variable’ returns a dictionary (community_map) with communities based on variable nodes, ‘bipartite’ returns a dictionary (community_map) with communities based on a bipartite graph (both constraint and variable nodes)
with_objective (bool, optional) – a Boolean argument that specifies whether or not the objective function is included in the model graph (and thus in ‘community_map’); the default is True
weighted_graph (bool, optional) – a Boolean argument that specifies whether community_map is created based on a weighted model graph or an unweighted model graph; the default is True (type_of_community_map=’bipartite’ creates an unweighted model graph regardless of this parameter)
random_seed (int, optional) – an integer that is used as the random seed for the (heuristic) Louvain community detection
use_only_active_components (bool, optional) – a Boolean argument that specifies whether inactive constraints/objectives are included in the community map
 Returns:
The CommunityMap object acts as a Python dictionary, mapping integer keys to tuples containing two lists (which contain the components in the given community)  a constraint list and variable list. Furthermore, the CommunityMap object stores relevant information about the given community map (dict), such as the model used to create it, its networkX representation, etc.
 Return type:
CommunityMap object (dictlike object)
Model Graph Generator Code
 pyomo.contrib.community_detection.community_graph.generate_model_graph(model, type_of_graph, with_objective=True, weighted_graph=True, use_only_active_components=True)[source]
Creates a networkX graph of nodes and edges based on a Pyomo optimization model
This function takes in a Pyomo optimization model, then creates a graphical representation of the model with specific features of the graph determined by the user (see Parameters below).
(This function is designed to be called by detect_communities, but can be used solely for the purpose of creating model graphs as well.)
 Parameters:
model (Block) – a Pyomo model or block to be used for community detection
type_of_graph (str) – a string that specifies the type of graph that is created from the model ‘constraint’ creates a graph based on constraint nodes, ‘variable’ creates a graph based on variable nodes, ‘bipartite’ creates a graph based on constraint and variable nodes (bipartite graph).
with_objective (bool, optional) – a Boolean argument that specifies whether or not the objective function is included in the graph; the default is True
weighted_graph (bool, optional) – a Boolean argument that specifies whether a weighted or unweighted graph is to be created from the Pyomo model; the default is True (type_of_graph=’bipartite’ creates an unweighted graph regardless of this parameter)
use_only_active_components (bool, optional) – a Boolean argument that specifies whether inactive constraints/objectives are included in the networkX graph
 Returns:
bipartite_model_graph/projected_model_graph (nx.Graph) – a NetworkX graph with nodes and edges based on the given Pyomo optimization model
number_component_map (dict) – a dictionary that (deterministically) maps a number to a component in the model
constraint_variable_map (dict) – a dictionary that maps a numbered constraint to a list of (numbered) variables that appear in the constraint