Méthodes pour l’optimisation combinatoire

Méthodes pour l’optimisation combinatoire

Dans le précédent chapitre nous avons présenté un problème inhérent à la conception /reconfiguration des lignes d’usinage sans évoquer les moyens offerts par la recherche opé- rationnelle pour le résoudre. Dans le présent chapitre, nous présentons d’abord une intro- duction à la théorie de la complexité pour sensibiliser le lecteur à la difficulté du problème posé. Ensuite, nous rapportons les méthodes les plus utilisées pour ce type de problèmes. Nous développons particulièrement les schémas basés sur les procédures de type séparation et évaluation car ce sont celles-ci que nous employons dans nos travaux.La théorie de la complexité s’intéresse de façon générale aux problèmes de l’optimisation combinatoire et de façon plus particulière aux problèmes de décision qui leur correspondent. Les problèmes d’optimisation se caractérisent par des contraintes à satisfaire et un objectif à minimiser ou à maximiser. Pour les résoudre à l’optimum, il est toujours possible de parcourir tout l’espace de recherche en analysant toutes les solutions réalisables1 pour ne garder que la meilleure du point de vue de l’objectif défini. Un problème de décision est un problème pour lequel il n’y a que deux réponses possibles : oui ou non. Le problème de décision compare, en général, une valeur fixe à la valeur que peut prendre la fonction objectif. La procédure la plus basique pour y répondre est de parcourir tout l’espace des solutions réalisables (ce qui correspond au pire des cas). Ce processus permet, entre autres, de trouver une (voire plusieurs) solution(s) satisfaisant à la condition, dans ce cas, le processus de recherche est arrêté et la réponse donnée est positive. Toutefois si aucune solution parcourue n’est faisable, après que la totalité de l’espace de recherche ait été parcouru, alors une telle valeur n’existe pas et la réponse à donner est négative.

Au sens de l’effort de calcul nécessaire, les problèmes d’optimisation sont au moins aussi difficile que les problèmes de décision qui leur correspondent. En effet, la résolution à l’op- timum des problèmes d’optimisation nécessitent une énumération complète de l’espace de recherche (à moins d’avoir une preuve de la sous-optimalité de certains espaces qui pour- raient, de ce fait, être ignorés). Par contre, pour des problèmes de décision, celle-ci dépend essentiellement de la valeur de l’objectif recherchée, ainsi l’exploration s’arrête dès qu’une telle solution est trouvée. Par conséquent, au mieux le problème de décision est plus facile que le problème d’optimisation correspondant. Au pire des cas, il lui est équivalent. Ainsi, même si la théorie de la complexité a été conçue pour les problèmes de décision, ses résultats sont aussi valables pour les problèmes d’optimisation correspondants. La complexité d’un algorithme est définie par le temps de calcul nécessaire à son exécu- tion pour la résolution d’un problème d’une taille donnée. Ce temps est, en réalité, exprimé en fonction du nombre d’instructions élémentaires nécessaires à l’exécution de l’algorithme par le processeur. Le choix de cette mesure est justifié par le fait que le nombre d’instruc- tions est indépendant de la puissance des machines qui détermine le temps de calcul effectif. La théorie de la complexité s’intéresse, entre autres, à l’ordre de grandeur de la complexité dans le pire des cas qui est dite en grand O. Pour estimer la complexité d’un algorithme, en grand O, il suffit de borner le nombre d’instructions élémentaires qu’il engendre. Cette borne est exprimée en fonction de la taille des données n, et lorsqu’elle s’écrit en p(n) tel que p(n) est une fonction polynomiale, l’algorithme est dit polynomial et sa complexité est donnée par O(p(n)) . Notons que lorsque celle-ci est linéaire la complexité est également dite linéaire. Il existe d’autres types de complexité, par exemple : l’exponentielle soit en O(an). Les algorithmes de complexité en O(n!) ou en O(nlogn) sont également considérés comme des algorithmes de complexité exponentielle.Jusqu’à présent, nous n’avons abordé que la complexité des algorithmes de résolution, cependant, il est important de la distinguer de la complexité des problèmes eux-mêmes, et ce même si la complexité d’un problème est directement liée à celle de ses algorithmes. De manière informelle, la complexité d’un problème est déterminée par celle du meilleur algorithme connu qui le résout [Pas05]. Dans la suite, nous expliquons plus en détail ce lien en distinguant les deux classes de problèmes qui en découlent, la classe P qui contient les problèmes faciles et la classe NP qui comportent ceux qui sont dits difficiles.