An Efficient Exact Algorithm for the Vertex $p$-Center Problem and Computational Experiments for Different Set Covering Subproblems

T. Ilhan (t-ilhannorthwestern.edu)
F.A. Ozsoy (aykutbilkent.edu.tr)
M.C. Pinar (mustafapbilkent.edu.tr)

Abstract: We develop a simple and yet very efficient exact algorithm for the problem of locating $p$ facilities and assigning clients to them in order to minimize the maximum distance between a client and the facility to which it is assigned. The algorithm iteratively sets a maximum distance value within which it tries to assign all clients, and thus solves set covering subproblems. Three different set covering problems are incorporated and excellent computational results are reported for each on a long list of test problems derived from OR-Lib and TSP-Lib problems with up to 900 data points.

Keywords: Integer programming, p-center problem, facility location.

Category 1: Integer Programming (0-1 Programming )

Citation: Bilkent University, Department of Industrial Engineering, Technical Report, November 2002.

Download: [Postscript]

Entry Submitted: 12/30/2002
Entry Accepted: 12/30/2002
Entry Last Modified: 12/30/2002

Modify/Update this entry