(a) For the network shown above in Exercise 4.11, write out the set covering problem formulation for a coverage distance of 34.
(b) For the problem formulated in part (a), can you eliminate any columns (e.g., force out any nodes)? Can any nodes be forced in? Can any rows be eliminated? After forcing in and out any nodes that can be forced in this way and eliminating any rows, find an optimal solution to the problem.
(c) What if anything does your solution tell you about the results you obtained in part (b) of Exercise 4.11?
The vertex P-center problem is the problem of finding P locations on the nodes of the network to minimize the maximum distance between any demand node and the nearest facility to it. The objective function of the P-center problem is to minimize this maximum (implied coverage) distance. This model is discussed in detail in Chapter 5. However, you should be able to answer the following two questions:
(d) What, if anything, does your solution tell you about the objective function for the 3-center problem?
(e) What, if anything, does your solution tell you about the objective function for the 2-center problem?
Exercise 4.11
Consider the network shown in Figure 4.27. Link distances are shown beside the links and the demands are shown in boxes beside each node.
(a) Use the greedy adding algorithm to solve the maximum covering problem for this network with a coverage distance of 34 and a single facility. Assume you can only locate on the nodes of the network. In particular, where do you locate? How many demands are covered? Which nodes are covered and which are not?
(b) For a coverage distance of 34 use the greedy adding algorithm (without substitution) for the maximum covering problem to complete the following table:
1. You may want to set up a table showing how much demand each candidate location covers.
2. Remember that even once a demand node is covered it may still be considered as a candidate facility site.
3. You may not need all rows of the table.