A scalable exact algorithm for the vertex p-center problem. (March 2019)

• Record Type: Journal Article
• Authors: Contardo, Claudio; Iori, Manuel; Kramer, Raphael
• Is Part Of: Computers & operations research. Volume 103(2019)
• Page Start: 211
• Page End: 220
• Publication Date: 2019-03
• Subjects: p-center problem -- Clustering -- Facility location -- Relaxation algorithm; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.11.006
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We introduce a scalable exact algorithm for the vertex p-center problem. An efficient procedure to update the subproblems is proposed. Instances containing up to one million clients are solved to optimality. Abstract: The vertex p -center problem consists in selecting p centers among a finite set of candidates and assigning a set of clients to them, with the aim of minimizing the maximum dissimilarity between a client and its associated center. State-of-the-art algorithms for the problem are based on the solution of a series of covering subproblems, and are particularly efficient when additional reduction rules are used to limit the size of the subproblems. In fact, these algorithms do not scale well when the cardinality of the dissimilarity matrix grows above a few million entries, as the time and space required to compute and store the matrix start dominating those required for solving the subproblems. We introduce a scalable relaxation-based iterative algorithm that does not rely on the computation of the entire matrix, but rather relies on the computation of a typically much smaller sub-matrix that is only enlarged if deemed necessary. This method can solve to proven optimality p -center problems derived from the TSP library and containing up to one million clients for small but realistic values of p .