Tirer le meilleur parti de l’optimisation

​J’ai commencé l’université à l’automne 1984 avec l’idée bien précise de poursuivre des études en informatique. C’était « l’avenir », comme le disaient nombre de mes aînés à l’époque; je me suis donc dit que ces études me lanceraient vers une carrière brillante de développeur de logiciels. Mon université avait la particularité d’avoir une faculté de mathématiques dont l’un des départements était l’informatique. (On nous avait dit alors qu’une seule autre université dans le monde possédait aussi une faculté des mathématiques… à Moscou). Bref, cela voulait dire que pour étudier l’informatique, je devais obtenir un baccalauréat en mathématiques.

Cette faculté était divisée en cinq départements : mathématiques pures (algèbre et théorie des nombres), mathématiques appliquées (fonctions et calcul), statistiques, informatique et optimisation combinatoire. Ce dernier département était plutôt étrange et mystérieux avec ses programmes sur la théorie de l’énumération et l’optimisation, ainsi que diverses disciplines qui semblaient n’être reliées à aucune autre formation, comme la théorie des graphes, la théorie des jeux et la cryptographie. Pour une raison que j’ignore, le cours obligatoire de deuxième année a capté mon attention. J’ai décidé de passer à une majeure composée d’une formation en optimisation combinatoire et en informatique afin de pouvoir choisir un sous-ensemble de cours obligatoires provenant des deux départements.

Un peu moins de trois décennies et demie après l’obtention de mon diplôme et bien avancé dans une carrière qui a très peu à voir avec le développement de logiciels, me voici en train de ressortir mes vieux manuels d’optimisation combinatoire et mes notes de cours (oui, oui, je les ai encore). Domaine émergent, l’informatique quantique a une importante incidence sur la cryptographie, tandis que l’optimisation est en train de devenir l’un des premiers cas d’utilisation avantageux pour l’application des techniques de programmation quantique. Je peux enfin mettre mes études académiques en pratique!

L’essentiel
Alors, qu’est-ce que l’optimisation et pourquoi est-elle si importante? Un article de Wikipédia en anglais indique que c’est « la sélection d’un meilleur élément, en fonction de certains critères, à partir d’un ensemble d’autres possibilités ». Euh… D’accord. Ce même article explique ensuite que « l’optimisation consiste notamment à trouver les “meilleures valeurs disponibles” d’une fonction objective selon un domaine donné, incluant différents types de fonctions objectives et de domaines ». Hum… Quelqu’un devrait peut-être éclaircir ces explications. Je comprends maintenant pourquoi mes enfants avaient le regard perdu quand je leur ai expliqué ce que j’étudiais dans ma jeunesse.

Bon, mettons les mathématiques de côté et examinons quelques exemples pratiques.

L’un des problèmes d’optimisation les mieux connus est l’histoire du vendeur itinérant. Celui-ci doit quitter sa ville de résidence pour se rendre à un certain nombre d’autres municipalités afin d’effectuer des appels de vente avant de terminer son voyage à une destination donnée. Les villes sont reliées par des routes et vous connaissez le coût du déplacement de l’une ville à l’autre (temps passé sur la route, prix de l’essence, etc.). Pouvez-vous calculer le trajet que le vendeur devrait prendre pour visiter un nombre précis de villes et arriver à destination au plus faible coût possible? S’il s’agit d’un vendeur qui ne doit visiter que quelques villes, la réponse est probablement oui. Mais qu’arrive-t-il s’il est plutôt question de nombreux livreurs de colis et qu’au lieu de quelques villes, ces personnes doivent se rendre à des douzaines d’entrepôts et à des milliers de destinations partout sur le continent? Voilà ce qu’on appelle un problème d’optimisation fort complexe.

