Problem 6: Implementation Question (25 Points) In this question, the input is an undirected graph G = (V, E), costs Ce > 0 for all e E E, an integer parameter k, and a balance parameter a (0,1). We say that TT = (V,...,Vk) is a partition of V if 1. VU...UVk = V, and 2. Vin V; = 0, for all i + j. For a given partition 7, define 8(T) = {(u, v) E E:ue Vi and ve V, for some i # j} to be the set of edges whose endpoints lie in different parts of a. We say that a partition a is balanced if each part Vi of 7 has at least a V nodes. The goal is to find a balanced partition that minimizes c(8(T)). (i) [8 Points) Write an integer program for this question. Explain all variables and constraints! (ii) (17 Points) Implement this IP in Gurobi/Python. As in the previous assignment, your code should read in a graph in csv format. The header row of such a file is u, v, cost and all subsequent rows correspond to edges of the given graph. Your code should have tunable parameters k and a (e.g., these could be command line parameters). Your code should write its output into a csv file with header line: u, part number that has one line for each node in the graph. The line for node v is of the form v, where pnum is the part number in {1,..., k} of node v. Run your code on the provided file g1.csv. As before, provide python code file and solution csv and upload these to Learn. Naming conventions are: _.py __sol.csv Problem 6: Implementation Question (25 Points) In this question, the input is an undirected graph G = (V, E), costs Ce > 0 for all e E E, an integer parameter k, and a balance parameter a (0,1). We say that TT = (V,...,Vk) is a partition of V if 1. VU...UVk = V, and 2. Vin V; = 0, for all i + j. For a given partition 7, define 8(T) = {(u, v) E E:ue Vi and ve V, for some i # j} to be the set of edges whose endpoints lie in different parts of a. We say that a partition a is balanced if each part Vi of 7 has at least a V nodes. The goal is to find a balanced partition that minimizes c(8(T)). (i) [8 Points) Write an integer program for this question. Explain all variables and constraints! (ii) (17 Points) Implement this IP in Gurobi/Python. As in the previous assignment, your code should read in a graph in csv format. The header row of such a file is u, v, cost and all subsequent rows correspond to edges of the given graph. Your code should have tunable parameters k and a (e.g., these could be command line parameters). Your code should write its output into a csv file with header line: u, part number that has one line for each node in the graph. The line for node v is of the form v, where pnum is the part number in {1,..., k} of node v. Run your code on the provided file g1.csv. As before, provide python code file and solution csv and upload these to Learn. Naming conventions are: _.py __sol.csv