Graph Partitioning and Processing

The Modeling with OptiGraphs section describes how to construct optigraphs using a bottom-up approach with a focus on Hierarchical Modeling using Subgraphs to create multi-level optigraphs. Plasmo.jl also supports creating multi-level optigraphs using a top-down approach. This is done using the optigraph partition functions and interfaces to standard graph partitioning tools such as Metis and KaHyPar.

Example Partitioning Problem: Dynamic Optimization

To help demonstrate graph partitioning capabilities in Plasmo.jl, we instantiate a simple optimal control problem described by the following equations. In this problem, $x$ is a vector of states and $u$ is a vector of control actions which are both indexed over the set of time indices $t \in \{1,...,T\}$. The objective function minimizes the state trajectory with minimal control effort, the second equation describes the state dynamics, and the third equation defines the initial condition. The last two equations define limits on the state and control actions.

\[\begin{aligned} \min_{\{ x,u \}} & \sum_{t = 1}^T x_t^2 + u_t^2 & \\ \textrm{s.t.} \quad & x_{t+1} = x_t + u_t + d_t, \quad t \in \{1,...,T-1\} & \\ & x_{1} = 0 &\\ & x_t \ge 0, \quad t \in \{1,...,T\}\\ & u_t \ge -1000, \quad t \in \{1,...,T-1\} \end{aligned}\]

This snippet shows how to construct the optimal control problem in Plasmo.jl. We create an optigraph, add optinodes which represent states and controls at each time period, we set objective functions for each optinode, and we use link-constraints to describe the dynamics.

using Plasmo

T = 100          #number of time points
d = sin.(1:T)    #disturbance vector

graph = OptiGraph()
@optinode(graph,state[1:T])
@optinode(graph,control[1:T-1])

for node in state
    @variable(node,x)
    @constraint(node, x >= 0)
    @objective(node,Min,x^2)
end
for node in control
    @variable(node,u)
    @constraint(node, u >= -1000)
    @objective(node,Min,u^2)
end

@linkconstraint(graph,[i = 1:T-1],state[i+1][:x] == state[i][:x] + control[i][:u] + d[i])
n1 = state[1]
@constraint(n1,n1[:x] == 0)

When we print the newly created optigraph for our optimal control problem, we see it contains about 200 optinodes (one for each state and control) and contains almost 100 linking constraints (which couple the time periods).

julia> println(graph)
      OptiGraph: # elements (including subgraphs)
-------------------------------------------------------------------
      OptiNodes:   199            (199)
      OptiEdges:    99             (99)
LinkConstraints:    99             (99)
 sub-OptiGraphs:     0              (0)

We can also plot the resulting optigraph (see Plotting) which produces a simple chain of optinodes.

using PlasmoPlots

plt_chain_layout = layout_plot(graph,
                               layout_options=Dict(:tol=>0.1,:iterations=>500),
                               linealpha = 0.2,
                               markersize = 6)

plt_chain_matrix = matrix_plot(graph)

Partitioning OptiGraphs

At its core, the OptiGraph is a hypergraph and can naturally interface to hypergraph partitioning tools. For our example here we demonstrate how to use hypergraph partitioning (using KaHyPar), but Plasmo.jl also supports standard graph partitioning algorithms using graph projections. The below snippet uses the hyper_graph function which returns a Plasmo.HyperGraph object and a hyper_map (a Julia dictionary) which maps hypernodes and hyperedges back to the original optigraph.

julia> hgraph, hyper_map = hyper_graph(graph);

julia> println(hgraph)
Hypergraph: (199 , 99)

With our hypergraph we can now perform hypergraph partitioning in the next snippet which returns a partition_vector. Each index in the partition_vector corresponds to a hypernode in hypergraph, and each value denotes which partition the hypernode belongs to. So in our example, partition_vector contains 199 elements which take on integer values between 0 and 7 (for 8 total partitions). Once we have a partition_vector, we can create a Partition object which describes partitions of optinodes and optiedges, as well as the shared optinodes and optiedges that cross partitions. We can lastly use the produced partition object to formulate subgraphs in our original optigraph (graph) using apply_partition!. After doing so, we see that our graph now contains 8 subgraphs with 7 link-constraints that correspond to the optiedges that cross partitions (i.e. connect subgraphs).

julia> using KaHyPar

julia> partition_vector = KaHyPar.partition(hypergraph,
                                            8,
                                            configuration=:connectivity,
                                            imbalance=0.01);

julia> partition = Partition(partition_vector, hyper_map);

julia> apply_partition!(graph, partition);

julia> length(partition_vector)
199

julia> partition
OptiGraph Partition w/ 8 subpartitions

julia> num_subgraphs(graph)
8

julia> num_linkconstraints(graph)
7

julia> num_all_linkconstraints(graph)
99

If we plot the partitioned optigraph, it reveals eight distinct partitions and the coupling between them. The plots show that the partitions are well-balanced and the matrix visualization shows the problem is reordered into a banded structure that is typical of dynamic optimization problems.

plt_chain_partition_layout = layout_plot(graph,
                                         layout_options=Dict(:tol=>0.01,
                                                        :iterations=>500),
                                         linealpha=0.2,
                                         markersize=6,
                                         subgraph_colors=true)

plt_chain_partition_matrix = matrix_layout(graph, subgraph_colors=true)

Aggregating OptiGraphs

Subgraphs can be converted into stand-alone optinodes using the using the aggregate function. This can be helpful when the user models using subgraphs, but they want to represent solvable subproblems using optinodes. In the snippet below, we aggregate our optigraph that contains 8 subgraphs. We include the argument 0 which specifies how many subgraph levels to retain. In this case, 0 means we aggregate subgraphs at the highest level so graph contains only new aggregated optinodes. For hierarchical graphs with many levels, we can define how many subgraph levels we wish to retain. The function returns a new aggregated graph (aggregate_graph), as well as a reference_map which maps elements in aggregate_graph to the original optigraph graph.

julia> aggregate_graph,reference_map = aggregate(graph,0);
Aggregating OptiGraph with a maximum subgraph depth of 0

julia> println(aggregate_graph)
      OptiGraph: # elements (including subgraphs)
-------------------------------------------------------------------
      OptiNodes:     8              (8)
      OptiEdges:     7              (7)
LinkConstraints:     7              (7)
 sub-OptiGraphs:     0              (0)

We can lastly plot the aggregated graph structure which simply shows 8 optinodes with 7 linking constraints.

plt_chain_aggregate = layout_plot(aggregate_graph,
                                  layout_options=Dict(:tol=>0.01,:iterations=>10),
                                  node_labels=true,
                                  markersize=30,
                                  labelsize=20,
                                  node_colors=true)

plt_chain_matrix_aggregate = matrix_plot(aggregate_graph,
                                         node_labels=true,
                                         node_colors=true);

OptiGraph Projections