optimisation combinatoire

L'optimisation combinatoire est un sous-domaine de l'optimisation mathématique qui consiste à trouver un objet optimal parmi un ensemble fini d'objets , où l'ensemble des solutions admissibles est discret ou peut être réduit à un ensemble discret. Parmi les problèmes d'optimisation combinatoire typiques, on peut citer le problème du voyageur de commerce (PVC), le problème de l'arbre couvrant minimal (ACM) et le problème du sac à dos . Dans nombre de ces problèmes, comme ceux mentionnés précédemment, la recherche exhaustive est impraticable ; il est donc nécessaire de recourir à des algorithmes spécialisés qui éliminent rapidement de larges portions de l'espace de recherche ou à des algorithmes d'approximation .

L'optimisation combinatoire est liée à la recherche opérationnelle , à la théorie des algorithmes et à la théorie de la complexité algorithmique . Elle trouve d'importantes applications dans plusieurs domaines, notamment l'intelligence artificielle , l'apprentissage automatique , la théorie des enchères , le génie logiciel , le VLSI , les mathématiques appliquées et l'informatique théorique .

Il existe une abondante littérature sur les algorithmes polynomiaux pour certaines classes particulières d'optimisation discrète. Une part importante de cette littérature est unifiée par la théorie de la programmation linéaire . Parmi les exemples de problèmes d'optimisation combinatoire couverts par ce cadre, on peut citer les problèmes de plus courts chemins et d'arbres de plus courts chemins , de flots et de circulations , d'arbres couvrants , de couplage et de matroïdes .

Pour les problèmes d'optimisation discrète NP-complets , la littérature de recherche actuelle aborde les sujets suivants :

• cas particuliers du problème considéré qui sont exactement solubles en temps polynomial (par exemple, des problèmes traitables à paramètre fixe )
• algorithmes performants sur des instances « aléatoires » (par exemple pour le problème du voyageur de commerce )
• algorithmes d'approximation qui s'exécutent en temps polynomial et trouvent une solution proche de l'optimum
• algorithmes d'approximation paramétrés qui s'exécutent en temps FPT et trouvent une solution proche de l'optimum
• résoudre des cas réels qui se présentent dans la pratique et qui ne présentent pas nécessairement le pire comportement des problèmes NP-complets (par exemple, des cas réels de TSP avec des dizaines de milliers de nœuds ).

Les problèmes d'optimisation combinatoire peuvent être vus comme la recherche du meilleur élément d'un ensemble discret d'éléments ; par conséquent, en principe, tout algorithme de recherche ou métaheuristique peut être utilisé pour les résoudre. Parmi les approches largement applicables, on trouve la méthode par séparation et évaluation (un algorithme exact qui peut être arrêté à tout moment et servir d'heuristique), la méthode par séparation et coupe (qui utilise l'optimisation linéaire pour générer des bornes), la programmation dynamique (une construction récursive de la solution avec une fenêtre de recherche limitée) et la recherche tabou (un algorithme d'échange de type glouton). Cependant, les algorithmes de recherche génériques ne garantissent ni la découverte immédiate d'une solution optimale, ni une exécution rapide (en temps polynomial). Étant donné que certains problèmes d'optimisation discrète sont NP-complets , comme le problème du voyageur de commerce (ou problème de décision) , ce résultat est prévisible sauf si P = NP .

À chaque problème d'optimisation combinatoire correspond un problème de décision qui cherche à déterminer s'il existe une solution réalisable pour une mesure donnée . Par exemple, dans un graphe contenant les sommets et , un problème d'optimisation pourrait être : « trouver un chemin de à utilisant le moins d'arêtes possible ». La solution à ce problème pourrait être, par exemple, 4. Le problème de décision correspondant serait : « Existe-t-il un chemin de à utilisant 10 arêtes ou moins ? » On peut répondre à ce problème par un simple « oui » ou « non ».

Le domaine des algorithmes d'approximation traite des algorithmes permettant de trouver des solutions quasi optimales à des problèmes difficiles. La formulation décisionnelle classique du problème s'avère alors inadéquate, car elle ne spécifie que des solutions acceptables. Bien qu'il soit possible d'introduire des problèmes de décision appropriés, le problème se caractérise alors plus naturellement comme un problème d'optimisation.

Un problème d'optimisation NP (NPO) est un problème d'optimisation combinatoire assorti des conditions supplémentaires suivantes. Il convient de noter que les polynômes mentionnés ci-dessous sont des fonctions de la taille des entrées des fonctions respectives, et non de la taille d'un ensemble implicite d'instances d'entrée.

• la taille de chaque solution réalisable , où désigne l'ensemble des solutions réalisables à l'instance , est polynomialement bornée par rapport à la taille de l'instance donnée ,
• Les langages des instances valides et des paires instance-solution valides peuvent être reconnus en temps polynomial , et
• La mesure d'une solution au problème est calculable en temps polynomial .

Cela implique que le problème de décision correspondant appartient à la classe NP . En informatique, les problèmes d'optimisation intéressants possèdent généralement les propriétés mentionnées ci-dessus et sont donc des problèmes NPO. Un problème est également appelé problème d'optimisation P (PO) s'il existe un algorithme qui trouve des solutions optimales en temps polynomial. Souvent, lorsqu'on traite de la classe NPO, on s'intéresse aux problèmes d'optimisation dont les versions de décision sont NP-complètes . Il est à noter que les relations de difficulté sont toujours définies par rapport à une réduction. En raison du lien entre les algorithmes d'approximation et les problèmes d'optimisation computationnelle, les réductions qui préservent l'approximation sous certains aspects sont préférées, dans ce contexte, aux réductions de Turing et de Karp classiques. La L-réduction en est un exemple . C'est pourquoi les problèmes d'optimisation dont les versions de décision sont NP-complètes ne sont pas nécessairement qualifiés de NPO-complets.

Les OPN sont divisées en sous-classes selon leur approximabilité :

• NPO(I) : Égal à FPTAS . Contient le problème du sac à dos .
• NPO(II) : Égal à PTAS . Contient le problème d'ordonnancement Makespan .
• NPO(III) : Classe des problèmes NPO admettant des algorithmes polynomiaux dont le coût est au plus c fois le coût optimal (pour les problèmes de minimisation) ou au moins égal au coût optimal (pour les problèmes de maximisation). Dans l’ouvrage de Hromkovič , * Algorithms for Hard Problems* , tous les problèmes NPO(II) sont exclus de cette classe, sauf si P=NP. Sans cette exclusion, cette classe est égale à APX. Elle inclut MAX-SAT et le problème du voyageur de commerce métrique .
• NPO(IV) : Classe des problèmes NPO admettant des algorithmes polynomiaux approchant la solution optimale par un rapport polynomial en logarithme de la taille de l'entrée. Dans l'ouvrage de Hromkovič, tous les problèmes NPO(III) sont exclus de cette classe, sauf si P = NP. Contient le problème de couverture d'ensembles .
• NPO(V) : Classe des problèmes NPO admettant des algorithmes polynomiaux approchant la solution optimale par un rapport borné par une fonction sur n. Dans l'ouvrage de Hromkovic, tous les problèmes NPO(IV) sont exclus de cette classe, sauf si P=NP. Contient le problème du voyageur de commerce (TSP) et le problème des cliques .

Un problème NPO est dit polynomialement borné (PB) si, pour toute instance et pour toute solution , la mesure est bornée par une fonction polynomiale de taille . La classe NPOPB est la classe des problèmes NPO qui sont polynomialement bornés.