We are given adjacency matrix representations of two flow networks. Each edge (i, j) is a directed edge from i to j. The capacity of each edge is given in the adjacency matrices. Node S represents the source and node T represents the sink in both the networks. Note that each capacity is an integer. Both the flow networks satisfy following properties
• Conservation of flow at each node except Source (i.e., Total incoming flow at a node must equal total outgoing flow at the node).
• For each edge, any flow respects the capacity constraint of the edge.
The assignment tasks are as follows
• Write a code for Simplex method(any variant) from scratch. (8 Marks)
• Formulate LPs for the flow-networks 1 and 2 to find out the maximum flow from S to T. (3 Marks)
• Take the Duals of each LP which corresponds to S−T Min-Cut in the respective network. (4 Marks)
• Write a code to solve all the LP’s(you formed) by simplex method (you coded). (2 Marks)
• Write the codes in AMPL to solve the LP’s (you formed). Show that min-cut is equal to max-flow (i.e, a LP and its dual have same optimal). Also Show that the solution you obtained by solving the LP are integral (Flow through each edge is an Integer). (3 Marks)
Network 1
S
A
B
C
D
T
S
0
16
13
0
0
0
A
0
0
10
12
0
0
B
0
4
0
0
14
0
C
0
0
9
0
0
20
D
0
0
0
7
0
7
T
0
0
0
0
0
0
Network 2
S
A
B
C
D
E
F
G
H
I
J
T
S
0
11
15
10
0
0
0
0
0
0
0
0
A
0
0
0
0
0
18
4
0
0
0
0
0
B
0
3
8
5
0
0
0
0
0
0
0
0
C
0
0
0
0
6
0
0
3
11
0
0
0
D
0
0
0
4
0
0
0
17
6
0
0
0
E
0
0
0
0
3
16
0
0
0
13
0
0
F
0
12
0
0
4
0
0
0
0
0
0
21
G
0
0
0
0
0
0
0
0
4
9
4
3
H
0
0
0
0
0
0
0
4
0
0
5
4
I
0
0
0
0
0
0
0
0
0
0
7
9
J
0
0
0
0
0
0
0
0
2
0
0
15
T
0
0
0
0
0
0
0
0
