Consider the network shown in Figure 1, where the triplet of numbers on each arc represents per unit flow cost, upper bound on flow, and lower bound on flow. Node 1 has an exogenous flow of 4, node 4 has an exogenous flow of -4, and all other exogenous flows are zero.
1. Consider the min cost flow problem created by deleting the (dashed) arc (2,3) from Figure 1. Use the min cost augmenting flow method to solve this problem. Show the steps of your work, but feel free to omit Bellman-Ford iterations.
2. Now consider the min cost flow problem with the (dashed) arc (2,3). Use the cycle canceling method to solve this problem. Show the steps of your work, but feel free to omit Bellman-Ford iterations.
3. Now consider a variant of the min-cost flow problem, again referencing Figure 1. The problem is defined as usual, except that a fixed cost of 2 must be paid if any positive flow is sent along the arc (2,3). Note that the fixed cost is in addition to variable (or per unit) cost of flow along that arc. Formulate the problem of finding the minimum cost feasible flow as a mixed integer programming problem that has a single integer variable.
