Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Catégorie
Optimisation combinatoire
Résumé
L’optimisation combinatoire, (sous-ensemble à nombre de solutions finies de l'optimisation discrète), 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é.
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 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 fini;
une fonction d'ensemble , dite fonction objectif ;
et un ensemble de sous-ensembles de , dont les éléments sont appelés les solutions réalisables,
un problème d'optimisation combinatoire consiste à déterminer
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 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 :
et où et la cardinalité de est exponentielle en ;
donc les propriétés de se traduisent en contraintes linéaires, c'est-à-dire que et un polyèdre de ;
Le problème du voyageur 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 2,5×1022. Pour fournir un ordre de grandeur comparatif, une année ne compte qu'environ 3,16×1013 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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.