partição$N$itens em$K$partições de tamanho igual, mantendo grupos em itens originais

Aug 16 2020

Suponha que existam$N$itens que entram$M$grupos. Deixar$c_i \in \{1, ..., M\}$por$i=1, ..., N$representam a associação de grupo para o item$i$. Eu gostaria de encontrar uma partição mais grosseira dos itens em$K$novos grupos, onde$K < M$, com duas restrições:

  1. itens no mesmo grupo devem ser atribuídos à mesma partição e
  2. os novos tamanhos de grupo devem ser tão próximos quanto possível.

Meu pensamento inicial é formular isso como um programa inteiro não linear, onde$y_{ij} = 1$se item$i$é atribuído à partição$j$e é zero caso contrário. Então eu teria um conjunto de restrições:

  1. $\sum_{j=1}^K y_{ij} = 1$por$i=1,..., N$(cada item deve ser atribuído a exatamente uma partição)
  2. $y_{ij} = y_{\ell j}$para todos$j=1, ..., K$E se$c_i = c_\ell$(itens no mesmo grupo devem ser atribuídos à mesma partição)

e então eu poderia definir$N_j = \sum_{i=1}^N y_{ij}$e minimizar

$$\sum_{j=1}^K \left(N_j - \frac NK \right)^2.$$

O objetivo particular não importa realmente aqui, no entanto. contanto que$N_j$está perto de$N/K$para todos$j$, não me importa se está em um$\ell_2$ou$\ell_1$sentido ou algo mais vagamente nesse sentido.

Minhas perguntas:

  1. Existe uma formulação melhor desse problema com uma solução particularmente fácil?
  2. Quais algoritmos resolverão esse problema exatamente? Existem maneiras de obter soluções aproximadas rápidas e gananciosas?
  3. Presumo que precisarei aproveitar algum software de otimização existente para obter minha solução. Existem opções padrão aqui para um usuário Python/Julia/R? (Exemplos de código muito apreciados!)

Alguns antecedentes adicionais: estou essencialmente procurando uma abordagem mais eficiente (computacionalmente) para validação cruzada de grupo de saída. O padrão atual é deixar um único grupo de fora de cada vez, de forma que você se encaixe$M$modelos, onde$M$pode ser bem alto. Na prática, algo como$K=5$ou$K=10$é suficiente para fins estatísticos e a validação cruzada terá as propriedades que desejamos, desde que todos no mesmo grupo entrem na mesma dobra e as dobras tenham aproximadamente o mesmo tamanho. tão apropriado$M >> 10$modelos quando há muitos grupos é muitas vezes ineficiente e desnecessário.

Respostas

2 RobPratt Aug 16 2020 at 04:07

Uma abordagem é pensar nos grupos como trabalhos, com a duração de cada trabalho igual ao número de itens em seu grupo. Agora agende esses trabalhos em$K$máquinas idênticas, minimizando o makespan, ou seja, minimizando$\max_j N_j$. A heurística LPT é rápida e produz uma$(2-1/K)$-aproximação.

1 prubin Aug 17 2020 at 02:18

Primeira pergunta: No modelo IP você não precisa de uma variável binária para cada combinação de item e partição. Dado o seu requisito de que os grupos sejam mantidos juntos, você só precisa de um binário para cada combinação de grupo e partição. Sua$y_{ij}=y_{\ell j}$As restrições permitirão que a função de pré-resolução do solucionador reduza o modelo a esse tamanho, mas você também pode começar com a formulação menor. Além disso, em vez de tornar o problema quadrático, provavelmente minimizaria a diferença entre o menor e o maior tamanho da partição, que é linear. Isso não produz necessariamente um modelo "particularmente fácil" de resolver, mas dependendo das dimensões do seu problema e do seu solucionador de IP (e da sua paciência), pode ser bastante fácil.

Segunda pergunta: Você pode resolver o problema exatamente usando o modelo IP e um solucionador de IP. Uma heurística rápida que pode funcionar razoavelmente bem é começar com$K$partições vazias, classifique os grupos em ordem de tamanho decrescente e atribua cada grupo à menor partição atual.

Terceira pergunta: não posso falar por Julia ou Python (embora eu conheça alguns solucionadores de IP para Python), mas com RI estaria inclinado a usar o pacote OMPR (uma DSL para LP/IP) para escrever o modelo. O OMPR, por sua vez, dependerá do ROI para resolver o modelo, e tanto o OMPR quanto o ROI exigirão que você carregue um plug-in específico do solucionador (e, é claro, tenha o solucionador correspondente instalado).

Hackeei um notebook R usando OMPR e ROI com seus respectivos plug-ins CPLEX. Em um problema de teste aleatório com$N=5700$,$M=130$e$K=10$, a heurística que descrevi normalmente obteve uma distribuição de tamanho de partição de 5 (tamanhos variando de 567 a 572) e o modelo IP obteve dez partições de 570 cada (difusão = 0). A heurística levou uma (pequena) fração de segundo. Construir o modelo IP e resolvê-lo com o CPLEX levou cerca de nove segundos.

Como sempre, sua milhagem varia.

ADENDO: Suspeitei (corretamente) que usar números redondos para as dimensões do problema poderia tornar as coisas mais agradáveis, então tentei$N=5723$,$M=137$e$K=10$(o que garante que nenhuma solução tenha todos os tamanhos de partição idênticos). A solução IP gerenciou um spread de 1 (algumas partições tinham 572 itens, algumas tinham 573, o que ainda é melhor do que eu acho que é geralmente alcançável). A solução heurística teve um spread de 30 (tamanhos de partição variando de 552 a 582).

ADENDO 2: Acrescentei uma heurística de intercâmbio pairwise após o que Rob está chamando de heurística LPT. No exemplo com$N=5723$etc., a heurística de troca de pares reduziu o spread de 30 para 2, não muito ideal (o ideal sendo 1), mas muito mais próximo. Como o LPT, a heurística de troca levou bem menos de um segundo neste exemplo.