In this exercise, you will use the SITATION program and the Lagrangian relaxation algorithm for solving the maximum covering location problem that is built into that package to do a simple branch-andbound analysis. The data set for the problem is the 88-node problem for the United States given online. This data set is called CITY1990. GRT.
One of the purposes of this exercise is to explore the implications of different solution procedures on the quality of the solution. In general, the Lagrangian procedure will give better results than those obtained by the greedy adding algorithm (or the greedy adding and substitution algorithm). This, however, is not always the case.
(a) For a coverage distance of 300, use the greedy adding algorithm with substitution allowed after each iteration (excluding dominated sites) to find the (approximate) maximum number of demands that can be covered by locating three facilities. Use the first demand data set. How many demands are covered in total? Where does the algorithm suggest locating facilities?
(b) Now do the same thing, but use the Lagrangian relaxation algorithm. Again, exclude dominated sites and allow substitution at the end of the procedure. Let the model locate three facilities. (Do not change any of the Lagrangian options on the OPTION SETTING MENU. However, turn off the branch and bound option in the Lagrangian settings for the remainder of this problem.) Again, how many demands are covered in total? Where does the algorithm suggest locating facilities? How does the total covered demand in this case compare with:
i. the upper bound on the coverage provided by the Lagrangian procedure and
ii. the coverage found by the greedy adding and substitution algorithm in part (a)?
(c) Verify that the three sites found in part (b) must be optimal. Do so by using the upper bounds available from the Lagrangian relaxation algorithm when you exclude each of these three sites one by one from the solution. Note that you will have to use the Force Specific Sites In/Out of Soln. option that is available on the main menu to force each site in turn out of the solution and then run the Lagrangian relaxation procedure. In all you will need to run the Lagrangian procedure a number of different times. Clearly show the upper bound obtained from each of these runs. Briefly explain why these runs show that the optimal solution is to locate at the three nodes you found in part (b).
(d) Return to the MAIN OPTION MENU and be sure that all candidate sites are allowed in the solution. (To do so, use the P option from the FORCE NODES OPTION MENU.) Now generate the covering trade off curve using the T option from the MAIN OPTION MENU. Allow substitution after each iteration and exclude dominated nodes.
i. How many facilities does the heuristic think are needed to cover all 88 nodes?
ii. Looking carefully at the trade off curve developed by the algorithm and at the incremental coverages, which of the solutions are likely to be suboptimal and why?
(e) Based on what you have done so far and learned so far about the differences between the greedy adding and substitution algorithm and Lagrangian relaxation, find the true minimum number of facilities needed to cover all demands. Note that to do so, you will need to change some of the options on the Lagrangian OPTION SETTING MENU that you are shown when you run the Lagrangian relaxation algorithm. You may also need to force some nodes into or out of the solution. In short, this will require considerable experimentation and work. Clearly document how you obtained the optimal solution and how you can show that fewer facilities cannot cover all of the demands.