p-Median Problems

One of the basic problems in the field of discrete location is the p-median problem. In this chapter we present and analyze several versions of the problem, but we can roughly define it as the choice of p facilities, among a set of n candidates, that minimize the cost of supplying a finite set of users. The p chosen facilities are usually called medians. Since the nature of the problem is combinatorial, integer programming is the common framework in which the problem is studied. Hence different formulations and their polyhedral properties constitute the kernel of this chapter. The study of the problem on a graph and heuristic procedures are treated in separate sections. Necessarily and unfortunately, we have to overlook many important references and results in the literature in the interest of legibility. Extensions of the problem, also of great interest, are covered in subsequent chapters and therefore are also ignored here. A companion problem of unquestionable importance, the Simple Plant Location Problem, is one of the main subjects of Chap. 4. Consequently, we have paid only little attention to it in our discussion.