Finding a cluster of points and the grey pattern quadratic assignment problem

In this paper we propose a model which aims at selecting a tight cluster from a set of points. The same formulation applies also to the grey pattern problem where the objective is to find a set of black dots in a rectangular grid with a given density so that the dots are spread as evenly as possible. A branch and bound algorithm and five heuristic approaches are proposed. Computational results demonstrate the efficiency of these approaches. Seven grey pattern problems are solved to optimality and for eight additional grey pattern problems the best known solution is improved. The cluster problem on a network is solved for 40 problems with the number of points ranging between 100 and 900 and the size of the cluster ranging between 5 and 200. Twenty one problems were solved optimally and the remaining 19 problems were heuristically solved in a very short computer time with excellent results.