  This paper studies binary quadratic programs in which the objective is
defined by a Euclidean distance matrix, subject to a general polyhedral
constraint set. This class of nonconcave maximisation problems includes the
capacitated, generalised and bi-level diversity problems as special cases. We
introduce two exact cutting plane algorithms to solve this class of
optimisation problems. The new algorithms remove the need for a concave
reformulation, which is known to significantly slow down convergence. We
establish exactness of the new algorithms by examining the concavity of the
quadratic objective in a given direction, a concept we refer to as directional
concavity. Numerical results show that the algorithms outperform other exact
methods for benchmark diversity problems (capacitated, generalised and
bi-level), and can easily solve problems of up to three thousand variables.
