On the unified dispersion problem: Efficient formulations and exact algorithms

Facility dispersion problems involve placing a number of facilities as far apart from each other as possible. Four different criteria of facility dispersal have been proposed in the literature (Erkut & Neuman, 1991). Despite their formal differences, these four classic dispersion objectives can be expressed in a unified model called the partial-sum dispersion model (Lei & Church, 2013). In this paper, we focus on the unweighted partial sum dispersion problem and introduce an efficient formulation for this generalized dispersion problem based on a construct by Ogryczak and Tamir (2003). We also present a fast branch-and-bound based exact algorithm.