182
Recherche opérationnelle
existe-t-il une fonction f sur l'ensemble des
avec
telle que toutes les
clauses soient satisfaites ? est un problème NP-complet. Si on trouve un algorithme
polynomial pour ce problème de logique, alors on trouve des algorithmes polynomiaux
pour de nombreux problèmes combinatoires de la recherche opérationnelle.
Cela dit, la présomption la plus couramment admise est qu'il n'existe pas d'algorithmes
polynomiaux pour ces problèmes NP-complets et que l'on risque fort de ne pas trouver
de méthode efficace (polynomiale) pour résoudre les problèmes que nous avons évoqués
(voyageur de commerce, programme linéaire en nombres entiers, par exemple, le
premier étant fortement réductible au second).
Dans la pratique, il peut être utile de démontrer qu'un problème auquel on est confronté
est NP-complet : cela signifie que ce n'est sans doute pas la peine de se fatiguer pour
trouver un algorithme polynomial, à moins de concourir pour la médaille Fields.
La notion de problème NP-difficile étend celle de problème NP-complet aux problèmes
d'optimisation. On démontre que si un problème d'existence est NP-complet, alors le
problème d'optimisation correspondant est NP-difficile.
Les programmes linéaires en nombres entiers et le problème du voyageur de commerce
sont NP-difficiles.
Finalement, les procédures arborescentes, malgré leur élégance, n'assurent pas que l'on
puisse trouver l'optimum de ces problèmes dans un temps raisonnable, en tout cas
évidemment pour des exemples d'une certaine taille. C'est pourquoi de nombreux auteurs
ont proposé pour ce type de problème des heuristiques : méthodes d'exploration des
solutions qui conduisent à des calculs rapides et à des résultats dont on a lieu de penser
(mais sans en être jamais totalement certain) qu'ils sont proches de la solution optimale.
C'est l'objet du développement suivant.
8.2. METAHEURISTIQUES
Pour résoudre des problèmes combinatoires particulièrement difficiles (NP-difficiles
pour être précis), du type :
( représentant l'espace des contraintes ; par souci de simplification, on appellera
solution tout satisfaisant aux contraintes).
Plusieurs techniques ont été élaborées, souvent astucieuses, susceptibles de parvenir à
des solutions '' vraisemblablement '' proches de la solution optimale. On peut être
légitimement déçu par le fait qu'on ne recherche plus une solution rigoureusement
optimale ; il convient cela dit de souligner que ces '' métaheuristiques '', une fois
imaginées, sont testées systématiquement sur des cas de grande taille dont on connaît la
solution exacte si bien qu'on peut ne conserver, parmi les nombreuses idées explorées
par les chercheurs, que celles qui sont en quelque sorte confirmées par l'expérience.
Recherche opérationnelle
existe-t-il une fonction f sur l'ensemble des
avec
telle que toutes les
clauses soient satisfaites ? est un problème NP-complet. Si on trouve un algorithme
polynomial pour ce problème de logique, alors on trouve des algorithmes polynomiaux
pour de nombreux problèmes combinatoires de la recherche opérationnelle.
Cela dit, la présomption la plus couramment admise est qu'il n'existe pas d'algorithmes
polynomiaux pour ces problèmes NP-complets et que l'on risque fort de ne pas trouver
de méthode efficace (polynomiale) pour résoudre les problèmes que nous avons évoqués
(voyageur de commerce, programme linéaire en nombres entiers, par exemple, le
premier étant fortement réductible au second).
Dans la pratique, il peut être utile de démontrer qu'un problème auquel on est confronté
est NP-complet : cela signifie que ce n'est sans doute pas la peine de se fatiguer pour
trouver un algorithme polynomial, à moins de concourir pour la médaille Fields.
La notion de problème NP-difficile étend celle de problème NP-complet aux problèmes
d'optimisation. On démontre que si un problème d'existence est NP-complet, alors le
problème d'optimisation correspondant est NP-difficile.
Les programmes linéaires en nombres entiers et le problème du voyageur de commerce
sont NP-difficiles.
Finalement, les procédures arborescentes, malgré leur élégance, n'assurent pas que l'on
puisse trouver l'optimum de ces problèmes dans un temps raisonnable, en tout cas
évidemment pour des exemples d'une certaine taille. C'est pourquoi de nombreux auteurs
ont proposé pour ce type de problème des heuristiques : méthodes d'exploration des
solutions qui conduisent à des calculs rapides et à des résultats dont on a lieu de penser
(mais sans en être jamais totalement certain) qu'ils sont proches de la solution optimale.
C'est l'objet du développement suivant.
8.2. METAHEURISTIQUES
Pour résoudre des problèmes combinatoires particulièrement difficiles (NP-difficiles
pour être précis), du type :
( représentant l'espace des contraintes ; par souci de simplification, on appellera
solution tout satisfaisant aux contraintes).
Plusieurs techniques ont été élaborées, souvent astucieuses, susceptibles de parvenir à
des solutions '' vraisemblablement '' proches de la solution optimale. On peut être
légitimement déçu par le fait qu'on ne recherche plus une solution rigoureusement
optimale ; il convient cela dit de souligner que ces '' métaheuristiques '', une fois
imaginées, sont testées systématiquement sur des cas de grande taille dont on connaît la
solution exacte si bien qu'on peut ne conserver, parmi les nombreuses idées explorées
par les chercheurs, que celles qui sont en quelque sorte confirmées par l'expérience.