Due secoli e mezzo di trasporto ottimale

Riconoscete le persone raffigurate in questa immagine? Probabilmente no, perché queste persone… non esistono! Questi ritratti sono stati generati automaticamente da un programma informatico (una rete neurale), addestrato a creare un numero arbitrario di ritratti. Uno degli strumenti impiegati per addestrare questa rete neurale è il trasporto ottimale. Questa teoria matematica, nata più di due secoli fa, si rivela infatti molto utile nel campo in rapida ascesa della scienza dei dati. Anche la fisica, l’economia e l’elaborazione delle immagini ricorrono al trasporto ottimale per risolvere i propri problemi.

Monge, un precursore -------------------------

La storia del trasporto ottimale inizia con il matematico francese Gaspard Monge. Nato a Beaune (Côte-d’Or), si fece notare a 17 anni disegnando una pianta dettagliata della sua città natale. Vi mostrò una vera vocazione per la geometria. Fu quindi assunto come assistente all’École royale du génie di Mézières (Ardenne), poiché le sue origini troppo modeste gli impedivano di esservi ammesso come allievo. Divenne rapidamente professore di matematica e fisica. Vi insegnò per quasi vent’anni, svolgendo parallelamente un’intensa e varia attività scientifica, in cui insegnamento, ricerca e applicazioni erano strettamente intrecciati.

Le attività scientifiche di Monge si alimentavano di applicazioni, spesso ispirate a questioni militari. Nel 1781 presentò all’Académie des sciences il suo Mémoire sur la théorie des déblais et des remblais. La domanda a cui tentava di rispondere era: come spostare un mucchio di sabbia di una data forma (lo scavo), per trasformarlo in un altro mucchio di sabbia (il riempimento) situato altrove, di uguale volume e forma prescritta, rendendo minima la somma delle distanze percorse dai granelli di sabbia?

Gaspard Monge, conte di Pelusio (1746 — 1818), incisione di Naigeon Jeune.

Vediamo un caso concreto del problema. Supponiamo che N abitanti della stessa città (rappresentati qui dalle lettere maiuscole A, B… G) desiderino tutti leggere lo stesso libro e che N biblioteche della città (rappresentate da numeri) ne possiedano ciascuna una copia. Ci chiediamo come debbano distribuirsi queste N persone affinché ognuna ritiri una copia in una biblioteca, senza creare conflitti (ogni biblioteca riceve una sola di queste persone, poiché possiede una sola copia del libro), e in modo che la somma delle distanze percorse sia minima. Questa domanda prende il nome di problema dell’abbinamento ottimale.

Per risolverlo, si può costruire una tabella contenente le distanze tra le persone e le biblioteche. Le colonne corrispondono agli individui, le righe alle biblioteche. Risolvere il problema equivale a colorare N caselle, in modo che ve ne sia una sola colorata per colonna e una sola per riga (nessun conflitto), e che la somma delle distanze nelle caselle colorate sia la più piccola possibile.

In blu, la soluzione del problema di abbinamento.

Invece delle distanze tra i punti, avremmo potuto considerare il tempo di percorrenza in bicicletta, o qualsiasi altra funzione di costo tra le persone e le biblioteche: avremmo così ottenuto una tabella diversa e dunque un risultato diverso (vedi riquadro).

Esiste un caso particolare in cui si sa trovare facilmente una soluzione al problema di abbinamento: quello in cui tutte le biblioteche e tutti gli individui si trovano su una stessa retta. Il problema è allora unidimensionale. Se la funzione di costo dello spostamento è la distanza, o il quadrato della distanza, una soluzione è data dal riordinamento monotono: si ordinano biblioteche e individui da sinistra a destra sulla retta, poi si manda il primo individuo alla prima biblioteca, e così via. La soluzione trovata non è necessariamente unica: più soluzioni distinte possono minimizzare la funzione di costo.

Il problema di abbinamento dei punti ha un’applicazione molto divertente nell’elaborazione delle immagini: permette di trasferire i colori da un’immagine a un’altra. Un’immagine è una tabella rettangolare in cui ogni casella (pixel) contiene tre valori che codificano un colore (vedi Mathématiques et Imagerie, fuori serie 77, 2021). Questi tre valori corrispondono alle coordinate di rosso, verde e blu in uno spazio cromatico tridimensionale. Abbinando i colori di due immagini mediante il trasporto ottimale, si può trasformare ogni colore della prima nel colore corrispondente della seconda. Questo procedimento si chiama trasferimento di colore ed è utile soprattutto nella post-produzione video.

####

Le strade della sabbia -----------------------

Torniamo a Monge. Il problema che lo interessa è più generale di quello delle biblioteche. Occorre inviare un mucchio di sabbia di forma assegnata verso un altro, anch’esso di forma prescritta. Bisogna sempre rendere minima la somma delle distanze percorse dai granelli di sabbia, con il vincolo che i granelli siano distribuiti secondo lo scavo alla partenza e il riempimento all’arrivo. Monge non risolve il suo problema, ma assume che una soluzione esista e cerca quali proprietà geometriche possa soddisfare.

