Optimisation combinatoire


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 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é.


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Optimisation combinatoire de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Optimisation multi-objectif — L optimisation multiobjectif est branche de l optimisation combinatoire dont la particularité est de chercher à optimiser simultanément plusieurs objectifs d un même problème (contre un seul objectif pour l optimisation combinatoire classique).… …   Wikipédia en Français

  • Optimisation (mathematiques) — Optimisation (mathématiques) En mathématiques, l optimisation est l’étude des problèmes qui sont de la forme : Étant donné : une fonction d’un ensemble A dans l ensemble des nombre réels Rechercher : un élément x0 de A tel que pour …   Wikipédia en Français

  • Optimisation (informatique) — Optimisation de code En programmation informatique, l optimisation est la pratique qui consiste généralement à réduire le temps d exécution d une fonction, l espace occupé par les données et le programme, ou la consommation d énergie. La règle… …   Wikipédia en Français

  • Optimisation du code — Optimisation de code En programmation informatique, l optimisation est la pratique qui consiste généralement à réduire le temps d exécution d une fonction, l espace occupé par les données et le programme, ou la consommation d énergie. La règle… …   Wikipédia en Français

  • Optimisation (mathématiques) — L optimisation est une branche des mathématiques, cherchant à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à déterminer le meilleur élément d un ensemble, au sens d un critère quantitatif donné. Ce mot vient …   Wikipédia en Français

  • Optimisation multiobjectif — L optimisation multiobjectif est une branche de l optimisation combinatoire dont la particularité est de chercher à optimiser simultanément plusieurs objectifs d un même problème (contre un seul objectif pour l optimisation combinatoire… …   Wikipédia en Français

  • Combinatoire — Pour les articles homonymes, voir combinatoire (homonymie). Une planche de l encyclopédie de Diderot et d Alembert illustrant l article « Carreleur » …   Wikipédia en Français

  • Optimisation linéaire — En optimisation, qui est une branche des mathématiques, un problème d optimisation linéaire est un problème d optimisation dans lequel on minimise une fonction linéaire sur un polyèdre convexe. La fonction coût et les contraintes peuvent donc… …   Wikipédia en Français

  • Optimisation de code — En programmation informatique, l optimisation est la pratique qui consiste généralement à réduire le temps d exécution d une fonction, l espace occupé par les données et le programme, ou la consommation d énergie. La règle numéro un de l… …   Wikipédia en Français

  • Optimisation difficile — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.