Comment l'optimisation combinatoire inverse transforme-t-elle la prise de décision et la planification stratégique ?

L’optimisation combinatoire, qui a longtemps été un pilier de la recherche opérationnelle, a évolué au fil du temps pour inclure un domaine en pleine expansion : les problèmes d’optimisation combinatoire inverse (ICOPs). Traditionnellement, l’optimisation combinatoire se concentre sur les problèmes d’optimisation directe, où l’on cherche à optimiser une fonction objective sous certaines contraintes. Cependant, la montée des ICOPs offre une nouvelle perspective, où l'on inverse le processus d'optimisation afin de déterminer les paramètres sous-jacents à partir des résultats observés. Cette approche inverse s'avère particulièrement utile dans des situations où ces paramètres sont inconnus ou cachés, comme dans les domaines de la conception de réseaux, de la logistique ou de la planification stratégique.

Le champ des ICOPs se divise en plusieurs catégories distinctes, chacune présentant des défis uniques tant sur le plan théorique que pratique. L’une des premières questions soulevées par l'optimisation inverse est la transition d’un problème d’optimisation direct à un problème inverse. Cela implique souvent une inversion du processus de calcul des solutions optimales en fonction des paramètres, ce qui est particulièrement complexe lorsque ces paramètres sont dissimulés ou difficilement mesurables. Cette complexité accrue nécessite une compréhension approfondie des structures sous-jacentes et des relations entre les différentes variables d’un modèle.

Les problèmes les plus étudiés dans le cadre des ICOPs sont ceux relatifs aux chemins les plus courts, aux arbres couvrants et aux problèmes de localisation de centres dans des réseaux. Par exemple, dans un problème inverse de chemin le plus court, l’objectif est de déterminer les poids des arêtes d’un graphe à partir de la solution optimale observée. Cela peut se traduire par une réestimation des coûts ou des contraintes qui ont permis d'atteindre ce chemin spécifique. Cette approche inverse est cruciale dans des applications pratiques comme l'optimisation des itinéraires de transport ou la gestion de flux dans des réseaux complexes.

De même, les problèmes d'optimisation inverse appliqués aux arbres couvrants portent sur la reconstruction de graphes de manière à ce que certaines conditions d'optimalité soient respectées, tout en étant guidé par des données issues de solutions existantes. Ce type de problème s’avère particulièrement utile pour améliorer les réseaux de communication ou d’électricité, où les solutions optimales ne sont souvent pas disponibles a priori et doivent être inférées à partir de configurations réelles.

Les applications des ICOPs ne se limitent pas à la simple reconstruction de solutions ; elles permettent aussi d’affiner et d’ajuster les modèles pour des objectifs spécifiques. Par exemple, dans la planification stratégique, l’optimisation inverse peut être utilisée pour identifier les ajustements nécessaires à un modèle d'affaires en fonction des résultats observés, offrant ainsi une base de réflexion plus solide pour les décisions futures.

Dans cette monographie, l'accent est mis sur les aspects théoriques et algorithmiques nécessaires pour aborder efficacement les ICOPs dans des situations réelles. L’objectif est de fournir aux chercheurs, praticiens et décideurs les outils nécessaires pour comprendre et résoudre des problèmes d’optimisation inverse dans divers contextes. En exposant les diverses catégories de ICOPs, cette œuvre aspire à offrir un cadre cohérent pour aborder cette branche de l’optimisation, souvent négligée mais pourtant essentielle.

Comment résoudre le problème inverse de l’arbre couvrant de poids minimal sous différentes normes

Le lien profond entre le problème de flot de coût minimal et le problème d'affectation permet d'établir une correspondance bijective entre les flots réalisables dans un graphe transformé $G'$ et les affectations réalisables dans le graphe d'origine $G_0$, avec une équivalence parfaite des coûts. Cette relation, exploitée par Sokkalingam et al., est cruciale pour formuler une solution optimale au problème inverse de l'arbre couvrant de poids minimal (Inv-MST).

Le vecteur $\alpha$ ainsi défini assigne à chaque sommet $i$ apparié dans le flot une valeur égale à $\pi(i)$, et zéro sinon. Cette approche permet de résoudre le problème inverse sous la norme $\ell_1$ non bornée avec un algorithme de complexité $O(n^3)$, utilisant l’algorithme des plus courts chemins successifs. L’efficacité de cette méthode repose sur l’application stratégique de l’algorithme de Dijkstra sur le graphe résiduel $G'(x)$, en mettant à jour les étiquettes de distance avec des longueurs d’arcs ajustées par la solution duale.

Dans le cas de la norme $\ell_\infty$ non bornée, Sokkalingam et al. proposent une formulation où l’on cherche à minimiser le plus grand écart absolu entre les poids initiaux et modifiés. En définissant les variables $\alpha_i = w^*_i - w_i$, le problème est reformulé en une minimisation du maximum des $|\alpha_i|$ sous contraintes d’ordre entre les poids, selon les cycles induits par les arêtes n'appartenant pas à l’arbre initial. Le théorème 9.4 établit que, en choisissant $\delta$ comme le plus grand écart admissible entre les poids dans ces cycles, une solution optimale s’obtient en assignant $-\delta/2$ aux arêtes de l’arbre et $\delta/2$ aux autres. Cette solution est réalisable en temps $O(n^2)$.

La généralisation de ces approches à différents types de normes ( $\ell_1$, $\ell_\infty$, Hamming pondérée) et contraintes (bornées ou non, pondérées ou non) révèle la richesse structurelle du problème inverse de l’arbre couvrant de poids minimal. Elle met en évidence une stratégie algorithmique commune : transformer le problème inverse en un problème primal-dual bien connu (flot, affectation, couverture), en exploitant les propriétés spécifiques du graphe et des contraintes.