3. Using AMPL to formulate and solve the MIP models

A company has 4 branches in one city and plans to move some of them to another city. The th branch costs a; per year if it stays in the original city and bi per year if it is moved to the new city. The company also needs to pay an extra Cij per year for traveling between branches i and j if they are not in the same city. The company must decide which branches should be moved to the new city in order to minimize the total yearly cost. The costs ai, b; and Cij are given in the following table. 1 b; 80 2 130 3 4 110 210 10 i ai 1 120 2 90 3 150 4 170 Cij 15 15 5 10 20 15 20 5 20 25 10 1. Formulate this problem as a maximum flow problem (Hint: In this problem, you will care more about the minimum cut than the maximum flow). In particular, you should draw the vertices and arcs of the network. You should also clearly indicate the capacity of each arc, together with the source and the sink of the maximum flow problem. 2. Use Ford-Fulkerson's algorithm to solve this maximum flow problem starting from the zero-flow. Draw a new residual network after each iteration you perform A company has 4 branches in one city and plans to move some of them to another city. The th branch costs a; per year if it stays in the original city and bi per year if it is moved to the new city. The company also needs to pay an extra Cij per year for traveling between branches i and j if they are not in the same city. The company must decide which branches should be moved to the new city in order to minimize the total yearly cost. The costs ai, b; and Cij are given in the following table. 1 b; 80 2 130 3 4 110 210 10 i ai 1 120 2 90 3 150 4 170 Cij 15 15 5 10 20 15 20 5 20 25 10 1. Formulate this problem as a maximum flow problem (Hint: In this problem, you will care more about the minimum cut than the maximum flow). In particular, you should draw the vertices and arcs of the network. You should also clearly indicate the capacity of each arc, together with the source and the sink of the maximum flow problem. 2. Use Ford-Fulkerson's algorithm to solve this maximum flow problem starting from the zero-flow. Draw a new residual network after each iteration you perform