Le transport optimal numérique et ses applications - Partie 1

Le transport de Monge

Piste rouge Le 5 mai 2019  - Ecrit par  Gabriel Peyré Voir les commentaires (3)

Le transport optimal est un problème ancien, formulé par Monge au XVIIIe siècle. Il consiste à chercher le moyen le plus économique, par exemple en temps, pour transporter des objets entre un ensemble de points de départ et de points d’arrivée. Cet article expose ce problème, la difficulté de trouver une solution quand il y a beaucoup de points, et illustre quelques applications. Un article compagnon à paraître prochainement présente la reformulation par Kantorovitch du problème de Monge, qui lui a permis de devenir un outil incontournable à la fois en théorie et en pratique.

$\newcommand{\Blu}[1]{{\color{blue}#1}} \newcommand{\Red}[1]{{\color{red}#1}} \newcommand{\iC}{\Red{i}} \newcommand{\jC}{\Blu{j}} \newcommand{\aC}{\Red{a}} \newcommand{\bC}{\Blu{b}} \newcommand{\si}{s} \newcommand{\Si}{S} \newcommand{\eq}[1]{\begin{equation*}#1\end{equation*}} \newcommand{\eql}[1]{\begin{equation}#1\end{equation}} \newcommand{\eqdef}{\overset{\Delta}{=}} \renewcommand{\eqdef}{:=} \newcommand{\umin}[1]{\underset{#1}{\min}\;} \newcommand{\RR}{\mathbb{R}} \newcommand{\norm}[1]{|\!| #1 |\!|}$

Gaspard Monge, en plus d’être un grand mathématicien, a participé activement à la révolution Française, et a créé l’Ecole Polytechnique ainsi que l’Ecole Normale Supérieure. Motivé par des applications militaires, il a formulé en 1781 le problème du transport optimal [1] : il s’est posé la question du calcul de la façon la plus économique de transporter de la terre entre deux endroits pour faire des remblais.

Le problème de Monge

Pour illustrer le problème et sa formulation mathématique, intéressons-nous à la façon optimale de distribuer les croissants depuis les boulangeries vers les cafés, le matin dans Paris. Pour simplifier, nous allons supposer qu’il y a uniquement six boulangeries et cafés, que l’on peut voir à la figure suivante (les boulangeries sont en rouge et les cafés en bleu).
On suppose que toutes les boulangeries produisent le même nombre de croissants et que tous les cafés demandent également ce même nombre de croissants.
Dans son texte original, Monge fait l’hypothèse que le coût du déplacement d’une unité de masse est égal à la distance parcourue, mais on peut utiliser n’importe quel coût adapté au problème à résoudre.
Le coût à minimiser que nous allons considérer est le temps total des trajets, et l’on note $C_{\iC,\jC}$ le temps entre la boulangerie $\iC \in \{1,\ldots,6\}$ et le café $\jC \in \{1,\ldots,6\}$. Par exemple, on a $C_{\Red{3},\Blu{4}}=10$, ce qui signifie qu’il y a dix minutes de trajet entre la boulangerie numéro $\Red{3}$ et le café numéro $\Blu{4}$.

Une ligne de la matrice de coût $C$ Un exemple de permutation $\sigma$

Afin de satisfaire la contrainte d’approvisionnement, il faut que chaque boulangerie soit connectée à un seul café et que chaque café soit connecté à une seule boulangerie. Ceci implique en particulier qu’il y a autant de cafés que de boulangeries. On va noter
\[ \si : \iC \in \{1,\ldots,6\} \longmapsto \jC \in \{1,\ldots,6\} \]
un tel choix de connexions. On appelle un tel choix $\si$ de connexions satisfaisant la contrainte d’approvisionnement une permutation.

La figure précédente illustre à droite l’exemple
\[\begin{equation}\label{eq-bijection-exmp} \si(\Red{1})=\Blu{5}, \; \si(\Red{2})=\Blu{2}, \; \si(\Red{3})=\Blu{6}, \; \si(\Red{4})=\Blu{1}, \; \si(\Red{5})=\Blu{3}, \; \si(\Red{6})=\Blu{4}. \end{equation}\]

Le coût de transport associé à une telle permutation est la somme des coûts $C_{\iC,\si(\iC)}$ sélectionnés par la permutation $\si$, c’est-à-dire
\[\begin{equation*} \text{Coût}(\si) \eqdef C_{\Red{1},\si(\Red{1})} + C_{\Red{2},\si(\Red{2})} + C_{\Red{3},\si(\Red{3})} + C_{\Red{4},\si(\Red{4})} + C_{\Red{5},\si(\Red{5})} + C_{\Red{6},\si(\Red{6})}. \end{equation*}\]
Par exemple, pour la permutation ($\ref{eq-bijection-exmp}$) montrée à la figure précédente, on obtient comme coût
\[\begin{equation*} C_{\Red{1},\Blu{5}} + C_{\Red{2},\Blu{2}} + C_{\Red{3},\Blu{6}} + C_{\Red{4},\Blu{1}} + C_{\Red{5},\Blu{3}} + C_{\Red{6},\Blu{4}} = 10 + 7 + 15 + 10 + 14 + 9 = 65. \end{equation*}\]

Le problème de Monge consiste à chercher une permutation $\si$ qui a le coût minimum, c’est-à-dire résoudre le problème d’optimisation
\[\begin{equation*} \umin{\si \in \Si_6} \text{Coût}(\si), \end{equation*}\]
où l’on a noté $\Si_6$ l’ensemble des permutations de l’ensemble $\{1,\ldots,6\}$.

Coût=64 Coût=65 Coût=66 Coût=152

La figure précédente montre des exemples de permutations avec différents coûts. On peut ainsi voir que la permutation ($\ref{eq-bijection-exmp}$) n’est pas la meilleure : il existe par exemple une autre permutation qui a un coût de 64. Mais est-ce la meilleure ? Il se trouve que oui, on peut en effet tester sur un ordinateur toutes les permutations de $\{1,\ldots,6\}$ et calculer leur coût. Combien y a-t-il de permutations au total ? Pour effectuer ce dénombrement, on voit qu’il y a six choix d’affectation possible de $\Red{1}$ à $\si(\Red{1}) \in \{\Blu{1},\ldots,\Blu{6}\} $, puis cinq choix possibles pour affecter $\Red{2}$ à $\si(\Red{2})$ dans l’ensemble $\{ \Blu{1},\ldots,\Blu{6 } \}$ auquel on exclu $ \si(\Red{1})$, et ainsi de suite. Le nombre total de possibilités est donc $6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720$ que l’on note $6!$, « factorielle 6 ». Si l’on considère un nombre $n$ de boulangeries, alors le nombre de permutations à tester pour trouver la meilleure est $n! =n \times (n-1) \times \cdots \times 2 \times 1$. Ce nombre croit extrêmement vite avec $n$, par exemple $70! \approx 1,198 \times 10^{100}$, à comparer avec les $10^{11}$ neurones dans le cerveau et les $10^{79}$ atomes dans l’univers. Cette stratégie de recherche exhaustive n’est donc possible que pour de toutes petites valeurs de $n$.

En 1D et 2D

Il aura fallu près de 200 ans pour que des idées nouvelles émergent pour calculer efficacement un transport optimal $\sigma$ même pour des grandes valeurs de $n$. Ces avancées mathématiques seront détaillées dans l’article compagnon. Commençons par un cas dans lequel le transport optimal se calcule facilement. Le cas le plus élémentaire est lorsque les points à apparier sont le long d’un axe 1D, par exemple si les cafés et les boulangeries sont situés le long d’une ligne de métro. Il faut également que le coût $C_{\iC,\jC}$ soit la distance le long de cet axe (par exemple le temps de trajet en métro entre les stations).
On se place à gauche de tous les points en jeu et on parcourt la ligne de métro de gauche à droite. Le premier point rouge est associé avec le premier point bleu, le deuxième point rouge avec le deuxième point bleu, etc.
Ce procédé est illustré à la figure suivante, où la permutation optimale est $\si : (\Red{1},\Red{2},\Red{3},\Red{4},\Red{5}) \mapsto (\Blu{3},\Blu{2},\Blu{1},\Blu{5},\Blu{4})$.

Le temps de calcul nécessaire pour calculer le transport optimal en métro est donc le temps nécessaire pour classer les indices. L’algorithme le plus simple pour effectuer un classement est celui utilisé habituellement pour trier un jeu de $n$ cartes : il s’agit du tri par insertion, qui insère itérativement chaque carte à sa place par rapport aux cartes déjà classées. Il effectue $n(n-1)/2$ comparaisons. Pour $n=70$, ceci nécessite donc seulement 2415 operations, ce qui rend la méthode utilisable, au contraire de la recherche exhaustive de toutes les $n!$ permutations. On dispose d’algorithmes encore plus rapides (par exemple le tri fusion), qui effectuent de l’ordre de $n \log(n)$ opérations, et donc pour $n = 70$, de telles méthodes nécessitent moins de 1000 opérations.

Malheureusement, il n’est plus possible d’utiliser cette technique de classement dans des cas plus généraux. Pour des points en dimension 2, si on prend comme coût $C_{\iC,\si(\iC)}$ la distance à vol d’oiseau entre les points, alors Gaspard Monge a montré dans son papier original (voir la figure suivante) qu’un transport optimal ne peut pas contenir de croisement.

Par exemple, comme le montre la figure suivante, si l’on trace tous les segments entre les points $\iC \mapsto \jC = \si(\iC)$ que l’on relie par la permutation définie par un $\si$ optimal, ceux-ci ne se croisent jamais.

Transport 2D, $n=10$ Transport 2D, $n=70$ Transport 2D, $n=200$

Cette observation géométrique n’est cependant pas suffisante pour calculer un transport optimal en 2D : il existe en effet beaucoup de permutations $\si$ telles que les segments associés ne se croisent pas.
Il va falloir analyser de façon plus fine la structure des permutations optimales afin de pouvoir les calculer de façon efficace.
L’article compagnon montrera comment Leonid Kantorovitch a reformulé le problème de Monge afin d’y parvenir.

Applications

La motivation initiale de Monge était principalement militaire. Les applications envisagées par Kantorovitch étaient économiques [2], et le transport optimal a eu un impact considérable sur l’optimisation de la production industrielle. En effet, à chaque fois que l’on doit mettre en relation des quantités de production et de consommation, on est amené à résoudre un problème de transport optimal. Kantorovitch a reçu le prix Nobel d’économie en 1975 pour ses travaux dans ce domaine, qui seront détaillés dans l’article compagnon.

Le transport optimal a trouvé bien d’autres applications, à la fois théoriques mais aussi plus concrètes. Sur le plan mathématique, on peut considérer des distributions « continues » de masses, en quelque sorte la limite quand le nombre de points $n$ tend vers l’infini. Ceci permet de définir le problème de transport entre des distributions de probabilités quelconques. Ce point de vue théorique est extrêmement fructueux, et c’est le mathématicien français Yann Brenier qui a le premier montré l’équivalence dans le cadre continu des formulations de Monge et de Kantorovich [3]. Ces travaux pionniers ont montré la connexion entre le problème de transport et les équations aux dérivées partielles, et ont débouché, entre autres, sur les médailles Fields de Cédric Villani (2010) et Alessio Figalli (2018).

Le transport optimal est depuis peu au cœur de problématiques plus appliquées en sciences des données, en particulier pour résoudre des problèmes en traitement d’image et en apprentissage machine.
La première idée, la plus immédiate, est d’utiliser la permutation $\si$ afin de transformer des données, par exemple des images. Dans ce cas, on considère les pixels $(\Red{x_1},\ldots,\Red{x_n} )$ et $(\Blu{y_1},\ldots,\Blu{y_n})$ de deux images couleurs. Chaque pixel $\Red{x_i}, \Blu{y_j} \in \RR^3$ est un vecteur de dimension 3, qui représente les intensités de chacune des trois couleurs élémentaires, rouge, vert et bleu. Afin de changer les couleurs de la première image, et lui imposer la palette de la deuxième image, on calcule le transport $\si$ en utilisant un coût $C_{\iC,\jC}$ qui prend en compte la similarité entre la couleur $\Red{x_i}$ et la couleur $\Blu{y_j}$ des deux pixels, ce qui signifie que $C_{\iC,\jC}$ est d’autant plus faible que les couleurs des deux pixels sont proches. L’image avec les couleurs modifiées est $(y_{\si(1)},\ldots,y_{\si(n)})$, c’est-à-dire que l’on remplace dans la première image le pixel $\Red{x_i}$ par le pixel $y_{\si(\iC)}$. Cette image ressemble à la première, mais a la palette de couleurs de la deuxième image.

La figure suivante illustre ce procédé pour imposer la palette de couleurs de Picasso à un tableau de Cézanne. Sur la ligne du haut de la figure, les pixels sont sur la grille d’affichage pour former une image couleur. Sur la ligne du bas, les pixels sont placés à leurs positions dans $\RR^3$ pour former un nuage de points. Les deux nuages de points au centre et à droite sont les mêmes : le transport optimal appliqué aux pixels du tableau de Cézanne donne une nouvelle image (montrée à droite) dont l’ensemble des pixels est une permutation des pixels du tableau de Picasso.

Image $(\Red{x_i})_{\iC=1}^n$ Image $(\Blu{y_j})_{\jC=1}^n$ Image $(y_{\si(\iC)})_{\iC=1}^n$

La figure suivante montre une autre application du transport optimal, la modification de formes 3D. Plus d’informations sur cette application, ainsi que sur d’autres applications à la science des données, seront détaillées dans l’article compagnon.

Articles reliés

Post-scriptum :

Je tiens à remercier Vincent Beck, Gwenn Guichaoua et Marie-Noëlle Peyré pour leurs relectures attentives, ainsi que les relecteurs Massok, Yassine Ghalem, Ophélie et François Brunault pour leurs commentaires et corrections.

Article édité par Jérôme Buzzi

Notes

[1Gaspard Monge. Mémoire sur la théorie des déblais et des remblais. Histoire de l’Académie Royale des Sciences, p. 666-704, 1781.

[2Leonid Kantorovich. On the transfer of masses (en russe). Doklady Akademii Nauk, 37(2), p. 227-229, 1942.

[3Yann Brenier. Polar factorization and monotone rearrangement of vector-valued functions. Communications on Pure and Applied Mathematics, 44(4) : p.375-417, 1991.

Partager cet article

Pour citer cet article :

Gabriel Peyré — «Le transport optimal numérique et ses applications - Partie 1» — Images des Mathématiques, CNRS, 2019

Commentaire sur l'article

  • Le transport optimal numérique et ses applications - Partie 1

    le 6 mai à 09:01, par B !gre

    Bonjour,

    Les exemples donnés en début d’article sont si je ne m’abuse des instances du problème dit du voyageur de commerce. Pouvez-vous expliciter les similarités et différences entre les deux problèmes ? À la lecture de l’article, j’ai le sentiment que le transport optimal serait une version continue du voyageur de commerce, cela fait-il du sens ?

    Merci !

    Répondre à ce message
    • Le transport optimal numérique et ses applications - Partie 1

      le 6 mai à 09:48, par Gabriel Peyré

      Bonjour,

      Non, il ne s’agit pas du problème du voyageur de commerce, qui est un problème très difficile à résoudre (NP-difficile) alors que le problème de transport optimal est relativement facile (algorithme de l’ordre de N^3).

      Dans le problème du voyageur de commerce, il y a un unique ensemble de points (graphe entre ces points) alors que pour le transport optimal, il y a 2 ensembles de points (graphe bipartite).

      Amitiés,

      Gabriel

      Répondre à ce message
      • Le transport optimal numérique et ses applications - Partie 1

        le 7 mai à 18:50, par B !gre

        Merci pour la réponse. Mon erreur était la suivante. Dans le problème du transport optimal, on dispose d’une matrice (de bi-adjacence) dans laquelle on cherche une permutation de poids minimal. Et je me disais que c’était exactement la même chose dans le voyageur de commerce, mais pour une matrice d’adjacence. Et dans ce cas, peu importe d’où vient la matrice (bi-adjacence d’un graphe biparti ou adjacence d’un graphe quelconque), le problème aurait été le même ! Mais l’erreur est que dans le voyageur de commerce, la permutation de poids minimal doit être circulaire, et non quelconque comme pour le transport optimal... Et ça fait donc une grosse différence en terme de complexité !

        Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?