The p-median problem is perhaps one of the most well-known location–allocation models in the location science literature. One element of past research that has remained almost constant is the original ReVelle–Swain formulation. This paper proposes a new model formulation for the p-median problem that contains both exact and approximate features. This new p-median formulation is called Both Exact and Approximate Model Representation (BEAMR). We show that BEAMR can result in a substantially smaller integer-linear formulation for a given application of the p-median problem and can be used to solve for either an exact optimum or a bounded, close to optimal solution.