Analysons un autre exemple. Disons que vous êtes un conseiller financier responsable du portefeuille de votre client. Vous offrez différents types de placements (actions, obligations, etc.), chacun ayant sa possibilité de retour et son risque de perte. Chaque placement est également assorti à un prix d’acquisition. Votre client dispose d’un montant d’argent fixe à investir et vous a indiqué son profil de risque, soit le montant qu’il est à l’aise de perdre et la probabilité de gains qu’il préfère. Comment acquérir des placements qui optimiseront le retour de votre client tout en réduisant au minimum son risque de perte? C’est peut-être réalisable si le client est débonnaire et que son portefeuille est petit. Mais qu’arrive-t-il si son portefeuille compte des centaines de millions de dollars, que vous travaillez pour des milliers de clients ayant différents profils de risque et qu’on ajoute à cela des dérivés et d’autres instruments financiers complexes? La solution optimale n’est soudainement plus si évidente.

Voilà ce qu’est l’optimisation : elle permet de trouver la meilleure solution pour réduire le coût au minimum (ou maximiser la valeur) en fonction d’un grand nombre de variables et de contraintes. La logistique et la finance, comme dans les exemples ci-dessus, sont deux cas d’utilisation évidents, mais les problèmes d’optimisation se posent à peu près partout où une organisation doit attribuer des ressources limitées à des intérêts concurrents. Le fait est que cette science n’est pas exacte. Les problèmes d’optimisation courants comme ceux ci-dessus sont souvent réglés approximativement. Pourquoi? Je ne parlerai pas des mathématiques qui sont en cause, mais l’indice se trouve dans la référence vague de l’article de Wikipédia : trouver la meilleure solution disponible.

Le travail
Les équations que les mathématiciens utilisent pour résoudre de nombreux problèmes d’optimisation ont souvent plusieurs solutions, dont certaines sont meilleures que d’autres. On les appelle les minima locaux, et la meilleure solution possible est le minimum global. Pour illustrer cela, imaginez une très grande feuille de caoutchouc étirée. À différents endroits sur cette feuille, vous placez des billes de poids variés. Chaque bille crée une empreinte dans la feuille de caoutchouc d’une profondeur variant selon le poids de l’objet. Visualisez maintenant une fourmi se promenant sur la feuille en essayant de trouver la bille la plus lourde qui crée l’empreinte la plus profonde, soit le minimum global. Elle trouvera des billes de poids variés créant différentes empreintes, soit les minima locaux, et pourrait, ou non, tomber sur le minimum global.

La fourmi sur la feuille de caoutchouc est en fait un programme d’ordinateur qui tente de résoudre l’équation d’un problème d’optimisation. Dans une période donnée, il peut trouver la meilleure solution disponible, mais ce n’est pas garanti qu’il trouvera la meilleure solution possible. Avec plus de temps et de capacité de traitement, il peut obtenir un meilleur résultat, mais la complexité de ces problèmes se heurte éventuellement aux limites pratiques de la loi de Moore et on ne peut pas toujours être certain d’avoir trouvé la meilleure solution. Pour illustrer la complexité, si le vendeur itinérant du problème cité plus haut ne visite que 15 villes une fois seulement, il y aurait déjà plus de 87 milliards de trajets possibles entre ces villes. Sur un ordinateur classique, on estime à jusqu’à deux décennies le temps nécessaire pour résoudre ce problème avec 15 000 villes.

Les mathématiciens et les informaticiens peuvent passer toute leur carrière à peaufiner leurs algorithmes pour tenter d’améliorer légèrement les optimisations. Une des histoires qui circulait à mon université était celle d’un professeur qui avait été embauché par une municipalité pour optimiser ses trajets de collecte des ordures. Il a travaillé sans répit sur le problème et a trouvé une solution, puis a constaté que les conducteurs de camion-benne de la ville obtenaient un meilleur résultat que le sien. Il a recommencé ses calculs et trouvé une autre solution, mais celle des conducteurs était encore meilleure. Enfin, il a décidé de faire le trajet avec eux un soir et a découvert qu’au petit matin, en l’absence de bouchons de circulation, les conducteurs prenaient des raccourcis en reculant dans des rues à sens unique, une amélioration créative, bien que pas tout à fait légitime, par rapport aux mathématiques.

