Toshiba Corporation heeft een grote doorbraak gerealiseerd in combinatorische optimalisatie - de selectie van de beste oplossingen uit een enorm aantal combinatorische patronen - met de ontwikkeling van een algoritme dat 's werelds snelste en grootste prestatie levert, en een ongeveer 10-voudige verbetering ten opzichte van de huidige methoden. Toshiba's nieuwe methode kan worden toegepast op zulke ontmoedigende maar essentiële taken als het identificeren van efficiënte leveringsroutes, het bepalen van de meest effectieve moleculaire structuren om te onderzoeken bij de ontwikkeling van nieuwe geneesmiddelen, en het opbouwen van portefeuilles van winstgevende financiële producten.

De nieuw ontwikkelde techniek, het gesimuleerde bifurcatie-algoritme, verkrijgt snel zeer nauwkeurige benaderingsoplossingen (goede oplossingen) voor complexe grootschalige combinatorische optimalisatieproblemen - problemen die lange tijd geen oplossing hebben gevonden, en die met conventionele technieken zeer moeilijk op te lossen zijn. Mogelijk nog belangrijker, het algoritme realiseert ook uitstekende schaalbaarheid tegen lage kosten met behulp van huidige computers, die een revolutie teweeg kunnen brengen in de huidige optimalisatieprocessen.

Toshiba zal het gesimuleerde bifurcatie-algoritme gebruiken om een ​​serviceplatform te bouwen dat snel diverse sociale en zakelijke problemen kan oplossen, streven naar commercialisering in 2019.

Details van de nieuwe technologie worden gepubliceerd in het online academische tijdschrift wetenschappelijke vooruitgang .

Veel problemen kunnen alleen worden opgelost door een groot aantal opties te doorzoeken om de beste combinaties te vinden. Deze omvatten het realiseren van efficiënte logistiek (het handelsreizigersprobleem in wiskunde), het regelen van het verkeer om congestie te verminderen, het toepassen van moleculair ontwerp op de ontwikkeling van geneesmiddelen, en het optimaliseren van financiële portefeuilles. Vandaag, het realiseren van een dergelijke combinatorische optimalisatie vereist een enorme hoeveelheid rekenwerk, en het blijft moeilijk om de huidige computers te gebruiken om oplossingen te vinden.

Er zijn groeiende verwachtingen dat computerapparatuur van de volgende generatie, zoals kwantumcomputers, zal leiden tot betere oplossingen, en huidig ​​onderzoek heeft tot doel computers te ontwikkelen die speciaal zijn ontworpen voor combinatorische optimalisatie door het gebruik van supergeleidende circuits, lasers, en op halfgeleiders gebaseerde digitale computers. Ondanks deze inspanningen, het blijft een uitdaging om de omvang van het oplosbare probleem te vergroten en de rekentijd te verkorten.

Bijvoorbeeld, het is nog steeds moeilijk voor kwantumcomputers met supergeleidende circuits om complexe grootschalige problemen op te lossen. En hoewel de huidige op halfgeleiders gebaseerde digitale computers het gemakkelijker hebben gemaakt om de omvang van het oplosbare probleem te vergroten, huidige algoritmen voor combinatorische optimalisatie zijn moeilijk te parallelliseren, waardoor het moeilijk is om parallel computing te gebruiken om het oplossen van problemen te versnellen.

Toshiba heeft deze problemen opgelost door een nieuw combinatorisch optimalisatiealgoritme te ontwikkelen, het gesimuleerde bifurcatie-algoritme. Het is zeer parallelleerbaar, en kan daarom gemakkelijk het oplossen van problemen op een standaard digitale computer versnellen door middel van parallelle berekening. Aangezien de huidige grootschalige computersystemen kunnen worden gebruikt zoals ze zijn, het is niet nodig om nieuwe apparatuur te installeren, waardoor het gemakkelijk is om tegen lage kosten op te schalen.

Bijvoorbeeld, door gebruik te maken van veldprogrammeerbare poortarrays (FPGA's), een goede oplossing voor een optimalisatieprobleem met 2, 000 volledig verbonden variabelen (ongeveer 2 miljoen verbindingen) kunnen worden verkregen in slechts 0,5 milliseconde. Dit is ongeveer 10 keer sneller dan de op laser gebaseerde kwantumcomputer die wordt erkend als 's werelds snelste, hetzelfde probleem kan oplossen. In aanvulling, met behulp van een cluster van acht GPU's, Toshiba heeft een goede oplossing gevonden voor een grootschalig probleem met 100, 000 volledig verbonden variabelen (ongeveer 5 miljard verbindingen) in slechts enkele seconden. Deze resultaten openen nieuwe manieren om grootschalige combinatorische optimalisatieproblemen in veel verschillende toepassingsgebieden op te lossen.

Het gesimuleerde bifurcatie-algoritme maakt gebruik van bifurcatieverschijnselen, adiabatische processen, en ergodische processen in de klassieke mechanica om snel zeer nauwkeurige oplossingen te vinden. Toshiba ontleende het principe aan een door het bedrijf zelf voorgestelde theorie van een kwantumcomputer. Deze ontdekking in de klassieke mechanica geïnspireerd door de kwantummechanica is een academisch interessant, hoogst nieuw resultaat dat het bestaan ​​van onbekende wiskundige stellingen suggereert.

Dit jaar vooruit, Toshiba wil deze belangrijke technologische doorbraak nu gebruiken om een ​​serviceplatform te realiseren en te commercialiseren dat voldoet aan alle optimalisatiebehoeften in de logistiek, financiën, en andere gebieden van de moderne samenleving.