Max-Flow/Min-Cut Duality: Implementation & Visualization
In a previous post, we discussed the strong dual relationship between the Max-Flow and Min-Cut optimization problems, and presented matrix/vector formulations of those problems. In this post, we show how to implement each problem as a linear program (LP) using gurobipy
, and then visualize the primal and dual variable values using networkx
and matplotlib
. As an aside, note that linear programming is generally not the best tool for solving these problems, as there exist specialized algorithms like the Ford-Fulkerson algorithm or Dinic’s algorithm. The purpose of solving these problems as LPs is to demonstrate the extraction of dual variable values in gurobipy
and to highlight these problems’ primal-dual relationships.
This post is part 2 of a 2-part series. This part focuses on LP implementations of the Max-Flow and Min-Cut optimization problems in gurobipy
, and visualizations of the primal and dual variable values for solved instances. In
the first part,
we walk through the strong dual relationship between these two problems.
The code from this post is available for download as a Jupyter notebook.
Setup
For this demonstration, we need tools from just a handful of packages.
|
|
Next, we define the graph parameters and instantiate a networkx.DiGraph
for later use.
|
|
Linear Programming Formulations
Recall from part 1 that the Max-Flow problem is defined on a directed graph ${G = (V, E)}$ with source node $s$ and sink node $t$. In an equivalent reformulation, the problem is defined on an augmented graph $\hat{G} = (V, \hat{E})$ where $\hat{E} = E \cup \{(t, s)\}.$ The added uncapacitated edge $(t, s)$ completes a cycle that allows the maximum flow to recirculate from $t$ to $s$. Each variable $x_{ij}$ represents the flow on edge $(i, j)$. In the flow balance constraints, ${\hat{V}_i^+ = \{j : (j, i) \in \hat{E}\}}$ and ${\hat{V}_i^- = \{j : (i, j) \in \hat{E}\}}.$ Additionally, $c_{ij}$ denotes the flow capacity of edge $(i, j)$. For the sake of simplicity, we suppose $G$ has at least one path from $s$ to $t$ and that $c_{ij} > 0$ for all $(i, j) \in E$ as the conditions guarantee a non-trivial solution (i.e., $z_p^* > 0$). Using this notation, we presented the following LP formulation of Max-Flow:
Its dual, an LP relaxation of the Min-Cut integer program, is
Linear Programming Implementations
In our code, most of the names are straightforward. Two names that warrant clarification are
Vp_hat[i]
(“p” for plus) which represents $\hat{V}_i^+$
and
Vm_hat[i]
(“m” for minus) which represents $\hat{V}_i^-.$
With the parameters already established, only a few lines of code are needed to implement and solve
this formulation.
|
|
con_z
represents the flow balance constraints and is named to indicate the corresponding dual variables. Likewise, con_y
represents the flow capacity constraints.
In part 1 we made two observations about the dual LP:
- Complementary slackness requires that $z_s^* - z_t^* \ge 1$ be binding if $x_{ts}^* > 0$.
- Given that only differences of the $z_i$ variables are present in the constraints, we are free to fix a single $z_i$ to a constant value.
Since our parameterization of the instance guarantees $x_{ts}^* > 0$ , rather than implement $z_s - z_t \ge 1$ we fix $z_t = 0$ and $z_s = 1$. Our implementation of the LP relaxation of Min-Cut is given below.
|
|
con_x
in the dual represents the separation-enforcing constraints whose corresponding dual variables are the flow variables in the primal LP. Though this is a formulation of a linear program, its extreme point solutions are all integral owing to the constraint matrix being totally unimodular and the constant terms in the constraints being integral.
Visualization via Max-Flow
We conclude by visualizing the optimal solutions to these problems that were identified by the Gurobi solver. Each visualization shows both the Max-Flow and Min-Cut solutions. To show the Max-Flow solution, we draw a label on each edge indicating the flow and the capacity. Moreover, we shade the edge to reflect its usage relative to its capacity (light for low usage and dark for high usage). To show the Min-Cut solution, we color the nodes to reflect their bipartitioning (green if in the same group as the source node and red if in the same group as the sink node). Additionally, edges that participate in the cut are drawn with dashed lines.
When using gurobipy
, a variable’s value in the current solution is stored as a float
to the X
attribute. A constraint’s shadow price (i.e., dual variable value) is stored as a float
to the Pi
attribute of the constraint. After we solve the primal problem, we thus retrieve the Max-Flow solution values via x[i].X
and the Min-Cut solution values as con_y[i, j].Pi
and con_z[i].Pi
. The code for illustrating the solution and the illustration itself are both shown below.
|
|
The identified optimal Max-Flow solution leverages all but one of the edges – edge $(a, c)$ – and achieves a flow of 20 from $s$ to $t$. The corresponding optimal Min-Cut solution bipartitions the nodes into ${A=\{s, a, b, c, d, e\}}$ and ${B=\{t\}}$ . It does so by cutting edges $(b, t)$ and $(e, t)$ with respective edge capacities of 8 and 12 which indeed sum to 20.
Note that complementary slackness requires requires either $x_{ij}^* = c_{ij}$ in the Max-Flow problem or $y_{ij}^* = 0$ in the Min-Cut problem (or both). That is, if an edge participates in the cut of an optimal Min-Cut solution, then its flow is equal to its capacity in the corresponding optimal Max-Flow solution.
Visualization via Min-Cut
The code for visualizing the solutions by way of solving the Min-Cut problem is much the same. The only differences are that we retrieve the Max-Flow solution values via con_x[i].Pi
and the Min-Cut solution values via y[i, j].X
and z[i].X
. The code and resulting illustration are both shown below.
|
|
The identified optimal Max-Flow solution again leverages all but edge $(a, c)$; however, a few glances back-and-forth with the previous illustration are enough to see that the Max-Flow solution is subtly different in the bottom part of the graph. Nevertheless, this solution also achieves a flow of 20 from $s$ to $t$. The corresponding optimal Min-Cut solution bipartitions the nodes into ${A=\{s, c, d, e\}}$ and ${B=\{a, b, t\}}.$ It does so by cutting edges $(s, a)$, $(c, b)$, and $(e, t)$ with respective edge capacities of 6, 2, and 12 which again sum to 20.
There are apparently multiple optima for each problem, and Gurobi interestingly identified a different primal-dual pair of optimal solutions when it solved Min-Cut versus when it solved Max-Flow. In solutions identified solving Min-Cut, another implication of complementary slackness is evidenced. Either $x_{ij}^* = 0$ in the Max-Flow problem or ${y_{ij}^* = z_i^* - z_j^* }$ in the Min-Cut problem (or both). So for edge $(i, j)$, if the optimal Min-Cut solution bipartitions the vertices with ${\{j, s\} \subseteq A}$ and ${\{i, t\} \subseteq B}$ , then the corresponding optimal Max-Flow solution has no flow across edge $(i, j)$. This is exhibited by edge $(a, c)$ above.
Wrap Up
In this post, we used gurobipy
to solve linear programming implementations of the Max-Flow and Min-Cut problems. For each problem, we were able to construct and visualize a solution to the other by accessing the constraint shadow price (i.e., dual variable) values. By jointly visualizing the Max-Flow and Min-Cut solutions, we were able to observe some implications of complementary slackness conditions that arise as a result of the two problems having a strong dual relationship.
You May Also Like
Max-Flow/Min-Cut Duality: Formulation & Theory
In the realm of algorithms and graph theory, two of the most famous …
Pyomo: Graphs and Blocks
I had the pleasure yesterday of presenting a follow-up tutorial within …
Introduction to Pyomo and Gurobipy
This morning, I had the honor of hosting a workshop on behalf of the …