Ickelinjär blandad heltalsoptimering – Relaxationsmetoder, utmaningar och framsteg

Abstract:

Ickelinjär blandad heltalsoptimering är en mycket allmän klass av optimeringsproblem med ett brett spektrum av tillämpningar till exempel inom schemaläggning, processdesign, finans och maskininlärning. Heltalsvariabler gör det möjligt att modellera diskreta beslut som till exempel ja/nej-beslut, ordningsföljder, antal maskiner och val mellan olika alternativ.

Beräkningsmässigt är ickelinjär blandad heltalsoptimering mycket utmanande, dels på grund av dess kombinatoriska natur men de ickelinjära komponenterna medför också numeriska svårigheter. Inom ickelinjär blandad heltalsoptimering finns undergrupper av optimeringsproblem där en klassisk indelning är konvexa och icke-konvexa problem. Under presentationen kommer vi att se att konvexitet är en viktig egenskap för att kunna lösa ickelinjära blandade heltalsproblem och beräkna optimala lösningar.

Typiskt sett är det inte möjligt att direkt beräkna en optimal lösning för ett ickelinjärt blandat heltalsproblem, utan de flesta metoder bygger på att iterativt lösa en sekvens av enklare problem. Dessa enklare problem är så kallade relaxationer av det ursprungliga problemet. Målet är att skapa och lösa relaxationer av det ursprungliga problemet på ett sådant sätt att den optimala lösningen hittas och att man kan bevisa att ingen bättre lösning kan existera. Hur man bäst kan skapa dessa relaxationer är en central fråga inom ickelinjär blandad heltalsoptimering och under presentationen kommer vi gå igenom några metoder för att skapa relaxationer. Idealt vill man att relaxationerna ska vara så starka som möjligt, det vill säga att de beskriver det ursprungliga problemet så väl som möjligt, men också vara beräkningsmässigt enkla att lösa. Dessa två egenskaper står ofta i konflikt med varandra, där starkare relaxationer leder till beräkningsmässigt svårare problem. Under presentationen kommer vi att gå igenom så kallade plansnittsmetoder för att skapa relaxationer och behandla centrala egenskaper kring dessa.