Use the approach outlined in Exercise 7.2 to
(a) Solve for the set covering solution to the 12-node problem of Figure
7.4 when all facility costs are equal. (Set them equal to 100.) Use a covering distance of 30 as in part (c) of Exercise 7.2.
(b) Why are the lower and upper bounds so far apart in your solution to part (a)?
(c) What does the value of the lower bound suggest to you about the linear programming relaxation of the problem? In particular, can you find a solution to the linear programming relaxation of this instance of the set covering problem that has an objective function equal to the lower bound computed by the Lagrangian procedure? If so, what is that solution?
(d) How can you use the constraint discussed in Exercise 7.3 to help tighten the bound? Using this approach, where does SITATION tell you to locate facilities?
Exercise 7.2.
In Chapter 4 we discussed the set covering problem under the assumption that all facility costs were identical. In that case, minimizing the total cost of the selected facilities becomes identical to minimizing the total number of facilities. In many cases, however, the facility costs are not identical. We indicated that the set covering objective function would then be changed to
MINIMIZE
Where
fj
= the fixed cost of locating at candidate site j
J
Xj
=1 if candidate site j 2 J is selected
0 if not
(a) Show how this extension of the set covering problem can be formulated as a fixed charge facility location problem.
(b) Do any of the row and column reduction rules discussed in Chapter 4 for the set covering problem with identical facility costs apply to this extended problem? If so, which ones? For those that do not apply, justify why they do not work in this case.
(c) For the 12-node network of Figure 7.4 and a covering distance of 30, solve this extension of the set covering problem using the SITATION program. Use the NET-SPEC program to create a 12-node problem suitable for use in SITATION. This will also create a distance file, MDST12.NET. Then use the MOD-DIST program to change the distances in the MDST12.NET file appropriately before running SITATION.