The paper is aimed at experimental evaluation of the complexity of the p-Median problem instances, defined by m Γ n costs matrices, from several of the most widely used libraries. The complexity is considered in terms of possible problem size reduction and preprocessing, irrespective of the solution algorithm. We use a pseudo-Boolean representation of PMP instances that allows several reduction techniques to be applied in a straightforward way: combining similar monomials in the polynomial, truncation of the polynomial from degree (m -1) to (mp) implying costs matrix truncation and exclusion of some rows from the costs matrix (preprocessing based only on compactification of the costs matrix), decomposition of the polynomial into the minimum number of expressions inducing the minimum number of aggregated columns (reduction of the columns' number in the costs matrix). We show that the reduced instance has at most
nonzero entries. We also provide results of computational experiments with the mentioned reductions that allow classification of the benchmark data complexity. Finally, we propose a new benchmark library of instances not amenable to size reduction by means of data compactification.