Consider the network shown in Figure 4.25:
(a) Solve the set covering location problem with all fixed costs equal to 1 (fj
= 1 for all j) and a critical distance of 14 (Dc
= 14).
Assume that facilities may only be located on the nodes of the network. Give the set of (node) locations that cover all other nodes. Also, clearly show which candidate facility sites are dominated by which other sites.
(b) Now consider the set covering location problem with all fixed costs equal to 1 (f
j
= 1 for all j) and a critical distance of 30 (Dc
= 30). Again, assume that facilities may only be located on the nodes of the network.
i. Clearly show which candidate facility sites are dominated by which other sites.
ii. Clearly indicate which rows of the constraint matrix can be eliminated.
iii. Solve the resulting problem as a linear programming problem. Note that the problem should be very small and you should be able to solve it by hand if you do not have any other linear programming solver available.
Note: Solving this problem may be more difficult than solving part (a) was. First, you must consider cases in which nodes are covered by facilities that are not directly linked to the facility node. For example, demands at node J can be covered by a facility at node A with a coverage distance of 30. Second, if you do this right, the resulting linear programming problem will not give you an all-integer solution.
iv. Find an all-integer solution to the problem. Explain any additional constraints that you add to the linear programming relaxation to force the solution to give you an all-integer solution.