Dividir$N$artículos en$K$particiones de igual tamaño mientras se conservan los grupos en los elementos originales

Aug 16 2020

Supongamos que hay$N$elementos que entran$M$grupos Dejar$c_i \in \{1, ..., M\}$por$i=1, ..., N$representar la membresía del grupo para el artículo$i$. Me gustaría encontrar una partición más gruesa de los elementos en$K$nuevos grupos, donde$K < M$, con dos restricciones:

  1. los elementos del mismo grupo deben asignarse a la misma partición, y
  2. los nuevos tamaños de grupo deben ser lo más parejos posible.

Mi pensamiento inicial es formular esto como un programa entero no lineal, donde$y_{ij} = 1$si el artículo$i$se asigna a la partición$j$y es cero en caso contrario. Entonces tendría un conjunto de restricciones:

  1. $\sum_{j=1}^K y_{ij} = 1$por$i=1,..., N$(cada elemento debe asignarse exactamente a una partición)
  2. $y_{ij} = y_{\ell j}$para todos$j=1, ..., K$si$c_i = c_\ell$(los elementos del mismo grupo deben asignarse a la misma partición)

y luego pude definir$N_j = \sum_{i=1}^N y_{ij}$y minimizar

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

Sin embargo, el objetivo particular en realidad no importa aquí. Siempre y cuando$N_j$está cerca de$N/K$para todos$j$, no me importa si es en un$\ell_2$o$\ell_1$sentido o algo más vagamente a lo largo de esas líneas.

Mis preguntas:

  1. ¿Hay una mejor formulación de este problema con una solución particularmente fácil?
  2. ¿Qué algoritmos resolverán este problema exactamente? ¿Hay formas de obtener soluciones aproximadas rápidas y codiciosas?
  3. Supongo que tendré que aprovechar algún software de optimización existente para obtener mi solución. ¿Hay opciones estándar aquí para un usuario de Python/Julia/R? (¡Ejemplos de código muy apreciados!)

Algunos antecedentes adicionales: esencialmente estoy buscando un enfoque más (computacionalmente) eficiente para la validación cruzada de exclusión de grupos. El estándar actual es dejar un solo grupo a la vez, de modo que quepa$M$modelos, donde$M$puede ser bastante alto. En la práctica, algo como$K=5$o$K=10$es suficiente para propósitos estadísticos, y la validación cruzada tendrá las propiedades que queremos siempre y cuando todos en el mismo grupo entren en el mismo pliegue y los pliegues tengan aproximadamente el mismo tamaño. tan apropiado$M >> 10$modelos cuando hay muchos grupos es a menudo ineficiente e innecesario.

Respuestas

2 RobPratt Aug 16 2020 at 04:07

Un enfoque es pensar en los grupos como trabajos, con la duración de cada trabajo igual al número de elementos en su grupo. Ahora programe estos trabajos en$K$máquinas idénticas, minimizando elmakespan, es decir, minimizar$\max_j N_j$. La heurística LPT es rápida y produce una$(2-1/K)$-aproximación.

1 prubin Aug 17 2020 at 02:18

Primera pregunta: en el modelo IP no necesita una variable binaria para cada combinación de elemento y partición. Dado su requisito de que los grupos se mantengan juntos, solo necesita un binario para cada combinación de grupo y partición. Su$y_{ij}=y_{\ell j}$Las restricciones permitirán que la función de resolución previa del solucionador reduzca el modelo a este tamaño, pero también podría comenzar con la formulación más pequeña. Además, en lugar de hacer que el problema sea cuadrático, probablemente minimizaría la diferencia entre el tamaño de partición más pequeño y el más grande, que es lineal. Esto no necesariamente produce un modelo "particularmente fácil" de resolver, pero dependiendo de las dimensiones de su problema y su solucionador de IP (y su paciencia), puede ser bastante fácil.

Segunda pregunta: puede resolver el problema exactamente utilizando el modelo de IP y un solucionador de IP. Una heurística rápida que podría funcionar razonablemente bien es comenzar con$K$particiones vacías, ordene los grupos en orden de tamaño descendente, luego asigne cada grupo a la partición más pequeña actualmente.

Tercera pregunta: no puedo hablar por Julia o Python (aunque conozco algunos solucionadores de IP para Python), pero con RI me inclinaría a usar el paquete OMPR (un DSL para LP/IP) para escribir el modelo. OMPR, a su vez, se basará en el ROI para resolver el modelo, y tanto OMPR como ROI requerirán que cargue un complemento específico del solucionador (y, por supuesto, que tenga instalado el solucionador correspondiente).

Hackeé una notebook R usando OMPR y ROI con sus respectivos complementos CPLEX. En un problema de prueba aleatorio con$N=5700$,$M=130$y$K=10$, la heurística que describí generalmente obtuvo una distribución de tamaño de partición de 5 (tamaños que van desde 567 a 572), y el modelo IP obtuvo diez particiones de 570 cada una (distribución = 0). La heurística tomó una (pequeña) fracción de segundo. Construir el modelo IP y resolverlo con CPLEX tomó alrededor de nueve segundos.

Como siempre, su millaje variará.

ADDENDUM: Sospeché (correctamente) que usar números redondos para las dimensiones del problema podría mejorar las cosas, así que intenté$N=5723$,$M=137$y$K=10$(lo que garantiza que ninguna solución tenga todos los tamaños de partición idénticos). La solución IP manejó una extensión de 1 (algunas particiones tenían 572 elementos, otras tenían 573, lo que sigue siendo mejor de lo que creo que generalmente se puede lograr). La solución heurística tenía una extensión de 30 (tamaños de partición que van desde 552 a 582).

ANEXO 2: Agregué una heurística de intercambio por pares después de lo que Rob llama la heurística LPT. En el ejemplo con$N=5723$etc., la heurística de intercambio por pares redujo la dispersión de 30 a 2, no del todo óptima (el óptimo es 1) pero mucho más cerca. Al igual que LPT, la heurística de intercambio tomó menos de un segundo en este ejemplo.