COBRA: A New Formulation of the Classic p-Median Location Problem

The p-median problem was first formulated as an integer-linear programming problem by ReVelle and Swain (1970) and further revised by Rosing, ReVelle and Rosing-Vogelaar (1979). These two forms have withstood the test of time, as they have been used by virtually everyone since then. We prove that a property associated with geographical proximity makes it possible to eliminate many of the model variables through a substitution process. This new substitution technique has resulted in the elimination of up to 60% of the variables needed in either of these classic model formulations.