Introduction
Ce module s'intéresse aux méthodes exactes classiques employées en optimisation combinatoire. Pour chaque méthode nous rappelons les principes de base. Des problèmes d'ordonnancement et de sac-à-dos, précédemment présentés, sont introduits comme des exemples d'application afin d'illustrer ces principes.
Nous nous sommes intéressés principalement à trois sous-classes de méthodes :
⋆ procédure de séparation et d'évaluation,
⋆ programmation dynamique,
⋆ programmation linéaire en nombres entiers ou en nombres mixtes.
De telles méthodes sont généralement utilisées/adaptées pour aborder des problèmes de petite ou de moyenne taille. Dans ce cas, le nombre de combinaisons réalisables est suffisamment faible/réduit, ce qui permet d'explorer l'espace des solutions en un temps raisonnable. Autrement, il est difficile d'éviter le phénomène d'explosion combinatoire caractérisant les problèmes NP-difficiles d'optimisation combinatoire. Comme nous allons le constater à travers les exemples de ce module, les méthodes présentées se basent sur le concept de l'exploration implicite. Ce concept consiste à éviter l'exploration inutile de certaines parties dominées de l'espace de recherche permettant ainsi de réduire le nombre de solutions à visiter ou à générer. Cette réduction conduit à une diminution du temps d'exécution de l'algorithme utilisé. D'une manière générale, on s'appuie sur des propriétés et des relations de dominance intrinsèques au problème étudié pour construire une solution optimale ou prouver rapidement qu'elle est optimale.
Ces techniques peuvent être adaptées à de nombreux problèmes NP-difficiles. Toutefois, il faudrait préalablement vérifier la complexité du problème étudié avant de se lancer dans la conception de tels algorithmes. En effet, de nombreux problèmes combinatoires peuvent s'avérer polynomiaux en analysant leurs structures et leurs propriétés (recherche d'un plus court chemin dans un graphe avec l'algorithme de Dijkstra, calcul d'un arbre couvrant de poids minimum dans un graphe avec l'algorithme de Prim, détermination d'une affectation de coût minimal avec l'algorithme hongrois, minimisation de la somme pondérée des dates de fin des tâches sur une machine avec des dates d'arrivée identiques avec la règle de Smith,...). Dans les chapitres précédents sur les graphes [Portmann 2013], certains de ces problèmes ont été exposés avec les solutions correspondantes.
Il est également important de noter que dans certains cas, la programmation dynamique peut servir à montrer qu'un problème est polynomial (exemple : quand on a réussi la conception d'un algorithme polynomial de programmation dynamique pour résoudre un tel problème).
