Nous nous intéressons au problème de gérer les aléas dans un problème d'optimisation, par exemple un problème de transport. Cet aléa est souvent modélisé par une loi de distribution ou un ensemble de scénario. À partir de ces informations, on peut classiquement utiliser des techniques d'optimisation stochastique (par exemple minimiser la moyenne des coûts d'une solution, connaissant la distribution de probabilité des coûts), ou l'optimisation robuste (minnimiser le coût d'une solution dans le pire scénario possible pour cette solution). Nous utilisons ici une technique récente mélangeant les deux techniques cités : l'optimisation distributionnellement robuste (ou DRO), qui consiste, connaissant un ensemble de distributions, à trouver une solution réalisable dont le coût moyen dans la pire distribution est minimum. Cette technique se révèle utile quand la distribution des aléas est inconnue ou difficile à maîtriser.
Nous avons conçu un framework qui, à partir d'un problème d'optimisation quelconque modélisé par un PLNE en variables binaires, produit un problème DRO équivalent au problème de départ où des aléas peuvent survenir sur la fonction objectif du programme linéaire. On construit par exemple le problème de plus court chemin distributionnellement robuste où il faut trouver un chemin entre deux points qui soit robuste aux aléas, ou le problème de sac à dos distributionnellement robuste où l'objectif est de résoudre un problème de sac à dos où les utilités des objets sont soumises à de l'aléa. L'ensemble des distributions est obtenu en construisant premièrement une distribution centrale $\hat{P}$ à partir d'un ensemble de données empiriques, puis en considérant, dans l'espace des distributions, l'ensemble des distributions autours de $\hat{P}$ à une distance $\varepsilon$ donnée, en utilisant comme métrique la distance de Wasserstein. Nous avons montré que le problème d'optimisation distributionnellement robuste obtenu concerve les propriétés de complexité algorithmique, d'approximabilité et de complexité paramétrée du problème de départ. Ainsi si le problème de départ est polynomial, sa version DRO l'est également.