Cet articlene cite pas suffisamment ses sources(juin 2013).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant lesréférences utiles à savérifiabilité et en les liant à la section « Notes et références ».

En pratique :Quelles sources sont attendues ?Comment ajouter mes sources ?

L’optimisation combinatoire (sous-ensemble à nombre de solutions finies de l'optimisation discrète) est une branche de l'optimisation enmathématiques appliquées et eninformatique, également liée à larecherche opérationnelle, l'algorithmique et lathéorie de la complexité.

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

• unensemble discret${\displaystyle N}$ fini;
• une fonction d'ensemble${\displaystyle f:2^N\to \mathbb{R}}$, ditefonction objectif ;
• et un ensemble${\displaystyle \mathcal{R}}$ de sous-ensembles de${\displaystyle N}$, dont les éléments sont appelés lessolutions réalisables,

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

${\displaystyle \underset{S\subseteq N}{max}\{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 estNP-complet de dire s'il en existe ou non. La description de${\displaystyle \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 :

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

Le problème duvoyageur de commerce (TSP) où un voyageur de Commerce doit parcourir les N villes d'un pays en effectuant le trajet le plus court. Une résolution par énumération nécessite de calculer ((N-1)!)/2 trajets entre des villes. En particulier, pour 24 villes, il faudrait en générer (23!)/2${\displaystyle \approx }$ 2,5×10²². Pour fournir un ordre de grandeur comparatif, une année ne compte qu'environ 3,16×10¹³ microsecondes.

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. Lathé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 unalgorithme glouton, un algorithme deprogrammation dynamique^[1] 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 estNP-difficile et, pour le résoudre, il faut faire appel à des algorithmes debranch and bound, à l'optimisation linéaire en nombres entiers ou encore à laprogrammation par contraintes.

En pratique, la complexité physiquement acceptable n'est souvent que polynomiale. On se contente alors d'avoir une solution approchée au mieux, obtenue par uneheuristique ou unemétaheuristique.

Pour le problème du VRP envisagé à large échelle,Richard Karp zone les villes, résout le problème zone par zone, puis assemble au mieux les parcours locaux.

Pour un problème d'optimisation d'affectation d'équipages, l'optimisation linéaire en variables réelles dégrossit le problème : on considère comme définitives les valeurs des variables ainsi collées aux extrêmes de leur domaine, et on n'applique les méthodes d'optimisation combinatoire que sur le problème résiduel.

Pour certains problèmes, on peut prouver unegarantie de performance, c'est-à-dire que pour une méthode donnée l'écart entre la solution obtenue et la solution optimale est borné. Dans ces conditions, à domaine égal, un algorithme est préférable à un autre si, à garantie égale ou supérieure, il est moins complexe.

v ·m Informatique théorique
Codage	Codage de l'information Compression de données Chiffrement Cryptanalyse Cryptographie Théorie de l'information
Modèles de calcul	Calculabilité Décidabilité et indécidabilité Ensemble récursif Problème de l'arrêt Ensemble récursivement énumérable Machine de Turing Thèse de Church Automate cellulaire Réseau de neurones artificiels Réduction polynomiale Problème NP-complet Principe de Church-Turing-Deutsch
Algorithmique	Algorithmique Algorithme glouton Algorithme probabiliste Algorithme génétique Complexité algorithmique Analyse d'algorithme Diviser pour régner Heuristique Programmation dynamique Géométrie algorithmique Algorithmes de tri Algorithmique du texte Exploration de données Science des données Apprentissage profond Test de primalité Structure de données Arbre enraciné Concurrence Parallélisme
Syntaxe	Réécriture Compilation Expression régulière Grammaire formelle Langage rationnel Ensemble rationnel Théorie des langages Théorie des automates Automate fini Automate sur les mots infinis Automate d'arbres Automate à pile Hiérarchie de Chomsky Linguistique informatique
Sémantique	Interprétation abstraite Méthodes formelles Vérification de modèles Sémantique des langages de programmation Sémantique dénotationnelle Sémantique axiomatique Sémantique opérationnelle
Logique mathématique	Assistant de preuve Calcul des prédicats Correspondance de Curry-Howard Fonction récursive Lambda-calcul Théorèmes d'incomplétude de Gödel Théorie des types
Mathématiques discrètes	Combinatoire Algorithme du simplexe Optimisation combinatoire Théorie des graphes Algorithmes de la théorie des graphes Recherche opérationnelle Théorie de la décision Analyse numérique

v ·m Optimisation:théorie etalgorithmes
Non linéaire	Méthode du nombre d'or Recherche linéaire Méthode de Nelder-Mead Critères de Wolfe Méthode de Broyden-Fletcher-Goldfarb-Shanno Algorithme à régions de confiance Pénalisation Algorithme du gradient Algorithme du gradient stochastique Méthode de Newton Algorithme de Gauss-Newton Algorithme de Levenberg-Marquardt Algorithme du lagrangien augmenté
Convexe	Optimisation complètement positive Optimisation copositive Optimisation SDP Méthode des plans sécants Algorithme de Frank-Wolfe Méthode de l'ellipsoïde Linéaire Optimisation conique Algorithme du simplexe Méthodes de points intérieurs Décomposition de Benders Génération de colonnes Quadratique Optimisation quadratique successive
Combinatoire	Algorithme d'approximation Programmation dynamique Algorithme glouton Optimisation linéaire en nombres entiers
Métaheuristique	Stratégie d'évolution Algorithme génétique Essaims Forêts aléatoires Boosting

• Portail des mathématiques
• Portail de l'informatique théorique

• Optimisation combinatoire
• Recherche opérationnelle

• Article manquant de références depuis juin 2013
• Article manquant de références/Liste complète
• Portail:Mathématiques/Articles liés
• Portail:Sciences/Articles liés
• Portail:Informatique théorique/Articles liés
• Portail:Informatique/Articles liés