Toshiba Corporation a réalisé une percée majeure dans l'optimisation combinatoire - la sélection des meilleures solutions parmi un nombre énorme de modèles combinatoires - avec le développement d'un algorithme qui offre les performances les plus rapides et à plus grande échelle au monde, et une amélioration d'environ 10 fois par rapport aux méthodes actuelles. La nouvelle méthode de Toshiba peut être appliquée à des tâches aussi intimidantes mais essentielles telles que l'identification d'itinéraires de livraison efficaces, déterminer les structures moléculaires les plus efficaces à étudier dans le développement de nouveaux médicaments, et la constitution de portefeuilles de produits financiers rentables.

La technique nouvellement développée, l'algorithme de bifurcation simulée, obtient rapidement des solutions approximatives très précises (bonnes solutions) pour des problèmes complexes d'optimisation combinatoire à grande échelle - des problèmes qui ont résisté à la solution pendant longtemps, et qui sont très difficiles à résoudre en utilisant les techniques conventionnelles. Potentiellement encore plus important, l'algorithme réalise également une excellente évolutivité à faible coût en utilisant les ordinateurs actuels, qui pourrait révolutionner les processus d'optimisation actuels.

Toshiba utilisera l'algorithme de bifurcation simulée pour créer une plate-forme de services capable de résoudre rapidement divers problèmes sociaux et commerciaux, en vue d'une commercialisation en 2019.

Les détails de la nouvelle technologie sont publiés dans la revue académique en ligne Avancées scientifiques .

De nombreux problèmes ne peuvent être résolus qu'en passant au crible un grand nombre d'options pour trouver les meilleures combinaisons. Il s'agit notamment de réaliser une logistique efficace (le problème du voyageur de commerce en mathématiques), orienter le trafic pour désengorger, appliquer la conception moléculaire au développement de médicaments, et l'optimisation des portefeuilles financiers. Aujourd'hui, réaliser une telle optimisation combinatoire nécessite une énorme quantité de calculs, et utiliser les ordinateurs actuels pour trouver des solutions reste difficile.

On s'attend de plus en plus à ce que les appareils informatiques de nouvelle génération, comme les ordinateurs quantiques, ouvrira la voie à de meilleures solutions, et les recherches actuelles visent à développer des ordinateurs spécialement conçus pour l'optimisation combinatoire par l'utilisation de circuits supraconducteurs, laser, et des ordinateurs numériques à semi-conducteurs. Malgré ces efforts, il reste un défi d'augmenter la taille du problème soluble et de réduire le temps de calcul.

Par exemple, il est encore difficile pour les ordinateurs quantiques dotés de circuits supraconducteurs de résoudre des problèmes complexes à grande échelle. Et tandis que les ordinateurs numériques à base de semi-conducteurs d'aujourd'hui ont facilité l'augmentation de la taille des problèmes résolvables, les algorithmes actuels d'optimisation combinatoire sont difficiles à paralléliser, rendant difficile l'utilisation de l'informatique parallèle pour accélérer la résolution de problèmes.

Toshiba a résolu ces problèmes en développant un nouvel algorithme d'optimisation combinatoire, l'algorithme de bifurcation simulée. Il est hautement parallélisable, et peut donc facilement accélérer la résolution de problèmes sur un ordinateur numérique standard grâce à un calcul parallèle. Comme les systèmes informatiques actuels à grande échelle peuvent être utilisés tels quels, il n'est pas nécessaire d'installer de nouveaux équipements, ce qui facilite la mise à l'échelle à faible coût.

Par exemple, en utilisant des réseaux de portes programmables sur le terrain (FPGA), une bonne solution à un problème d'optimisation avec 2, 000 variables entièrement connectées (environ 2 millions de connexions) peuvent être obtenues en seulement 0,5 milliseconde. C'est environ 10 fois plus rapide que l'ordinateur quantique à laser reconnu comme le plus rapide au monde peut résoudre le même problème. En outre, en utilisant un cluster de huit GPU, Toshiba a obtenu une bonne solution pour un problème à grande échelle impliquant 100, 000 variables entièrement connectées (environ 5 milliards de connexions) en quelques secondes seulement. Ces résultats ouvrent de nouvelles voies pour résoudre des problèmes d'optimisation combinatoire à grande échelle dans de nombreux domaines d'application différents.

L'algorithme de bifurcation simulée exploite les phénomènes de bifurcation, processus adiabatiques, et les processus ergodiques en mécanique classique pour trouver rapidement des solutions très précises. Toshiba a dérivé le principe d'une théorie d'un ordinateur quantique proposée par l'entreprise elle-même. Cette découverte de la mécanique classique inspirée de la mécanique quantique est une découverte académiquement intéressante, résultat très nouveau qui suggère l'existence de théorèmes mathématiques inconnus.

Avancer cette année, Toshiba ambitionne désormais d'utiliser cette avancée technologique clé pour réaliser et commercialiser une plateforme de services qui répond à tous les besoins d'optimisation en logistique, la finance, et d'autres domaines de la société moderne.