An Exact Algorithm for the Capacitated Vertex p-Center Problem

F.A. Ozsoy (aykutbilkent.edu.tr)
M.C. Pinar (mustafapbilkent.edu.tr)

Abstract: We develop a simple and practical exact algorithm for the problem of locating $p$ facilities and assigning clients to them within capacity restrictions in order to minimize the maximum distance between a client and the facility to which it is assigned (capacitated $p$-center). The algorithm iteratively sets a maximum distance value within which it tries to assign all clients, and thus solves bin-packing or capacitated concentrator location subproblems using off-the-shelf optimization software. Experiments on OR-Lib instances yield promising results.

Keywords: Integer programming, capacitated p-center

Category 1: Integer Programming (0-1 Programming )

Category 2: Applications -- OR and Management Sciences (Production and Logistics )

Citation: Technical Report, Department of Industrial Eng. Bilkent University

Download: [Postscript]

Entry Submitted: 09/15/2003
Entry Accepted: 09/15/2003
Entry Last Modified: 09/15/2003

Modify/Update this entry