MaxFlow/MinCut Duality: Implementation & Visualization
In a previous post, we discussed the strong dual relationship between the MaxFlow and MinCut 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 FordFulkerson 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’ primaldual relationships.
This post is part 2 of a 2part series. This part focuses on LP implementations of the MaxFlow and MinCut 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 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 MaxFlow 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 nontrivial solution (i.e., \(z_p^* > 0\)). Using this notation, we presented the following LP formulation of MaxFlow: \[ \begin{aligned} z_p^* = \max~~ & x_{ts} && \\ \text{s.t.}~~ & \sum_{j \in \hat{V}_i^+} x_{ji}  \sum_{j \in \hat{V}_i^} x_{ij} = 0, && \forall i \in V, \\ & x_{ij} \le c_{ij}, && \forall (i, j) \in E, \\ & x_{ij} \in \mathbb{R}_+, && \forall (i, j) \in \hat{E}. \end{aligned} \]
Its dual, an LP relaxation of the MinCut integer program, is \[ \begin{aligned} z_d^* = \min~~ & \sum_{(i, j) \in E} c_{ij} y_{ij} && \\ \text{s.t.}~~ & y_{ij} \ge z_i  z_j, && \forall (i, j) \in E, \\ & z_s  z_t \ge 1, && \\ & y_{ij} \in \mathbb{R}_+, && \forall (i, j) \in E, \\ & z_i \in \mathbb{R}, && \forall i \in V. \end{aligned} \]
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^\). Which 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 MinCut is given below.


con_x
in the dual represents the separationenforcing 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 MaxFlow
We conclude by visualizing the optimal solutions to these problems that were identified by the Gurobi solver. Each visualization shows both the MaxFlow and MinCut solutions. To show the MaxFlow 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 MinCut 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 MaxFlow solution values via x[i].X
and the MinCut 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 MaxFlow solution leverages all but one of the edges – edge \((a, c)\) – and achieves a flow of 20 from \(s\) to \(t\). The corresponding optimal MinCut 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 MaxFlow problem or \(y_{ij}^* = 0\) in the MinCut problem (or both). That is, if an edge participates in the cut of an optimal MinCut solution, then its flow is equal to its capacity in the corresponding optimal MaxFlow solution.
Visualization via MinCut
The code for visualizing the solutions by way of solving the MinCut problem is much the same. The only differences are that we retrieve the MaxFlow solution values via con_x[i].Pi
and the MinCut solution values via y[i, j].X
and z[i].X
. The code and resulting illustration are both shown below.


The identified optimal MaxFlow solution again leverages all but edge \((a, c)\); however, a few glances backandforth with the previous illustration are enough to see that the MaxFlow 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 MinCut 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 primaldual pair of optimal solutions when it solved MinCut versus when it solved MaxFlow. In solutions identified solving MinCut, another implication of complementary slackness is evidenced. Either \(x_{ij}^* = 0\) in the MaxFlow problem or \({y_{ij}^* = z_i^*  z_j^* }\) in the MinCut problem (or both). So for edge \((i, j)\), if the optimal MinCut solution bipartitions the vertices with \({\{j, s\} \subseteq A}\) and \({\{i, t\} \subseteq B}\), then the corresponding optimal MaxFlow 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 MaxFlow and MinCut 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 MaxFlow and MinCut 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
MaxFlow/MinCut 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 followup tutorial within …
Introduction to Pyomo and Gurobipy
This morning, I had the honor of hosting a workshop on behalf of the …