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.

A scalable exact algorithm for the vertex p-center problem / Contardo, Claudio; Iori, Manuel; Kramer, Raphael. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 103:(2019), pp. 211-220. [10.1016/j.cor.2018.11.006]

A scalable exact algorithm for the vertex p-center problem

Iori, Manuel;Kramer, Raphael
2019

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.
2019
103
211
220
A scalable exact algorithm for the vertex p-center problem / Contardo, Claudio; Iori, Manuel; Kramer, Raphael. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 103:(2019), pp. 211-220. [10.1016/j.cor.2018.11.006]
Contardo, Claudio; Iori, Manuel; Kramer, Raphael
File in questo prodotto:
File Dimensione Formato  
1803.04865.pdf

Open access

Descrizione: Versione pre print
Tipologia: Versione originale dell'autore proposta per la pubblicazione
Dimensione 342.03 kB
Formato Adobe PDF
342.03 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1168936
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 32
  • ???jsp.display-item.citation.isi??? 27
social impact