Sintesi Tecnica: Un'analisi delle formulazioni di programmazione lineare (mista-) intera per il problema del raggruppamento massimamente diversificato

Definizione del Problema

Il Problema del Raggruppamento Massimamente Diversificato (MDGP) è un classico problema di ottimizzazione combinatoria NP-difficile. Dato un insieme di elementi $I$ e un insieme di gruppi $G$, l'obiettivo è assegnare ciascun elemento a esattamente un gruppo in modo da massimizzare la diversità totale all'interno dei gruppi. La diversità di una coppia di elementi $(i, j)$ è definita da un parametro $d_{ij} \geq 0$. La diversità totale è la somma di tutte le diversità a coppie degli elementi assegnati allo stesso gruppo. Il problema è soggetto a vincoli sul numero di elementi per gruppo, definiti da limiti inferiori $l_g$ e limiti superiori $u_g$ per ogni gruppo $g \in G$.

Le applicazioni per l'MDGP includono l'assegnazione di studenti a gruppi o corsi, la formazione di team di progetto, la creazione di gruppi di revisori e la pianificazione di esami finali. Sebbene gli approcci euristici siano comuni nella letteratura, i metodi di soluzione esatta sono stati storicamente limitati a piccole istanze del problema.

Metodologia e Formulazioni del Modello

Il documento analizza e confronta quattro distinte formulazioni di programmazione lineare (mista-) intera (MILP):

1. Formulazione Standard (Weitz e Lakshminarayanan, 1998):

   • Variabili: Variabili binarie $x_{ig}$ indicano se l'elemento $i$ è assegnato al gruppo $g$. Variabili binarie ausiliarie $y_{ijg}$ rappresentano se gli elementi $i$ e $j$ sono entrambi nel gruppo $g$.
   • Meccanismo: L'obiettivo viene linearizzato utilizzando i vincoli $y_{ijg} \leq x_{ig}$ e $y_{ijg} \leq x_{jg}$.
   • Debolezza: Il rilassamento della Programmazione Lineare (LP) è debole. Nel rilassamento, gli elementi possono essere assegnati frazionariamente a tutti i gruppi ($x_{ig} = 1/|G|$), causando il fatto che il valore dell'obiettivo sommi tutte le possibili coppie $d_{ij}$, che è un limite superiore non raggiungibile per le soluzioni intere ammissibili.

2. Formulazione di Papenberg e Klau (2021):

   • Variabili: Variabili binarie $z_{ij}$ indicano se gli elementi $i$ e $j$ sono assegnati allo stesso gruppo, senza specificare quale gruppo.
   • Meccanismo: Utilizza vincoli di transitività (ad esempio, $-z_{ij} + z_{ik} + z_{jk} \leq 1$) per garantire la coerenza e un vincolo che assicura che ogni elemento sia raggruppato con esattamente $|I|/|G| - 1$ altri elementi.
   • Punto di forza: Il branching avviene sulle assegnazioni elemento-elemento ($z_{ij}$), che influenzano direttamente la funzione obiettivo. Il rilassamento LP è significativamente più forte perché i vincoli limitano il numero di coppie per elemento alla dimensione del gruppo.
   • Limitazione: Originariamente progettata solo per gruppi di dimensioni uguali.

3. Formulazione Combinata:

   • Meccanismo: Unisce la formulazione standard con l'approccio di Papenberg e Klau collegando $z_{ij} = \sum_{g \in G} y_{ijg}$.
   • Contributo: Aggiunge vincoli di transitività al modello standard e adatta i vincoli sulla dimensione del gruppo per dimensioni variabili. Il documento dimostra che, per gruppi di dimensioni uguali, questa formulazione ha un rilassamento LP almeno forte quanto la formulazione di Papenberg e Klau.

