Considered is the problem of selecting p out of n given points in some space, such that the minimum distance between pairs of selected points is maximized. This objective may be appropriate if the selected points correspond to facility sites and the objective is to have as ‘dispersed’ a set as possible. This problem is NP-complete. Related graph theoretical problems are discussed, integer programming models are proposed, and an outline is given on a line search procedure to solve this problem optimally. Using a branch-and-bound procedure, problems with n=40 and p=16 can be solved on a microcomputer. The heuristic, developed to get an initial lower bound, finds an optimal solution for most of the present random test problems. Also described is an extension to the basic problem that allows for preselected points, which may correspond to existing facility locations. This more general version can be solved by slight modifications of the algorithms.
