In general, we would expect that the trade off curve of the percentage of the total demand covered versus the number of facilities located will be concave. In other words, we generally expect that we will have decreasing marginal or incremental coverage. However, this is not always the case.
In this exercise, you will solve a series of maximum covering problems using SITATION. You will use the 88-node data set, CITY1990 .GRT. In addition, you will limit the candidate sites to the capitals of the 48 states in the continental United States plus Washington, DC. You will use a coverage distance of 550 miles. The easiest way to do this is to:
i. Load CITY1990.GRT (by pressing L at the MAIN OPTION MENU, G at the DISTANCE OPTIONS MENU, typing CITY1990.GRT as the file name to read);
ii. Limit the candidate sites to those in the file CAPITALS.FOR (by pressing S at the MAIN OPTION MENU, F at the SET PARAMETERS MENU, R at the FORCE NODES OPTION MENU, CAPITALS.ONL when prompted for the file name to read, and C at the FORCE NODES OPTION MENU to return to the SET PARAMETERS MENU);
iii. Set the coverage distance to 550 miles and the cost per mile to 0.001 in the SET PARAMETERS menu. Then type D to return to the MAIN OPTION MENU).
(a) Find the optimal solution to the maximum covering problem locating three facilities. Do so using the Lagrangian algorithm. Set the Lagrangian options as follows to force the algorithm to obtain very tight bounds:
In addition, allow substitution at the end of the Lagrangian algorithm and exclude dominated nodes. What are the values of the lower and upper bounds on the coverage? Where do you locate facilities? Is the solution provably optimal?
(b) Find the optimal solution to the maximum covering problem locating five facilities. Use the same parameter values for the Lagrangian problem that you used in part (a). What are the values of the lower and upper bounds on the coverage? Where do you locate facilities? Is the solution provably optimal?
(c) If you did parts (a) and (b) correctly, you should have obtained provably optimal solutions (since all of the demands are integer valued). Assuming the trade off curve does exhibit decreasing marginal coverage, what is the minimum coverage that we must attain with four facilities?
(d) Use the Lagrangian procedure to solve the problem locating four facilities. Again, use the same Lagrangian parameters you used in part (a). What are the lower and upper bounds on the coverage? Where do you locate the four facilities? Is the solution provably optimal? How many demands are covered by each of the four facilities?
(e) Exclude the node that covers the most demand in the four-facility solution found in part (d) from the solution.
Run the Lagrangian algorithm again locating four facilities. What are the lower and upper bounds on the coverage now? Comparing the bounds to the value you computed in part (c), what can you conclude about whether the node you excluded must be in or out of the solution if the trade off curve is to exhibit decreasing marginal coverage? Why?
(f) Force the node that covers the most demand in the four-facility solution found in part (d) into the solution.
Run the Lagrangian algorithm again locating four facilities. Now what are the lower and upper bounds on the coverage? Comparing the bounds to the value you computed in part (c) and using the knowledge you obtained in part (e), what can you conclude about whether the trade off curve exhibits decreasing marginal coverage? Why?
(g) In parts (d)–(f) you essentially walked through part of a branch-andbound tree. Draw the tree showing the lower and upper bounds on the problem in each node of the tree and the facility location that was forced into or out of the solution on each link of the tree.