Complexité des algorithmes et des problèmes
Optimisation discrète

Résoudre un problème d’optimisation, c’est rechercher, parmi un ensemble de solutions qui vérifient des contraintes données, la ou les solutions qui rendent minimale (ou maximale) une fonction mesurant la qualité de cette solution. Cette fonction est appelée fonction-objectif. En général, pour modéliser un problème d’optimisation, on commence par définir les éléments qui composent les contraintes et la fonction objectif. Parmi ces éléments, certains sont connus et sont appelés paramètres du problème. On lit leur valeur dans des bases de données ou on les fournit dans des fichiers ou encore en les tapant au clavier d’un ordinateur. D’autres éléments sont inconnus et sont appelés inconnues ou variables. Les contraintes et la fonction objectif s’expriment à l’aide de formules mathématiques qui combinent les paramètres connus et les variables du problème. Les variables correspondent souvent à des décisions à prendre de manière à obtenir l’optimum souhaité. On parle d’optimisation continue (cf. [], si les variables représentant les décisions prennent leur valeur sur un ensemble continu de valeurs : par exemple, tous les réels contenus entre deux limites. On parle d’optimisation discrète si les variables prennent leur valeur dans un ensemble fini ou dans un ensemble dénombrable, comme par exemple l’ensemble des entiers. Dans le cas le plus général, une partie des variables sont continues et une autre partie des variables sont discrètes. C’est la difficulté des problèmes contenant des variables discrètes qui nous intéressent ici.

Nous présentons ici quatre problèmes concrets et nous les modélisons en utilisant des équations linéaires ou éventuellement quadratiques. Nous introduisons ensuite les notions de complexité d’algorithmes et de problèmes. La suite du dossier est composée de deux grandes parties.

Une partie est consacrée à la présentation de méthodes de résolution exacte, certaines sont polynomiales, spécifiques du problème « facile » considéré et donc utilisables même pour des problèmes de grandes tailles ; d’autres sont pseudo-polynomiales et encore utilisables pour des problèmes de tailles importantes ; enfin, des méthodes exponentielles, construites sur des schémas généraux, appelés procédures par séparation et évaluation ne peuvent être utilisées que sur des problèmes de taille relativement restreinte. Ce sont des méthodes exponentielles de ce type qui sont utilisées dans les solveurs généraux, à base de programmation linéaire ou de propagation de contraintes, qui sont actuellement disponibles sur le marché des progiciels. L’amélioration progressive de ces solveurs et l’augmentation spectaculaire de la rapidité des ordinateurs permettent actuellement de résoudre, avec ces progiciels, des problèmes de taille relativement importante. Néanmoins, la durée des exécutions augmente toujours exponentiellement avec la taille des problèmes.

Une deuxième partie est consacrée aux méthodes de résolution approchées, quand on accepte de ne plus avoir la preuve d’obtenir une solution optimale, mais que l’on espère utiliser des approches suffisamment astucieuses pour obtenir de très bonnes solutions. Nous présentons, en particulier, les méta-heuristiques les plus connues telles que le recuit simulé, la méthode Taboue et les algorithmes génétiques. Nous incitons également le lecteur à croiser les méthodes de manière à essayer d’obtenir les meilleurs résultats.