Cloison$N$articles dans$K$partitions de taille égale tout en conservant les groupes dans les éléments d'origine

Aug 16 2020

Supposons qu'il y ait$N$articles qui entrent$M$groupes. Laisser$c_i \in \{1, ..., M\}$pour$i=1, ..., N$représentent l'appartenance au groupe pour l'élément$i$. Je voudrais trouver une partition plus grossière des éléments dans$K$de nouveaux groupes, où$K < M$, avec deux contraintes :

  1. les éléments du même groupe doivent être affectés à la même partition, et
  2. les nouvelles tailles de groupe doivent être aussi égales que possible.

Ma pensée initiale est de formuler cela comme un programme entier non linéaire, où$y_{ij} = 1$si article$i$est affecté à la partition$j$et vaut zéro sinon. Ensuite, j'aurais un ensemble de contraintes:

  1. $\sum_{j=1}^K y_{ij} = 1$pour$i=1,..., N$(chaque élément doit être affecté à exactement une partition)
  2. $y_{ij} = y_{\ell j}$pour tous$j=1, ..., K$si$c_i = c_\ell$(les éléments du même groupe doivent être affectés à la même partition)

et puis je pourrais définir$N_j = \sum_{i=1}^N y_{ij}$et minimiser

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

L'objectif particulier n'a pas vraiment d'importance ici, cependant. Tant que$N_j$est proche de$N/K$pour tous$j$, je m'en fous si c'est dans un$\ell_2$ou$\ell_1$sens ou quelque chose d'autre vaguement dans ce sens.

Mes questions:

  1. Existe-t-il une meilleure formulation de ce problème avec une solution particulièrement simple ?
  2. Quels algorithmes résoudront ce problème exactement ? Existe-t-il des moyens d'obtenir rapidement des solutions approximatives gourmandes ?
  3. Je suppose que je vais devoir tirer parti de certains logiciels d'optimisation existants pour obtenir ma solution. Existe-t-il ici des choix standard pour un utilisateur Python/Julia/R ? (Échantillons de code très appréciés !)

Quelques informations supplémentaires : je recherche essentiellement une approche plus efficace (en termes de calcul) pour la validation croisée des groupes de sortie. La norme actuelle est de laisser un seul groupe à la fois, de sorte que vous correspondiez$M$modèles, où$M$peut être assez élevé. En pratique, quelque chose comme$K=5$ou$K=10$est suffisant à des fins statistiques, et la validation croisée aura les propriétés souhaitées tant que tout le monde dans le même groupe entre dans le même pli et que les plis ont à peu près la même taille. Tellement approprié$M >> 10$modèles lorsqu'il y a de nombreux groupes est souvent inefficace et inutile.

Réponses

2 RobPratt Aug 16 2020 at 04:07

Une approche consiste à considérer les groupes comme des tâches, la durée de chaque tâche étant égale au nombre d'éléments de son groupe. Planifiez maintenant ces travaux sur$K$machines identiques, en minimisant le makingpan, c'est-à-dire en minimisant$\max_j N_j$. L'heuristique LPT est rapide et donne une$(2-1/K)$-approximation.

1 prubin Aug 17 2020 at 02:18

Première question : dans le modèle IP, vous n'avez pas besoin d'une variable binaire pour chaque combinaison d'élément et de partition. Étant donné votre exigence que les groupes restent ensemble, vous avez juste besoin d'un binaire pour chaque combinaison de groupe et de partition. Ton$y_{ij}=y_{\ell j}$les contraintes permettront à la fonction de prérésolution du solveur de réduire le modèle à cette taille, mais vous pouvez tout aussi bien commencer avec la formulation la plus petite. De plus, plutôt que de rendre le problème quadratique, je minimiserais probablement la différence entre la plus petite et la plus grande taille de partition, qui est linéaire. Cela ne produit pas nécessairement un modèle "particulièrement facile" à résoudre, mais selon les dimensions de votre problème et votre solutionneur IP (et votre patience), cela peut être assez facile.

Deuxième question : Vous pouvez résoudre le problème exactement en utilisant le modèle IP et un solveur IP. Une heuristique rapide qui pourrait raisonnablement bien fonctionner consiste à commencer par$K$partitions vides, triez les groupes par ordre décroissant de taille, puis affectez chaque groupe à la plus petite partition actuellement.

Troisième question : je ne peux pas parler pour Julia ou Python (bien que je connaisse certains solveurs IP pour Python), mais avec RI, je serais enclin à utiliser le package OMPR (un DSL pour LP/IP) pour écrire le modèle. OMPR s'appuiera à son tour sur le retour sur investissement pour résoudre le modèle, et OMPR et ROI vous demanderont de charger un plug-in spécifique au solveur (et, bien sûr, d'avoir installé le solveur correspondant).

J'ai piraté un bloc-notes R en utilisant OMPR et ROI avec leurs plug-ins CPLEX respectifs. Sur un problème de test aléatoire avec$N=5700$,$M=130$et$K=10$, l'heuristique que j'ai décrite a généralement une répartition de taille de partition de 5 (tailles allant de 567 à 572), et le modèle IP a dix partitions de 570 chacune (diffusion = 0). L'heuristique a pris une (petite) fraction de seconde. La création du modèle IP et sa résolution avec CPLEX ont pris environ neuf secondes.

Comme toujours, votre kilométrage variera.

ADDENDA : Je soupçonnais (à juste titre) que l'utilisation de chiffres ronds pour les dimensions du problème pourrait rendre les choses plus agréables, alors j'ai essayé$N=5723$,$M=137$et$K=10$(ce qui garantit qu'aucune solution n'a toutes les tailles de partition identiques). La solution IP a géré un écart de 1 (certaines partitions avaient 572 éléments, certaines en avaient 573, ce qui est toujours mieux que ce que je pense être généralement réalisable). La solution heuristique avait une propagation de 30 (taille de partition allant de 552 à 582).

ADDENDUM 2 : J'ai ajouté une heuristique d'échange par paires après ce que Rob appelle l'heuristique LPT. Dans l'exemple avec$N=5723$etc., l'heuristique d'échange par paires a réduit l'écart de 30 à 2, pas tout à fait optimal (optimal étant 1) mais beaucoup plus proche. Comme LPT, l'heuristique d'échange a pris bien moins d'une seconde sur cet exemple.