Community Detection Method for Decomposition for Optimization Problems

Generates Decompositions for Generic Optimization Problems

Detection of Communities for Optimization Decomposition (DeCODe) is a systematic method and software package that generates decompositions for generic optimization problems. The automated, generic method uses community detection to find subproblems that decomposition solution methods can efficiently solve. The subproblems generated are tightly interacting amongst themselves but weakly interacting with other subproblems, thus minimizing the amount of coordination required in the solution approach. The software package requires minimal input from the user: it needs only the constraint equations and an initial guess for the variables. The software then uses embedded functions to generate a variable-constraint graph, calculate modularity of different partitions, detect communities, and return which variables or constraints belong to which subproblem.

Community Detection Identifies Subproblems

Optimization, a ubiquitous tool in process systems engineering, is used on models of ever-increasing size and complexity. Large or difficult to solve optimization problems sometimes require applying decomposition, which breaks the original problem into a series of subproblems with smaller size and reduced computational complexity. From there, one of several ad hoc decomposition solution methods can be applied. DeCODe generates decompositions for a generic optimization problem and uses communities as the basis for finding subproblems that decomposition solution methods can efficiently solve. Community detection is widely used in network theory to find groups within a network that have high modularity (i.e., groups with statistically high intra-group connectivity and therefore statistically low inter-group connectivity). To apply DeCODe to an optimization problem, a bipartite variable-constraint graph is developed, where nodes representing a variable or constraint are connected if the variable appears in the constraint. The communities found in this network represent subproblems in the decomposition that have low connectivity (coupling) between them, reducing the effort needed by the decomposition solution method.

BENEFITS AND FEATURES:

• Systematic method and software package generates decompositions for generic optimization problems
• New, generic method for finding decompositions
• Uses community detection to find subproblems that decomposition solution methods can efficiently solve
• Novel variable-constraint graph representation of optimization
• Community detection finds high modularity partitions
• Results applicable to any decomposition solution method
• Distributed optimization approach to test algorithm
• Method works well when finding optimal solution difficult

APPLICATIONS:

• Solving optimization problems
• Finding difficult optimal solutions

Phase of Development – research licenses available

Researchers