Partizione$N$elementi in$K$partizioni di dimensioni uguali mantenendo i gruppi negli elementi originali

Aug 16 2020

Supponiamo che ci siano$N$oggetti che entrano$M$gruppi. Permettere$c_i \in \{1, ..., M\}$per$i=1, ..., N$rappresentano l'appartenenza al gruppo per l'elemento$i$. Vorrei trovare una partizione più grossolana degli elementi in$K$nuovi gruppi, dove$K < M$, con due vincoli:

  1. gli elementi dello stesso gruppo devono essere assegnati alla stessa partizione e
  2. le nuove dimensioni del gruppo dovrebbero essere il più simili possibile.

Il mio pensiero iniziale è di formulare questo come un programma intero non lineare, dove$y_{ij} = 1$se articolo$i$è assegnato alla partizione$j$ed è zero altrimenti. Quindi avrei una serie di vincoli:

  1. $\sum_{j=1}^K y_{ij} = 1$per$i=1,..., N$(ogni elemento deve essere assegnato esattamente a una partizione)
  2. $y_{ij} = y_{\ell j}$per tutti$j=1, ..., K$Se$c_i = c_\ell$(gli elementi nello stesso gruppo devono essere assegnati alla stessa partizione)

e poi potrei definire$N_j = \sum_{i=1}^N y_{ij}$e minimizzare

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

Tuttavia, l'obiettivo particolare in realtà non ha importanza qui. Finché$N_j$è vicino a$N/K$per tutti$j$, non mi interessa se è in un$\ell_2$o$\ell_1$senso o qualcos'altro vagamente lungo quelle linee.

Le mie domande:

  1. Esiste una migliore formulazione di questo problema con una soluzione particolarmente facile?
  2. Quali algoritmi risolveranno esattamente questo problema? Esistono modi per ottenere rapidamente soluzioni approssimate avide?
  3. Presumo che avrò bisogno di sfruttare alcuni software di ottimizzazione esistenti per ottenere la mia soluzione. Ci sono scelte standard qui per un utente Python/Julia/R? (Esempi di codice molto apprezzati!)

Alcuni retroscena aggiuntivi: sto essenzialmente cercando un approccio più efficiente (computazionalmente) alla convalida incrociata senza gruppo. Lo standard attuale è di lasciare fuori un singolo gruppo alla volta, in modo tale da adattarsi$M$modelli, dove$M$può essere piuttosto elevato. In pratica, qualcosa del genere$K=5$o$K=10$è sufficiente per scopi statistici e la convalida incrociata avrà le proprietà che desideriamo fintanto che tutti nello stesso gruppo entrano nella stessa piega e le pieghe hanno all'incirca le stesse dimensioni. Così appropriato$M >> 10$modelli quando ci sono molti gruppi è spesso inefficiente e non necessario.

Risposte

2 RobPratt Aug 16 2020 at 04:07

Un approccio consiste nel pensare ai gruppi come lavori, con la durata di ogni lavoro uguale al numero di elementi nel suo gruppo. Ora pianifica questi lavori$K$macchine identiche, minimizzando il makespan, cioè minimizzare$\max_j N_j$. L'euristica LPT è veloce e produce a$(2-1/K)$-approssimazione.

1 prubin Aug 17 2020 at 02:18

Prima domanda: nel modello IP non è necessaria una variabile binaria per ogni combinazione di elemento e partizione. Data la tua esigenza che i gruppi siano tenuti insieme, hai solo bisogno di un binario per ogni combinazione di gruppo e partizione. Tuo$y_{ij}=y_{\ell j}$i vincoli consentiranno alla funzione presolve del risolutore di ridurre il modello a questa dimensione, ma potresti anche iniziare con la formulazione più piccola. Inoltre, piuttosto che rendere il problema quadratico, probabilmente ridurrei al minimo la differenza tra la dimensione della partizione più piccola e quella più grande, che è lineare. Ciò non produce necessariamente un modello "particolarmente facile" da risolvere, ma a seconda delle dimensioni del problema e del risolutore IP (e della pazienza), potrebbe essere abbastanza facile.

Seconda domanda: puoi risolvere il problema esattamente utilizzando il modello IP e un risolutore IP. Un'euristica veloce che potrebbe funzionare ragionevolmente bene è per cominciare$K$partizioni vuote, ordinare i gruppi in ordine di dimensione decrescente, quindi assegnare ogni gruppo alla partizione attualmente più piccola.

Terza domanda: non posso parlare per Julia o Python (anche se conosco alcuni risolutori IP per Python), ma con RI sarei propenso a utilizzare il pacchetto OMPR (un DSL per LP/IP) per scrivere il modello. OMPR a sua volta si affiderà al ROI per risolvere il modello e sia OMPR che ROI richiederanno il caricamento di un plug-in specifico del risolutore (e, ovviamente, l'installazione del risolutore corrispondente).

Ho violato un notebook R utilizzando OMPR e ROI con i rispettivi plug-in CPLEX. Su un problema di test casuale con$N=5700$,$M=130$e$K=10$, l'euristica che ho descritto in genere ha uno spread di dimensioni della partizione di 5 (dimensioni comprese tra 567 e 572) e il modello IP ha dieci partizioni di 570 ciascuna (spread = 0). L'euristica ha richiesto una (piccola) frazione di secondo. Costruire il modello IP e risolverlo con CPLEX ha richiesto circa nove secondi.

Come sempre, il tuo chilometraggio varierà.

ADDENDUM: sospettavo (correttamente) che l'uso di numeri tondi per le dimensioni del problema potesse rendere le cose più belle, quindi ho provato$N=5723$,$M=137$e$K=10$(che garantisce che nessuna soluzione abbia tutte le dimensioni delle partizioni identiche). La soluzione IP gestiva uno spread di 1 (alcune partizioni avevano 572 elementi, altre 573, che è ancora meglio di quanto penso sia generalmente ottenibile). La soluzione euristica aveva uno spread di 30 (dimensioni delle partizioni comprese tra 552 e 582).

ADDENDUM 2: Ho aggiunto un'euristica di interscambio a coppie dopo quella che Rob chiama l'euristica LPT. Nell'esempio con$N=5723$ecc., l'euristica dello scambio a coppie ha ridotto lo spread da 30 a 2, non proprio ottimale (l'ottimale è 1) ma molto più vicino. Come LPT, l'euristica dello scambio ha impiegato ben meno di un secondo in questo esempio.