A hybrid three-phase approach for the Max-Mean Dispersion Problem

•We describe a hybrid heuristic for the Max-Mean Dispersion Problem.•The novel element is the use of the QIP solver to develop an efficient hybrid heuristic.•The proposed approach combines a mixed integer non-linear solver, a local branching scheme and a path relinking procedure.•Computational experiments show the effectiveness of the proposed approach.

This paper deals with the Max-Mean Dispersion Problem (Max-Mean DP) belonging to the general category of clustering problems which aim to find a subset of a set which maximizes a measure of dispersion/similarity between elements. A three-phase hybrid heuristic was developed, which combines a mixed integer non-linear solver, a local branching scheme and a path relinking procedure. Computational results performed on the literature instances show that the proposed procedure outperforms the state-of-the-art approaches.