Studia il problema in due dimensioni, poi in tre. Mostra in particolare che i percorsi non si intersecano: se si devono inviare due granelli di sabbia dai punti A, B ai punti a, b, allora i percorsi che rendono minima la somma degli spostamenti non possono intersecarsi (vedi riquadro).

Il problema di Monge è in realtà particolare e difficile. Si possono costruire esempi semplici in cui non ha un’unica soluzione, bensì più soluzioni, e altri in cui non esiste affatto una soluzione. Un secolo più tardi, dunque alla fine del 19^º secolo, la questione non era ancora risolta e l’Académie des sciences la propose in occasione del premio Bordin.

Bisogna attendere il 20^º secolo perché la questione dell’esistenza di soluzioni al problema del trasporto ottimale sia finalmente risolta. Importanti progressi furono compiuti da vari matematici già dagli anni Trenta e durante la Seconda guerra mondiale, soprattutto per rispondere a problemi di allocazione delle risorse e di ottimizzazione della produzione in economia. Tutte queste idee emersero parallelamente e indipendentemente presso diversi scienziati, tanto «a ovest» quanto «a est».

Entra in scena Kantorovich --------------------------------

I contributi più importanti sull’argomento furono apportati dal matematico russo Leonid Vital’evič Kantorovič (1912-1986). Sviluppò gli strumenti della programmazione lineare, uno dei contributi più significativi alla teoria economica del 20^º secolo. Per questi lavori ricevette nel 1975 il premio Nobel per l’economia insieme a Tjalling Charles Koopmans (1910-1985).

Il problema studiato da Kantorovich è leggermente diverso da quello di Monge. Torniamo ai nostri individui e alle nostre biblioteche. Nel problema di Monge, ci sono tante persone quante biblioteche e si cerca di abbinarle. Nella versione di Kantorovich, ogni biblioteca può possedere più copie del libro e ogni persona è sostituita da un nucleo familiare di più individui che vivono nello stesso luogo e desiderano leggere l’opera tanto ambita.

Il numero totale degli individui che desiderano leggere il libro in tutti i nuclei familiari è uguale al numero totale delle copie presenti in tutte le biblioteche. Si cerca ancora di stabilire come distribuire gli individui tra le diverse biblioteche, senza conflitti e soddisfacendo tutti gli individui, minimizzando la somma degli spostamenti. Ma questa volta più individui di uno stesso nucleo familiare possono distribuirsi tra biblioteche diverse e, viceversa, una stessa biblioteca può ricevere individui provenienti da nuclei diversi.

Per risolvere il problema di Kantorovich, si costruisce di nuovo una matrice delle distanze tra i nuclei familiari (A, B, C e D) e le biblioteche (a, b e c). Si indica con *c_a*_A la distanza tra il nucleo A e la biblioteca a, e così via. Si costruisce poi un’altra tabella delle stesse dimensioni, che indica come i diversi nuclei familiari si distribuiscono tra le biblioteche. Il valore *p_a*_A, per esempio, indica quanti individui del nucleo A vanno alla biblioteca a.

I valori di questa tabella devono soddisfare dei vincoli: il numero di individui provenienti dai diversi nuclei familiari che vanno alla biblioteca a deve essere esattamente uguale al numero di copie del libro in quella biblioteca, cioè 3. Analogamente, il numero di individui che frequentano le biblioteche provenendo dal nucleo A deve essere esattamente uguale al numero di individui di quel nucleo, ossia 2. Tutti questi vincoli si traducono in sette equazioni, che fissano le somme dei valori della tabella in ogni riga e in ogni colonna.

Si cerca quindi di riempire la tabella in modo da rendere minima la somma dei prodotti tra i *p_i*_,*_j e i costi c_i*_,*_j, con il vincolo che le quantità p* siano positive e soddisfino le sette equazioni, cioè:

Il problema ottenuto è un caso particolare di una classe di problemi più generali, detti di programmazione lineare. Un algoritmo molto noto per risolverli è il simplesso, ideato da George Dantzig nel 1947 (vedi la Recherche opérationnelle, fuori serie 75, 2020).

Soluzione del problema di trasporto ottimale di Kantorovich.

Uno strumento fondamentale -----------------

Bisogna attendere gli anni Novanta e, in particolare, i lavori del matematico francese Yann Brenier perché siano esplicitate le condizioni in cui le soluzioni del problema di Kantorovich forniscono soluzioni al problema di Monge. Da allora, la scuola franco-italiana del trasporto ottimale si è notevolmente sviluppata e ha ottenuto numerosi successi, sia nella matematica teorica sia in quella applicata. Il trasporto ottimale è diventato inoltre uno strumento fondamentale in molti campi applicativi, come l’economia, la grafica computerizzata e la fisica. Ha per esempio forti legami con la meccanica dei fluidi. Nell’elaborazione delle immagini, serve a modificare il contrasto o il colore, a confrontare o creare interpolazioni tra forme, a manipolare immagini di texture… Nell’apprendimento automatico, è diventato uno strumento imprescindibile per confrontare dati, impiegato in particolare nell’addestramento di alcune reti neurali. Oggi il trasporto ottimale fa meraviglie!