Consider the network shown in Figure 4.26. Numbers beside each node enclosed in a box (e.g., 10) are the demands associated with the node.
(a) Write out the objective function and constraints for the set covering model for this network when the coverage distance is 18. Assume that facilities can only be located on the nodes of the network.
(b) Which candidate sites can be excluded from the formulation? Which rows (corresponding to the need to cover specific demands) can be excluded? In both cases, justify your answer.
(c) After you have reduced the problem as suggested in part (b), are there any sites at which you must locate facilities? If so, where?
Why? If any sites are now forced into the solution, which demand nodes are now covered?
(d) Write out the remaining covering problem. That is, write out the constraint matrix for the remaining candidate sites and uncovered demand nodes.
(e) What is the linear programming relaxation solution to the original problem? Note that you should be able to solve for this using the matrix you obtain in part (d).
(f) What is the solution to the (integer programming) set covering problem? Specifically, where do you locate facilities and what is the objective function value?