Groupe d’études et de recherche en analyse des décisions

The Maximum Dispersion Problem

Jörg Kalcsics Karlsruhe Institute of Technology, Allemagne

In this talk we discuss the maximum dispersion problem, MaxDP. In this problem we are given a set of objects and a set of groups. Each object has a weight associated to it and for each group we are given a desired size of the group in terms of the object weights. Moreover, we are given the "distance" between each pair of objects. The task is to assign objects to groups such that the desired group size is met and all objects assigned to the same group are as dispersed as possible with respect to the distance measure. After presenting some applications of the model, we introduce a straight-forward as well as a covering-type formulation for the problem. To solve the problem efficiently, we study a specific relaxation of a covering-type formulation that enables us to derive tight bounds that considerably improve the effectiveness of the formulation. Thereby, we obtain an upper bound by finding cliques of given size in an auxiliary graph. A lower bound can be derived based on the relation of the optimal solution of the relaxation to the chromatic number of a series of auxiliary graphs. Finally, we propose an exact algorithm for the Maximum Dispersion Problem. Extensive computational experiments assess the efficiency of the proposed exact algorithm.