An Efficient Exact Algorithm for the Vertex p-Center Problem

T. Ilhan (taylanibilkent.edu.tr)
M.C. Pinar (mustafapbilkent.edu.tr)

Abstract: Inspired by an algorithm due to Minieka, 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 it is assigned to. After a lower bounding phase, the algorithm iteratively sets a maximum distance value within which it tries to assign all clients, and thus solves integer feasibility subproblems. Excellent computational results are reported on a set of 84 test problems derived from OR-Lib and TSP-Lib problem instances with up to 900 vertices, solved to optimality for the first time.

Keywords: Integer Programming, p-center problem, facility location

Category 1: Integer Programming (0-1 Programming )

Citation: Bilkent University Technical Report, Department of Industrial Engineering 06533 Ankara Turkey

Download: [Postscript]

Entry Submitted: 09/27/2001
Entry Accepted: 09/27/2001
Entry Last Modified: 09/27/2001

Modify/Update this entry