3.12.2018
Jan Kronqvist, Anders Lundell och Tapio Westerlund är upphovspersonerna till SHOT, som är det snabbaste optimeringsprogrammet i världen. Programmet öppnar för möjligheter att lösa hittills olösliga problem inom utvecklingen av artificiell intelligens.
Optimering är en specialisering inom matematik och teknik där man systematiskt söker den bästa möjliga, eller en tillräckligt bra lösning på ett problem som egentligen är en matematisk beskrivning av något system eller en process.
– I dag finns flera optimeringsmetoder som ger endast en möjlig lösning utan att man har någon aning om hur bra lösningen är jämfört med den absolut bästa. I en del fall är det här tillräckligt, säger Jan Kronqvist, universitetslärare i anläggnings- och systemteknik vid Åbo Akademi.
Vad som är en tillräckligt bra lösning definieras av tillämpningen eller användaren, men kan vara svårt att veta i förväg.
– Men med de metoder vi utvecklat kan man stänga in den lösning man får mellan en övre och undre gräns. På så sätt fås ett mått på lösningens kvalitet, och man kan garanterat säga att man hittat bästa möjliga lösning då den övre och undre gränsen möts, säger docent Andreas Lundell.
Optimeringsproblemen kan relatera till i stort sett vad som helst, till exempel den bästa produktionsplanen för en vara i en fabrik (med en effektivare eller optimerad process kan man få ner svinn och energikostnader, öka lönsamhet och minska skadliga effekter på miljön), den effektivaste strålbehandlingen (hur optimera behandlingen för största möjliga effekt med minsta möjliga risk, hur spara tid, och så vidare), eller den kortaste vägen mellan två städer (stadexemplet relaterar till ett klassiskt optimeringsproblem – mer om det nedan).
Handelsresandeproblemet
En förutsättning för att kunna göra en optimeringsberäkning är att man kan beskriva problemet matematiskt för att sedan kunna göra en analys.
”Handelsresandeproblemet” är ett exempel som ofta används i undervisningssyfte, men även har många praktiska tillämpningar. Problemet går ut på att en handelsresande ska besöka ett visst antal städer – uppgiften är att hitta den kortaste rutten via alla dessa städer så att den resande i slutet är tillbaka där den startade.
Märk att det bara gäller den kortaste vägen, det vill säga endast sträckan beaktas. Men man kan också beakta vägarnas framkomlighet beroende på årstid, tid på dygnet, trafik, vilket det optimala fordonet är, etcetera.
En rimlig fråga: Varför inte bara testa alla rutter för att få fram den kortaste sträckan?
Svar: Om problemet är enkelt (litet) är det ett rimligt tillvägagångsätt. Säg att det bara gäller att finna det snabbaste sättet att ta sig genom fyra städer för att till slut anlända där man startade, då finns det tre olika rutter att välja på. Finns det fem städer som ska besökas ökar ruttalternativen till tolv. Men ökar man till tio städer finns det 181 440 möjliga rutter. Femton städer ger 43 589 145 600 möjliga rutter och tjugo städer ger 60 822 550 204 416 000 möjliga rutter. När antalet variabler ökar börjar även superdatorer få problem: att lösa optimeringsproblem på det här sättet, alltså med ren datorkraft eller beräkningskraft (”brute force”), fungerar bara givet att man lyckas beskriva problemet tillräckligt enkelt – vilket i verkligheten ofta betyder en avsevärd förenkling av beskrivningen av problemet.
– Matematiskt går optimeringsproblemen ut på att antingen finna ett minimum eller ett maximum av en funktion, det kallas ”objektfunktion”, givet vissa begränsningar, som kallas ”bivillkor”, säger Jan Kronqvist.
– En objektfunktion skulle till exempel vara: få ut största möjliga vinst med bivillkoret som beskriver begränsade resurser, till exempel råvarukostnader eller dylikt.
MILP och MINLP
Heltalsvariabler har den egenskapen att deras värden alltid ges i heltal; ett specialfall av detta är binära variabler som antar ett entydigt ”ja” eller ”nej” (eller annorlunda uttryckt: i ”1” eller ”0”). Till exempel: Hur många bilar lönar det sig att tillverka, eller hur många produktionslinjer lönar det sig att ha igång? Svaret ges i heltal – det är inte rimligt att tillverka en fjärdedels bil, eller konstruera en halv produktionslinje. Den enklaste klassen av heltalsoptimeringsproblem som innehåller heltalsvariabler sorterar under beteckningen MILP (Mixed-Integer Linear Programming) och kan idag lösas effektivt med datorprogram.
– MILP kan också ge svar på ordningsföljdsfrågor – i vilken ordning lönar det sig att utföra processer i tillverkningen av en produkt och mycket mer, säger Andreas Lundell.
Men MILP-problem har den begränsningen att alla funktioner, det vill säga objektfunktionen och bivillkoren, måste vara linjära. Det enklaste handelsresandeproblemet är ett typiskt exempel på ett problem av MILP-typ, men så fort man lägger till begränsningar som till exempel bränsleeffektivitet blir problemet mycket svårare att lösa.
– Faktum är att nästan alla verkliga problem inom till exempel industrin är ickelinjära – det vill säga problemet låter sig inte beskrivas linjärt. Ett enkelt exempel: Kostnaden per enhet är inte densamma oberoende av mängden enheter som tillverkas, och inte minskar den till exempel heller linjärt så att priset per enhet sjunker med en viss procent per extra enhet man tillverkar.
Dessa betydligt mer komplexa problem faller under beteckningen ickelinjär heltalsoptimering, MINLP (Mixed-Integer NonLinear Programming). Exemplen är otaliga men berör bland annat problem som optimering av cancerbehandling, optimal drift av kärnreaktorer, design av värmeväxlarnätverk, produktionsoptimering, portföljoptimering, samt diverse problem som berör maskininlärning och artificiell intelligens. Det gemensamma för dessa är att de är mycket svåra optimeringsproblem.
Konvexa problem
Ämnena anläggnings- och systemteknik, samt matematik och statistik vid Åbo Akademi har under de senaste åren speciellt fokuserat på metodutveckling för en typ av ickelinjära heltalsproblem som kallas konvexa MINLP.
Konvexa problem innebär att de ickelinjära funktionerna har vissa egenskaper, särskilt gäller att om man drar en linje mellan två punkter på funktionens graf så ligger hela linjen ovanför grafen. I praktiken betyder det att problemen är enklare, men tyvärr det är väldigt svårt att på förhand avgöra om ett problem är konvext eller inte, och exakt vad som gör ett problem konvext menar Kronqvist och Lundell skulle kräva ett par timmars föreläsning i matematik.
Många problem går dock att skriva om i en konvex form.
– Våra nya algoritmer utnyttjar de egenskaper som konvexa problem har. Dessutom kombinerar vi och drar nytta av framsteg som gjorts inom andra optimeringsområden, till exempel inom MILP. Om vi kan lösa konvexa MINLP-problem effektivt kan vi också lösa ickekonvexa problem. Och det igen öppnar upp helt nya möjligheter att lösa optimeringsproblem inom industrin och hitta sätt att angripa problem inom artificiell intelligens som hittills varit omöjliga.
SHOT
Ett viktigt steg i detta är utvecklingen av programmet SHOT (The Supporting Hyperplane Optimization Toolkit) som utvecklats av Lundell, Kronqvist och professor emeritus Tapio Westerlund. Programmet, som lanserades offentligt i juni i år, hittar den garanterat bästa lösningen till konvexa MINLP-problem. Källkoden är öppen och programmet är baserat på en metod som kallas ESH-algoritmen, där ESH står för Extended Supporting Hyperplane.
Omfattande tester har visat att SHOT tillhör världseliten av de tillgängliga optimeringsprogrammen för den här typen av problem – detta i tävling med både kommersiella programleverantörer och program utvecklade vid framstående universitet som Carnegie Mellon University, MIT, Princeton, med flera.
– Även om SHOT idag främst är avsedd för konvexa MINLP-problem, har vi redan en klar plan för hur detta ska utökas till även mer generella optimeringsproblem, och vi har överlag mycket intressant på kommande, säger Lundell.
– Vi kommer dessutom att se på en del speciella appliceringsområden inom till exempel artificiell intelligens och systemidentifiering, inflikar Kronqvist.
Eftersom optimeringsproblem finns överallt i samhället, är de möjliga tillämpningsområdena för MINLP även otaliga. Speciellt i och med att metoderna utvecklas och gör att man kan övergå från förenklade MILP-modeller till mera avancerade MINLP-modeller som bättre motsvarar verkliga system. Då kan effektiviteten hos de metoder som utvecklats vid Åbo Akademi, och speciellt SHOT ha en nyckelposition.
Utvecklingen i heltalsoptimering mellan 1988 och 2017
• Förbättring i algoritmer och metoder: 147 650 gånger snabbare.
• Förbättring i datorkraft: 17 120 gånger snabbare.
• Total förbättring 2 527 768 000 gånger snabbare.
I praktiken betyder det att ett typiskt MILP-problem som skulle tagit 80 år att lösa 1988, tar en sekund att lösa idag. Men medan lösning av MILP-problem idag är en standardteknik, så är det fortsättningsvis en utmaning att lösa MINLP-problem. Det här motiverar och inspirerar forskningen inom området.
Bakgrund
Vid Åbo Akademi började forskningen inom MINLP-optimering under 1990-talet under ledning av professor Tapio Westerlund. Totalt 16 doktorander har disputerat inom området varav Kronqvist är den senaste.
Gruppen har ett bra internationellt rykte och ett starkt nätverk och har ett nära samarbete med världsledande forskare inom området. Som:
Ignacio Grossman vid Carniegie Mellon University (h-index 114, hedersdoktor vid ÅA)
Nick Sahinidis vid Carniegie Mellon University
Leo Liberti vid École Polytechnique
En annan person som gruppen under flera år hade ett nära samarbete med var Christodoulus Floudas verksam vid Princeton University och Texas A&M University (h-index 96, hedersdoktor vid Åbo Akademi). Tyvärr gick professor Floudas hastigt bort för något år sedan, men det nära samarbetet fortsätter med en av hans tidigare studenter, Ruth Misener som numera är verksam vid Imperial College London.