Exact method for maximum diversity problem

EasyChair Preprint no. 562

Abstract

We revise a quadratic formulation for the maximum diversity problem (MDP). We apply the t-linearization technique and strengthen the resulting constraints. We propose new rules for fixing variables, also translated as valid constraints for the problem. From these ingredients, we propose an exact algorithm for the MDP, based on the branch-and-bound method. Computational results obtained with instances of the literature show that the proposed method is able to solve instances with up to $ 125 $ elements, being more efficient than the best exact algorithm in the literature.

Keyphrases: Desigualdades válidas, Lifting, Problema da Diversidade Máxima, t-Linearização

@Booklet{EasyChair:562,
  author = {Pablo Luiz Braga Soares and Manoel Bezerra Campêlo Neto and Daniel Nogueira Rebouças},
  title = {Exact method for maximum diversity problem},
  howpublished = {EasyChair Preprint no. 562},
  doi = {10.29007/m7js},
  year = {EasyChair, 2018}}