L’optimisation mathématique

Article 1
A chaque problème son algorithme
Rail & Recherche n°23 - avril/mai/juin 2002

Deux facteurs ont contribué à relancer l’intérêt pour l’optimisation mathématique : d’abord l’accroissement prodigieux de la puissance de calcul des ordinateurs, mais aussi l’arrivée d’algorithmes plus performants. Notamment lorsque les solutions recherchées sont dites “discrètes”, c’est-à-dire lorsqu’elles se présentent sous la forme de choix binaires (j’engage telle locomotive sur tel train ou sur tel autre train). Un cas de figure plus fréquent et malheureusement plus complexe à traiter que les problèmes “à variables continues”.
“Les problèmes faciles sont ceux pour lesquels on sait qu’il existe une méthode exacte qui peut résoudre le problème en un temps polynomial : si vous avez des données de taille n, le temps de calcul sera proportionnel à une puissance de n (n2, n3, etc.)”, précise David De Almeida à la direction de l'Innovation & de la Recherche de la SNCF.

Des temps de calcul exponentiels

Pour les problèmes difficiles, les méthodes exactes requièrent un temps de calcul exponentiel : si un problème de taille 10 exige une minute de résolution, un problème de taille 100 pourra demander plusieurs jours, voire plusieurs semaines. On est très vite dépassé. D’où la nécessité de recourir à des algorithmes "approchés", qui n’ont pas pour ambition de trouver la solution optimale, mais une solution satisfaisante qui s’en approche.
L’astuce, dans un problème à variables discrètes comme un programme linéaire en nombres entiers, sera par exemple d’autoriser des choix continus. En clair, de permettre au programme d’affecter une moitié ou un tiers de locomotive à un train donné. Les calculs, plus faciles, livrent une solution bien sûr inadmissible, mais qui fixe le gain ultime d’efficacité que l’on ne peut pas dépasser. La solution au problème réel, dans lequel les locomotives restent entières, est alors calculée, par exemple, en arrondissant la solution continue du problème plus général que l’on vient de résoudre. L’algorithme permet alors de chiffrer l’écart entre la solution approchée qu’il fournit dans ce cas particulier et la solution idéale du problème à variables continues.

Méthodes exactes ou heuristiques

La combinatoire du problème peut aussi être explorée par une autre famille de méthodes, appelées métaheuristiques, comme le recuit simulé*, les algorithmes génétiques, etc. Ces méthodes reposent sur des principes généraux qui doivent être adaptés au problème étudié et sur un paramétrage parfois délicat à régler. Elles permettent de trouver des solutions admissibles et approchées en termes d’optimisation,
sans toutefois offrir une garantie sur la qualité de ces solutions.
Une dernière catégorie d’algorithmes, enfin, s’appuie non pas sur des mathématiques, mais sur des principes très généraux, sur un ensemble de "trucs" issus du bon sens, mais dont l’efficacité ne peut pas toujours être chiffrée.

"Dans le cas d’un voyageur de commerce qui veut minimiser la distance qu’il parcourt, on peut se dire qu’après un point donné, le prochain où il se rendra sera le plus proche. Cela semble logique, mais rien ne dit que globalement c’est le choix le plus intéressant", explique David De Almeida.
Le choix d’un algorithme exact, approché ou heuristique** dépend bien souvent du temps dont on dispose pour trouver la solution : plusieurs minutes pour la planification d’un roulement ou quelques secondes en opérationnel, lorsqu’un incident perturbe le plan de transport prévu. Un impératif qui conduit, lorsque l’ensemble des solutions disponibles est vaste, à des stratégies différentes. Si le programme dispose de plusieurs heures, il pourra explorer patiemment l’ensemble des choix possibles. En revanche, si le temps manque, il ne testera qu’un ensemble réduit de combinaisons possibles pour atteindre plus rapidement une solution admissible. L’algorithme le plus performant n’étant pas forcément celui qui donne la meilleure solution, mais celui qui en donne au moins une dans le temps imparti.

*Recuit simulé : technique d’exploration de l’espace des solutions dans laquelle les déplacements successifs entre solutions reposent sur une démarche probabiliste.

**Du grec "heuriskien" qui signifie trouver. Cette démarche s’appuie sur le bon sens et l’expérience qui permettent de résoudre des problèmes théoriquement difficiles