Consider the following MCNF problem with feasible flow x.

c) Use the residual network to check whether the network contains a negative cost cycle(s) or whether it is optimal. If you find a negative cost cycle, determine the nodes in the cycle and the capacity of the cycle d) Use MPL to find the optimal solution Problem 1 (25 points) (Flow Decomposition Algorithm) Consider the following MCNF problem with feasible flow x .1 (2,8,12) 4,5,7) a) Decompose the flows on the arcs into flows along directed paths or/and along directed cycles Assume that you use an adjacency list where the heads of the arcs are in increasing order b) Draw the residual network with respect to the initial feasible flow c) Use the residual network to check whether the network contains a negative cost cycle(s) or whether it is optimal. If you find a negative cost cycle, determine the nodes in the cycle and the capacity of the cycle d) Use MPL to find the optimal solution Problem 1 (25 points) (Flow Decomposition Algorithm) Consider the following MCNF problem with feasible flow x .1 (2,8,12) 4,5,7) a) Decompose the flows on the arcs into flows along directed paths or/and along directed cycles Assume that you use an adjacency list where the heads of the arcs are in increasing order b) Draw the residual network with respect to the initial feasible flow