Discrete equal-capacity p-median problem

This paper examines the discrete equal-capacity p-median problem that seeks to locate p new facilities (medians) on a network, each having a given uni form capacity, in order to minimize the sum of distribution costs while sat isfying the demand on the network. Such problems arise, for example, in loc al access and transport area telecommunication network design problems when any number of a set of p facility units can be constructed at the specifie d candidate sites (hence, the net capacity is an integer multiple of a give n unit capacity). We develop various valid inequalities, a separation routi ne for generating cutting planes that are specific members of such inequali ties, as well as an enhanced reformulation that constructs a partial convex hull representation that subsumes an entire class of valid inequalities vi a its linear programming relaxation. We also propose suitable heuristic Sch emes for this problem, based on sequentially rounding the continuous relaxa tion solutions obtained for the various equivalent formulations of the prob lem. Extensive computational results are provided to demonstrate the effect iveness of the proposed valid inequalities, enhanced formulations, and heur istic schemes. The results indicate that the proposed schemes for tightenin g the underlying relaxations play a significant role in enhancing the perfo rmance of both exact and heuristic solution methods for this class of probl ems. (C) 2000 John Wiley & Sons, Inc.