In trying to solve the vertex 4-center problem for the 88-node data set (CITY1990.GRT)—which has a total demand of 44,840,571—I obtained the following results with a coverage distance of 650. Branch and bound was turned off.
(a) With no nodes forced in or out of the solution, the Lagrangian upper bound is 44,840,571 and the lower bound is 44,385,925. Facilities are located at nodes 23, 29, 71, and 78.
(b) With node 23 (the node which covers the most demand in the solution above) forced out of the solution, the Lagrangian upper bound is 44,760,066 and the lower bound is 44,757,084. Facilities are located at nodes 48, 59, 74, and 78.
(c) With node 23 forced into the solution, the Lagrangian upper bound is 44,630,491 and the lower bound is 44,482,023. Facilities are located at nodes 18, 23, 26, and 78.
With this information what can you say about the optimal solution to the 4-center problem? Be as specific as possible. You might want to confirm your answer using the SITATION program.