Resumo Técnico: Uma Análise de Formulações de Programação Linear Inteira (Mista) para o Problema de Agrupamento Máximamente Diverso

Definição do Problema

O Problema de Agrupamento Máximamente Diverso (MDGP) é um problema clássico de otimização combinatória NP-difícil. Dado um conjunto de itens $I$ e um conjunto de grupos $G$, o objetivo é atribuir cada item a exatamente um grupo de tal forma que a diversidade total dentro dos grupos seja maximizada. A diversidade de um par de itens $(i, j)$ é definida por um parâmetro $d_{ij} \geq 0$. A diversidade total é a soma de todas as diversidades pari passu para itens atribuídos ao mesmo grupo. O problema está sujeito a restrições sobre o número de itens por grupo, definidas por limites inferiores $l_g$ e limites superiores $u_g$ para cada grupo $g \in G$.

As aplicações para o MDGP incluem a atribuição de alunos a grupos ou cursos, formação de equipes de projeto, criação de grupos de revisores e escalonamento de exames finais. Embora abordagens heurísticas sejam comuns na literatura, os métodos de solução exata têm sido historicamente limitados a instâncias de pequeno porte.

Metodologia e Formulações de Modelos

O artigo analisa e compara quatro formulações distintas de programação linear (mista-) inteira (MILP):

1. Formulações Padrão (Weitz e Lakshminarayanan, 1998):

   • Variáveis: Variáveis binárias $x_{ig}$ indicam se o item $i$ é atribuído ao grupo $g$. Variáveis binárias auxiliares $y_{ijg}$ representam se os itens $i$ e $j$ estão ambos no grupo $g$.
   • Mecanismo: A linearização do objetivo é feita usando as restrições $y_{ijg} \leq x_{ig}$ e $y_{ijg} \leq x_{jg}$.
   • Fraqueza: A relaxação de Programação Linear (LP) é fraca. Na relaxação, os itens podem ser atribuídos de forma fracionária a todos os grupos ($x_{ig} = 1/|G|$), fazendo com que o valor do objetivo some todos os pares possíveis de $d_{ij}$, o que é um limite superior inalcançável para soluções inteiras viáveis.

2. Formulações de Papenberg e Klau (2021):

   • Variáveis: Variáveis binárias $z_{ij}$ indicam se os itens $i$ e $j$ são atribuídos ao mesmo grupo, sem especificar qual grupo.
   • Mecanismo: Utiliza restrições de transitividade (ex: $-z_{ij} + z_{ik} + z_{jk} \leq 1$) para garantir consistência e uma restrição garantindo que cada item seja agrupado com exatamente $|I|/|G| - 1$ outros itens.
   • Força: O ramificamento (branching) ocorre nas atribuições item-item ($z_{ij}$), que influenciam diretamente a função objetivo. A relaxação de LP é significativamente mais forte porque as restrições limitam o número de pares por item ao tamanho do grupo.
   • Limitação: Originalmente projetada apenas para grupos de tamanhos iguais.

3. Formulações Combinadas:

   • Mecanismo: Mescla a formulação padrão com a abordagem de Papenberg e Klau ao vincular $z_{ij} = \sum_{g \in G} y_{ijg}$.
   • Contribuição: Adiciona restrições de transitividade ao modelo padrão e adapta as restrições de tamanho de grupo para tamanhos variáveis. O artigo prova que, para grupos de tamanhos iguais, esta formulação possui uma relaxação de LP pelo menos tão forte quanto a formulação de Papenberg e Klau.

4. Formulações Adaptadas de Papenberg e Klau (para Tamanhos de Grupo Variáveis):

   • Mecanismo: Estende a formulação de Papenberg e Klau para lidar com tamanhos de grupo variados ($l_g \neq u_g$) introduzindo um "item fictício" (dummy item) para cada grupo.
   • Variáveis: Os itens são atribuídos a itens fictícios (representando grupos) via $z_{i, \text{dummy}}$.
   • Restrições: Restrições de transitividade aplicam-se a todos os itens, incluindo os fictícios. As restrições garantem que cada item real seja atribuído a exatamente um grupo fictício e que o tamanho do cluster em torno de cada fictício adira a $l_g$ e $u_g$.

Principais Contribuições

• Análise Comparativa: O artigo fornece uma comparação teórica e empírica da formulação padrão de atribuição item-grupo versus a formulação de atribuição item-item.
• Insight Teórico: Demonstra que o ramificamento em variáveis de atribuição item-item ($z_{ij}$) é superior ao ramificamento em variáveis de atribuição item-grupo ($x_{ig}$), pois o primeiro restringe diretamente o valor da função objetivo e produz uma relaxação de LP mais estreita.
• Novas Formulações: Duas novas formulações são apresentadas para lidar com o caso geral de tamanhos de grupo variáveis, estendendo a aplicabilidade da lógica de atribuição item-item mais forte.
• Quebra de Simetria: O artigo discute e transfere restrições de quebra de simetria para o caso geral da formulação padrão.

Resultados Computacionais

Um estudo computacional abrangente foi conduzido utilizando o CPLEX 12.9 em instâncias variando de 10 a 30 itens e 2 a 10 grupos. Cenários de grupos de tamanhos iguais e tamanhos variáveis foram testados.

• Qualidade da Relaxação de LP: A formulação de Papenberg e Klau e suas adaptações produziram consistentemente limites superiores significativamente mais estreitos (gaps menores) em comparação com a formulação padrão. Os gaps de relaxação de LP da formulação padrão foram frequentemente superiores a 100%, enquanto as formulações item-item permaneceram muito menores.
• Desempenho de Resolução:
  • Grupos de Tamanhos Iguais: A formulação de Papenberg e Klau resolveu quase todas as instâncias para a otimalidade mais rapidamente do que a formulação padrão.
  • Tamanhos de Grupo Variáveis: A formulação adaptada de Papenberg e Klau (Seção 3.4) teve o melhor desempenho, resolvendo instâncias com até 30 itens para a otimalidade ou com pequenos gaps dentro do limite de tempo de 1800 segundos.
  • Formulações Padrão: Teve dificuldades significativas, muitas vezes falhando em fechar o gap ou resolver instâncias com mais de 15 itens dentro do limite de tempo.
  • Formulações Combinadas: Embora teoricamente fortes, a formulação combinada não mostrou uma melhoria substancial de desempenho sobre a formulação padrão quando o ramificamento ocorre nas variáveis $x_{ig}$, sugerindo que as restrições de transitividade sozinhas são insuficientes para superar a fraqueza da estratégia de ramificação item-grupo.

Significância e Alegações

O artigo alega que o principal motor para o desempenho superior das novas formulações é a estratégia de ramificação. Ao realizar o ramificamento em atribuições item-item em vez de atribuições item-grupo, o solver pode restringir o espaço de busca de forma mais eficaz devido à relaxação de LP mais forte fornecida pelas restrições de transitividade.

O estudo conclui que, para o MDGP, especialmente em configurações de tamanhos de grupo variáveis, a adaptação da formulação de Papenberg e Klau é a abordagem exata mais eficaz disponível atualmente. Ela estende com sucesso os benefícios da lógica de atribuição item-item para restrições gerais de agrupamento, superando as limitações da formulação padrão de décadas de idade. Os autores observam que, embora a formulação adaptada tenha o melhor desempenho, as instâncias com tamanhos de grupo variáveis permanecem mais difíceis de resolver do que as de tamanhos iguais, provavelmente devido à maior flexibilidade do espaço de solução.