Toshiba Corporation ha realizzato un importante passo avanti nell'ottimizzazione combinatoria, la selezione delle migliori soluzioni tra un numero enorme di modelli combinatori, con lo sviluppo di un algoritmo che offre le prestazioni più veloci e su larga scala del mondo, e un miglioramento di circa 10 volte rispetto ai metodi attuali. Il nuovo metodo di Toshiba può essere applicato a compiti così scoraggianti ma essenziali come identificare percorsi di consegna efficienti, determinare le strutture molecolari più efficaci da indagare nello sviluppo di nuovi farmaci, e la creazione di portafogli di prodotti finanziari redditizi.

La tecnica di nuova concezione, l'algoritmo di biforcazione simulata, ottiene rapidamente soluzioni approssimate altamente accurate (buone soluzioni) per problemi complessi di ottimizzazione combinatoria su larga scala, problemi che hanno resistito alla soluzione per lungo tempo, e che sono molto difficili da risolvere utilizzando tecniche convenzionali. Potenzialmente ancora più importante, l'algoritmo realizza anche un'eccellente scalabilità a basso costo utilizzando i computer attuali, che potrebbe rivoluzionare gli attuali processi di ottimizzazione.

Toshiba utilizzerà l'algoritmo di biforcazione simulata per costruire una piattaforma di servizi in grado di risolvere rapidamente diversi problemi sociali e aziendali, puntando alla commercializzazione nel 2019.

I dettagli della nuova tecnologia sono pubblicati nella rivista accademica online Progressi scientifici .

Molti problemi possono essere risolti solo vagliando un vasto numero di opzioni per trovare le migliori combinazioni. Questi includono la realizzazione di una logistica efficiente (il problema del commesso viaggiatore in matematica), dirigere il traffico per ridurre la congestione, applicare il design molecolare allo sviluppo di farmaci, e l'ottimizzazione dei portafogli finanziari. Oggi, realizzare tale ottimizzazione combinatoria richiede un'enorme quantità di calcolo, e l'utilizzo dei computer attuali per trovare soluzioni rimane difficile.

Ci sono aspettative crescenti che i dispositivi di elaborazione di prossima generazione, come i computer quantistici, aprirà la strada a soluzioni migliori, e la ricerca attuale mira a sviluppare computer appositamente progettati per l'ottimizzazione combinatoria attraverso l'uso di circuiti superconduttori, laser, e computer digitali basati su semiconduttori. Nonostante questi sforzi, rimane una sfida aumentare la dimensione del problema risolvibile e ridurre il tempo di calcolo.

Per esempio, è ancora difficile per i computer quantistici con circuiti superconduttori risolvere problemi complessi su larga scala. E mentre i computer digitali odierni basati su semiconduttori hanno reso più facile aumentare la dimensione del problema risolvibile, gli attuali algoritmi per l'ottimizzazione combinatoria sono difficili da parallelizzare, rendendo difficile l'uso del calcolo parallelo per accelerare la risoluzione dei problemi.

Toshiba ha risolto questi problemi sviluppando un nuovo algoritmo di ottimizzazione combinatoria, l'algoritmo di biforcazione simulata. È altamente parallelizzabile, e può quindi accelerare facilmente la risoluzione dei problemi su un computer digitale standard attraverso il calcolo parallelo. Poiché gli attuali sistemi di calcolo su larga scala possono essere utilizzati così come sono, non è necessario installare nuove apparecchiature, rendendo facile scalare a basso costo.

Per esempio, utilizzando array di porte programmabili sul campo (FPGA), una buona soluzione a un problema di ottimizzazione con 2, È possibile ottenere 000 variabili completamente connesse (circa 2 milioni di connessioni) in soli 0,5 millisecondi. Questo è circa 10 volte più veloce del computer quantistico basato su laser riconosciuto come il più veloce al mondo in grado di risolvere lo stesso problema. Inoltre, utilizzando un cluster di otto GPU, Toshiba ha ottenuto una buona soluzione per un problema su larga scala che coinvolge 100, 000 variabili completamente connesse (circa 5 miliardi di connessioni) in pochi secondi. Questi risultati aprono nuovi modi per risolvere problemi di ottimizzazione combinatoria su larga scala in molte aree di applicazione differenti.

L'algoritmo di biforcazione simulata sfrutta i fenomeni di biforcazione, processi adiabatici, e processi ergodici nella meccanica classica per trovare rapidamente soluzioni altamente accurate. Toshiba ha derivato il principio da una teoria di un computer quantistico proposta dall'azienda stessa. Questa scoperta nella meccanica classica ispirata dalla meccanica quantistica è un interessante accademicamente, risultato altamente innovativo che suggerisce l'esistenza di teoremi matematici sconosciuti.

Andando avanti quest'anno, Toshiba ora mira a utilizzare questa svolta tecnologica chiave per realizzare e commercializzare una piattaforma di servizi che soddisfi tutte le esigenze di ottimizzazione nella logistica, finanza, e altri settori della società moderna.