A note on solving large p-median problems (Q1060943)

In a previous paper by \textit{N. Christofides} and the author [ibid. 10, 196-204 (1982; Zbl 0481.90020)] we presented a tree search algorithm for the p-median problem, the problem of locating p facilities (medians) on a network, which was based upon Lagrangean relaxation and subgradient optimisation. That algorithm solved (optimally) problems with an arbitrary number of medians and having up to 200 vertices. In this note we show that it is possible to enhance that algorithm to solve (optimally) problems having up to 900 vertices using the Cray-1S computer.