Optimisation combinatoire

L’optimisation combinatoire est une branche de l'optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l'algorithmique et la théorie de la complexité. On parle également d’optimisation discrète.

Définition

Dans sa forme la plus générale, un problème d'optimisation combinatoire (on dit aussi d'optimisation discrète) consiste à trouver dans un ensemble discret un parmi les meilleurs sous-ensembles (ou solutions) réalisables, la notion de meilleure solution étant définie par une fonction objectif. Formellement, étant donnés :

• un ensemble discret N,
• une fonction d'ensemble $f: 2^N \rightarrow \mathbb R$, dite fonction objectif, et
• un ensemble $\mathcal R$ de sous-ensembles de N, dont les éléments sont appelés les solutions réalisables,

un problème d'optimisation combinatoire consiste à déterminer

$\max_{S \subseteq N} \{ f(S): \, S\in \mathcal R \}.$

L'ensemble des solutions réalisables ne saurait être décrit par une liste exhaustive car la difficulté réside ici précisément dans le fait que le nombre des solutions réalisables rend son énumération impossible, ou bien qu'il est NP-complet de dire s'il en existe ou non. La description de $\mathcal R$ est donc implicite, il s'agit en général de la liste, relativement courte, des propriétés des solutions réalisables.

La plupart du temps on est dans les cas particuliers suivants :

• $N = \{1,2,\ldots,n\}$ et $\mathcal R = X \cap \mathbb Z^n$ où $X \subset \mathbb R^n$ et la cardinalité de $\mathcal R$ est exponentielle en n,
• $\mathcal R = conv(\mathcal R)\cap \mathbb Z^n$ donc les propriétés de $\mathcal R$ se traduisent en contraintes linéaires, c'est-à-dire que X et un polyèdre de $\mathbb R^n$,
• $f(S)=\sum_{s\in S} f(s)$.

Exemple

Le problème du plus court chemin entre deux sommets s et t d'un graphe est un exemple classique de problème d'optimisation combinatoire. L'ensemble des solutions réalisables est l'ensemble des chemins entre s et t tandis que la fonction objectif est la longueur du chemin.

Résolution

Trouver une solution optimale dans un ensemble discret et fini est un problème facile en théorie : il suffit d'essayer toutes les solutions, et de comparer leurs qualités pour voir la meilleure. Cependant, en pratique, l'énumération de toutes les solutions peut prendre trop de temps ; or, le temps de recherche de la solution optimale est un facteur très important et c'est à cause de lui que les problèmes d'optimisation combinatoire sont réputés si difficiles. La théorie de la complexité donne des outils pour mesurer ce temps de recherche. De plus, comme l'ensemble des solutions réalisables est défini de manière implicite, il est aussi parfois très difficile de trouver ne serait-ce qu'une solution réalisable.

Quelques problèmes d'optimisation combinatoire peuvent être résolus (de manière exacte) en temps polynomial par exemple par un algorithme glouton, un algorithme de programmation dynamique ou en montrant que le problème peut être formulé comme un problème d'optimisation linéaire en variables réelles.

Dans la plupart des cas, le problème est NP-difficile et, pour le résoudre, il faut faire appel à des algorithmes de branch and bound, à l'optimisation linéaire en nombres entiers ou encore à la programmation par contraintes. En pratique, on se contente très souvent d'avoir une solution approchée, obtenue par une heuristique ou une métaheuristique. Pour certains problèmes, on peut prouver une garantie de performance, c'est-à-dire que l'écart entre la solution obtenue et la solution optimale est borné.