Qual é o objetivo do problema k-dispersão?

Maximizar a menor distância mínima (δ) entre os k pontos selecionados, com a restrição de selecionar exatamente k pontos (\( \sum_i x_i = k \)).


Explicação:
Variáveis: \(x_i\in\{0,1\}\) indica seleção do ponto i; \(\delta\ge0\) é a menor distância a maximizar.
Formulação típica:
\( \displaystyle \max\ \delta \)
s.a.
- selecionar exatamente k pontos: \( \sum_i x_i = k \).
- garantir que, se i e j forem ambos selecionados, \(d_{ij}\ge\delta\). Isso pode ser modelado com variáveis auxiliares \(y_{ij}\in\{0,1\}\) (valem 1 se i e j forem ambos escolhidos) e um M grande:
\(y_{ij}\le x_i,\quad y_{ij}\le x_j,\quad y_{ij}\ge x_i+x_j-1\),
\(d_{ij} + M(1-y_{ij}) \ge \delta\quad\forall i
Exemplo:
Candidatos em linha nos pontos \(0,2,5,9,12\); escolher \(k=3\).
Testando combinações:
- Seleção \(\{0,5,12\}\): distâncias \(5,12,7\) → \(\min=5\).
- Seleção \(\{0,5,9\}\): distâncias \(5,9,4\) → \(\min=4\).
Portanto a melhor escolha é \(\{0,5,12\}\) com \(\delta^*=5\), ou seja, maximiza a menor distância entre os 3 pontos.