In this paper, we use a pseudo‐Boolean formulation of the p‐median problem and using data aggregation, provide a compact representation of p‐median problem instances. We provide computational results to demonstrate this compactification in benchmark instances. We then use our representation to explain why some p‐median problem instances are more difficult to solve to optimality than other instances of the same size. We also derive a preprocessing rule based on our formulation, and describe equivalent p‐median problem instances, which are identical sized instances which are guaranteed to have identical optimal solutions.
