Computation Organization

3. {12 marks} Recall the fire station problem from assignment 3. A graph G = (V, E) is given where V is a set of communities, and two communities are adjacent if and only if a fire station from one community can reach the other community within a reasonable time. The goal is to set up a fire station in a number of communities such that all communities can be reached by some fire station within a reasonable time. We want to do so while minimizing the total number of fire stations that we set up. We can formulate this problem using the following integer program (IP): min (tu : VEV) s.t. 2 + (xw : vw E) >1 Wue V x > 0 X, EZ VvE V Consider the following graph G for our problem. (a) Write down the linear programming relaxation (P) for this specific graph. You need to write out the full constraints. Make sure you list your constraints and variables in alphabetical order of the vertex labels. You can write in matrix form. (b) Write down the dual (D) of the linear program (P) in part (a). (c) Determine a feasible solution to (D) with objective value greater than 2. Give a brief explanation of why your solution is feasible. (Hint: Consider a fractional solution where every entry is identical.) (d) Find a solution to (IP) with objective value 3, and use the theory of linear programming duality to prove that this is an optimal solution to the (IP)