Le calcul des chiffres
Les problèmes d’optimisation sont exactement la sorte de mathématiques difficiles qu’un ordinateur quantique peut facilement traiter. Lorsqu’ils deviendront disponibles, les grands ordinateurs quantiques pourraient très bien accélérer nos algorithmes et permettre aux mathématiciens de trouver de bien meilleures solutions d’optimisation. Il reste toutefois quelques années avant que le matériel requis soit offert et beaucoup de travail à faire pour résoudre les problèmes de bruit et de correction d’erreurs. De petits ordinateurs quantiques de quelques centaines de qubits (bits quantiques) sont offerts aujourd’hui à ceux qui ne veulent pas attendre et qui y ont accès; malgré leur taille, ils peuvent quand même apporter des améliorations graduelles par rapport aux méthodes classiques. Sinon, le recuit quantique et l’optimisation inspirée de la quantique sont des services offerts en infonuagique qui produisent de bonnes solutions intermédiaires.

En physique, le recuit est le processus de chauffage, puis de refroidissement lent d’une matière comme le métal ou le verre. Cette méthode élimine les contraintes internes de la matière pour réduire sa friabilité et augmenter sa flexibilité. Le recuit quantique est la version adaptée aux mathématiques des qubits dans un ordinateur quantique. Un recuiseur quantique crée un modèle mathématique de votre problème d’optimisation dans un système de qubits. En raffinant graduellement les paramètres et les variables du modèle, le système peut continuer d’atteindre de meilleurs minima locaux et accroître ses chances de trouver le minimum global. Si on revient à la fourmi sur la feuille de caoutchouc, l’avantage du recuiseur est sa capacité de se servir des effets quantiques pour réduire le nombre de fois où la fourmi doit ressortir d’une empreinte et parfois simplement pour passer d’une empreinte à l’autre, la dernière étant meilleure que la précédente.

L’optimisation inspirée de la quantique est semblable, mais les qubits sont simulés dans un logiciel plutôt que d’être matériels. Les mêmes principes s’appliquent : il faut créer un modèle mathématique du problème dans un logiciel qui imite les qubits, puis laisser le système évoluer en peaufinant ses paramètres jusqu’à l’obtention de la solution désirée.

Remarquez que l’expression clé est solution désirée ou, comme mentionné précédemment, meilleure solution disponible. Il n’est toujours pas garanti que les systèmes quantiques dits à petite échelle, inspirés de la quantique et de recuit quantique produisent la meilleure solution possible. Toutefois, dans les bonnes circonstances, ils peuvent donner de meilleurs résultats que les techniques classiques. Ils peuvent trouver une solution du même degré de qualité qu’un ordinateur classique en moins de temps que celui-ci, ou une meilleure solution en autant de temps. Ils pourraient également traiter des versions plus complexes du problème avec plus de variables, toujours en produisant une solution préférable ou plus réaliste que les méthodes classiques.

Le recuit quantique et les techniques d’optimisation inspirées de la quantique ont déjà résolu des problèmes réels avec une amélioration de 10 % à 15 %, et parfois plus, par rapport aux autres méthodes. Une entreprise de télécommunications a optimisé l’emplacement de tours de téléphonie cellulaire dans une région donnée. Plusieurs institutions financières ont optimisé des portefeuilles pour réduire au minimum la valeur à risque. Une entreprise de livraison de colis a optimisé les trajets de ses livreurs. Ces exemples ne sont que le début; bien d’autres cas d’utilisation suivront.

L’informatique quantique a le potentiel de tirer le meilleur parti de tout le secteur de l’optimisation. Encore mieux : on peut s’y mettre dès maintenant.