Double bound method for solving the p-center location problem

We give a review of existing methods for solving the absolute and vertex restricted p-center problems on networks and propose a new integer programming formulation, a tightened version of this formulation and a new method based on successive restrictions of the new formulation. A specialization of the new method with two-element restrictions obtains the optimal p-center solution by solving a series of simple structured integer programs in recognition form. This specialization is called the double bound method. A relaxation of the proposed formulation gives the tightest known lower bound in the literature (obtained earlier by Elloumi et al., 1]). A polynomial time algorithm is presented to compute this bound. New lower and upper bounds are proposed. Problems from the OR-Library 2] and TSPLIB 3] are solved by the proposed algorithms with up to 3038 nodes. Previous computational results were restricted to networks with at most 1817 nodes.