Método exato para o problema da diversidade máxima

EasyChair Preprint no. 562

Abstract

Revisitamos uma formulação quadrática para o problema da diversidade máxima (MDP). Aplicamos a técnica da t-linearização e fortalecemos as restrições resultantes. Propomos novas regras para fixação de variáveis, também traduzidas como restrições válidas para o problema. A partir desses ingredientes, propomos um algoritmo exato para o MDP, baseado no método branch-and-bound. Resultados computacionais obtidos com instâncias da literatura mostram que o método proposto é capaz de resolver instâncias com até $125$ elementos, sendo mais eficiente que o melhor algoritmo exato da literatura.

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 = {Método exato para o problema da diversidade máxima},
  howpublished = {EasyChair Preprint no. 562},
  doi = {10.29007/m7js},
  year = {EasyChair, 2018}}