Capacitated p-center problem (CPCP)

Raphael Kramer*, Manuel Iori*, and Thibaut Vidal+
*DISMI, University of Modena and Reggio Emilia, 42100 Reggio Emilia, Italy.
+Departamento de Informįtica, Pontifķcia Universidade Católica do Rio de Janeiro, Rio de Janeiro, Brazil.


The capacitated p-center problem (CPCP) is defined as follows. Let G = (F, C, E) be a bipartite graph, where F = {1, . . . , m} and C = {1, . . . , n} are the sets of candidate locations and customer nodes, respectively, and E = {(i, j) : i ∈ F, j ∈ C} is the set of edges. Each edge (i, j) ∈ E represents a possible assignment of a customer j to a facility i and has a non-negative distance dij. Each facility i ∈ F has a capacity Qi, which can be used to supply the demands qj of customers j ∈ C. The CPCP aims at opening at most p facilities and assigning each customer to exactly one facility, seeking to minimize the maximum distance between a customer and its facility, and ensuring that the total demand of the customers assigned to each facility does not exceed its capacity.

Key words

Capacitated p-center, mathematical models, valid inequalities, search algorithms.