Question

The dual of maximum flow. Consider the following network with edge capacities

(a) Write the problem of finding the maximum flow from $\mathbf{S}\mathbf{to}\mathbf{T}$as a linear program.

(b) Write down the dual of this linear program. There should be a dual variable for each edge of the network and for each vertex other than $\mathbf{S},\mathbf{T}.$

Now we’ll solve the same problem in full generality. Recall the linear program for a general maximum flow problem (Section 7.2).

(c) Write down the dual of this general flow LP, using a variable${\mathit{y}}_{\mathbf{e}}$for each edge and ${\mathbf{x}}_{\mathbf{u}}$for each vertex$\mathbf{u}\ne \mathbf{s},\mathbf{t}.$

(d) Show that any solution to the general dual LP must satisfy the following property: for any directed path from in the network, the sum of the ${\mathit{y}}_{\mathbf{e}}$values along the path must be at least $\mathbf{1}$.

(e) What are the intuitive meanings of the dual variables? Show that any$\mathbf{s}\mathbf{-}\mathbf{t}$cut in the network can be translated into a dual feasible solution whose cost is exactly the capacity of that cut.

Short answer

a)The maximum flow from$\mathrm{S}\mathrm{to}\mathrm{T}$ as a linear program is given below.

b)The dual of this linear program is defined below.

c)The dual of this general flow LP, using a variable${\mathrm{y}}_{\mathrm{e}}$ for each edge and${\mathrm{x}}_{\mathrm{u}}$ for each vertex$\mathrm{u}\ne \mathrm{s},\mathrm{t}.$ is proved.

d)For any directed path from$\mathrm{S}\mathrm{to}\mathrm{T}$ in the network, the sum of the values$y_e$ along the path must be at least one is proved.

e) The network can be translated into a dual feasible solution whose cost is exactly the capacity of that cut is given below.

Step-by-step solution

Maximum Flow Diagram of Following Network

a).

There are different graph show the different network connectivity base of figures but calculation show all diagram is concern with same theory of flow which is LP. The final and the maximum flow of the directed graph is defined as$S\to A\to B\to T$:

And its flow is defined as,$Flow=flow+1$

Here, the problem of finding the maximum flow from$StoT$as a linear program

In this graph given a directed graph contain minimal spanning tree (MST as a minimum spanning tree) is a subgroup of something like a tree that has the shortest packets from the source to all of its vertex points. A graph $G=(V,E)$Some minimum spanning tree is shown, along with edge weights that are positive. $T=(V,E)$ such as relation to all of these weights. Take a look at the clustering lists. Graph$G$ and$T$ are supplied. After this step suppose that a particular edge’s weight is altered from$w\left(e\right)$ to $w\text{'}\left(e\right)$.

Here, the source or the starting vertex is s and the sink called as the end vertex is T here the shortest path covered in the graph is defined below, the second graph is called as residual graph. in the first graph a network is defined from source vertex to the sink node.

The final and the maximum flow of the directed graph is defined as:

$S\to A\to B\to T$

$Flow=flow+1$

Dual of this linear program.

b)

The dual of this linear program, And here should be a dual variable for each edge of the network and for each vertex other than $S,T.$

The dual problem of this graph is defined as, And here should be a dual variable for each edge of the network and for each vertex other than $A,B$vertices.

The networks we are dealing with consist of a directed graph $G=(V,E);$

Two special nodes $s,t\in V$, which are, respectively, a source and sink of $G$; and capacities $ce>0$on the edges. We would like to send as much oil as possible without exceeding the capacities of any of the edges.

A particular shipping scheme is called a flow and consists of a variable for each edge e of the network, satisfying the following two properties:

1. It doesn’t violate edge capacities:

$0\le fe\le ceforalle\in E.$

For all node the amount of flow entering u equals the amount leaving :

$X(w,u)\in Efwu=X(u,z)\in Efuz.$

In other words, flow is conserved. The size of a flow is the total quantity sent from s to t and, by the conservation principle, is equal to the quantity leaving

$s:size\left(f\right)=X(s,u)\in Efsu.$

In short, our goal is to assign values to that will satisfy a set of linear constraints and maximize a linear objective function. But this is a linear program .The maximum-flow problem reduces to linear programming.

The dual problem of this graph is defined as, And here should be a dual variable for each edge of the network and for each vertex other than vertices

Dual Problem:

$Min\sum C_e{y}_e$

$s:size\left(f\right)=X(s,u)\in Efsu.$

$s.tz{}_w-z_v+y_e>0$ ,

$0\le fe\le ceforalle\in E.$

$Z_s=1$ ,$Z_s=0$ ,

$y_e\ge 0$

Step 3: The general flow LP.

c)

The dual of this general flow LP, by using a variable $y_e$for each edge and $x_u$for each vertex$u\ne s,t.$is defined as, in the graph four vertices and five edges are given where the maximum flow path is evaluated as $S\to A\to B\to T$and the flow is given as, $Flow=flow+1$

.

Analyse how minimum spanning t until one of the edges is heavier than the other$e\notin E\text{'}$. And itis increased Let$e=(u,v)$and just let the subtrees that were created by deleting them$e$be $T_v$and.$T_u$ With BFS (breadth first search )(ignoring weights of edges) , It really is possible to detect whichever vertices are all in the$T_u$ and which are in$T_v$ .

Assume each node is marked with its membership.

Each edge is checked and edge $e\text{'}$with having one endpoint $T_u$and$T_v$having the other only are kept.

Hence, the general flow is defined as,

.$Flow=flow+1$

In the manner of $S\to A\to B\to T$.

This statement is proved.

d)

A solution to the general dual LP must satisfy the following property: for any directed path from$stot$ in the network, the sum of the $y_e$values along the path must be at least $1$.

And here no more path left :

Implementation :

An augmenting path in residual graph can be follow using DFS (depth first search) and BFS (breadth first search). Duality of Linear programming:

Prinet problem:

$z_p=max\left\{C^{t}x\right|A_x{S}_b,x\in R^n\}$

Dual Problem:

$W_o=min\left\{b^{t}u\right|A^{t}u=c,u\ge o\}$

Maximum Flow and Duality:

Primal problem:

$Max{\sum }_{e.source\left(a\right)=}{}_{S}x_e-{\sum }_{e.taged\left(a\right)=}{}_{S}x_e$

$s.t{\sum }_{\text{e.source(a)V}}\text{-}{\sum }_{\text{e.taged(e)=}{}_{\text{V}}\text{X}_{\text{e}}}=0$

$0\le x_e\le C_e$

Step 5: Network into a dual feasible solution.

e).

The intuitive meanings of the dual variables that any $s-t$cut in the network can be translated into a dual feasible solution whose cost is exactly the capacity of that cut.

Dual Problem:

$Min\sum C_e{y}_e$,$s.tz{}_w-z_v+y_e>0$

$Z_s=1$,$Z_s=0$

$y_e\ge 0$

Maximum Flow & Duality:

1). Let ($y^u$,$z^u$) be an optimal solution of dual

2). ($S$,$T$) is a minimum cut.

3). Max flow min cut there is special case of LP duality.