4. Formulazione di Papenberg e Klau Adattata (per dimensioni di gruppo variabili):

   • Meccanismo: Estende il modello di Papenberg e Klau per gestire dimensioni di gruppo variabili ($l_g \neq u_g$) introducendo un "elemento dummy" per ogni gruppo.
   • Variabili: Gli elementi sono assegnati agli elementi dummy (che rappresentano i gruppi) tramite $z_{i, \text{dummy}}$.
   • Vincoli: I vincoli di transitività si applicano a tutti gli elementi, inclusi i dummy. I vincoli assicurano che ogni elemento reale sia assegnato a esattamente un gruppo dummy, e che la dimensione del cluster attorno a ciascun dummy rispetti $l_g$ e $u_g$.

Contributi Chiave

• Analisi Comparativa: Il documento fornisce un confronto teorico ed empirico tra la formulazione standard di assegnazione elemento-gruppo e la formulazione di assegnazione elemento-elemento.
• Approfondimento Teorico: Dimostra che il branching sulle variabili di assegnazione elemento-elemento ($z_{ij}$) è superiore al branching sulle variabili di assegnazione elemento-gruppo ($x_{ig}$) perché il primo restringe direttamente il valore della funzione obiettivo e produce un rilassamento LP più stretto.
• Nuove Formulazioni: Vengono presentate due nuove formulazioni per gestire il caso generale di dimensioni di gruppo variabili, estendendo l'applicabilità della logica di assegnazione elemento-elemento più forte.
• Rottura della Simmetria: Il documento discute e trasferisce i vincoli di rottura della simmetria al caso generale per la formulazione standard.

Risultati Computazionali

È stata condotta uno studio computazionale completo utilizzando CPLEX 12.9 su istanze che vanno da 10 a 30 elementi e da 2 a 10 gruppi. Sono stati testati sia scenari con gruppi di dimensioni uguali che con dimensioni variabili.

• Qualità del Rilassamento LP: La formulazione di Papenberg e Klau e le sue adattazioni hanno prodotto costantemente limiti superiori significativamente più stretti (gap minori) rispetto alla formulazione standard. I gap del rilassamento LP della formulazione standard erano spesso superiori al 100%, mentre le formulazioni elemento-elemento rimanevano molto più bassi.
• Prestazioni di Risoluzione:
  • Gruppi di Dimensioni Uguali: La formulazione di Papenberg e Klau ha risolto quasi tutte le istanze all'ottimo più velocemente della formulazione standard.
  • Dimensioni di Gruppo Variabili: La formulazione di Papenberg e Klau adattata (Sezione 3.4) è stata la migliore, risolvendo istanze fino a 30 elementi all'ottimo o con piccoli gap entro il limite di tempo di 1800 secondi.
  • Formulazione Standard: Ha incontrato grandi difficoltà, spesso fallendo nel chiudere il gap o nel risolvere istanze con più di 15 elementi entro il limite di tempo.
  • Formulazione Combinata: Sebbene teoricamente forte, la formulazione combinata non ha mostrato un miglioramento sostanziale delle prestazioni rispetto alla formulazione standard quando il branching avviene sulle variabili $x_{ig}$, suggerendo che i soli vincoli di transitività non sono sufficienti a superare la debolezza della strategia di branching elemento-gruppo.

Significato e Rivendicazioni

Il documento afferma che il principale motore della prestazione superiore delle nuove formulazioni è la strategia di branching. Effettuando il branching sulle assegnazioni elemento-elemento piuttosto che sulle assegnazioni elemento-gruppo, il solver può limitare più efficacemente lo spazio di ricerca grazie al rilassamento LP più forte fornito dai vincoli di transitività.

Lo studio conclude che, per l'MDGP, specialmente in contesti con dimensioni di gruppo variabili, l'adattamento della formulazione di Papenberg e Klau è l'approccio esatto più efficace attualmente disponibile. Esso estende con successo i benefici della logica di assegnazione elemento-elemento ai vincoli di raggruppamento generali, superando i limiti della formulazione standard decennale. Gli autori osservano che, sebbene la formulazione adattata sia la migliore, le istanze con dimensioni di gruppo variabili rimangono più difficili da risolvere rispetto a quelle con dimensioni uguali, probabilmente a causa della maggiore flessibilità dello spazio delle soluzioni.