Aktuella examensarbeten

Nedan finner du en lista över möjliga områden inom vilka examensarbeten kan definieras. De anknyter samtliga till aktuell forskning och kan anpassas till att innehålla en större del av teoretiskt arbete inom modell- och algoritmutveckling eller en större del av numeriskt orienterad algoritmutveckling och utvärdering.

Mallar för rapporten, som skall skrivas i LaTeX, finns här: mall for LaTeX; fontfil; styrfil 1; styrfil 2; logo 1;. logo 2.

Optimization methods for a maintenance problem at Volvo Aero [inlagt 071128]

The optimization group at applied mathematics, Mathematical Sciences, Chalmers university of technology and Mathematical Sciences, Göteborg University, have recently been given a research grant from The Swedish Research Council to perform research within the following project: ``Development of generic mathematical optimization models and algorithms for the solution of opportunistic and preventive maintenance planning problems in industry''.

This research project follows previous projects with grants from Vinnova (previously also from Nationella Flygforskningsprogrammet, NFFP) and performed in collaboration with researchers at Volvo Aero (VAC) in Trollhättan. Together we have generated important knowledge about maintenance processes regarding aircraft engines, in particular the jet engine RM12. We have especially constructed mathematical models that describe the problem to find an optimal maintenance plan for a whole engine during a contract period, taking into account the existence of used parts with shorter lives at warehouses, work costs, and possible side constraints on the engine condition at the end of the contract period.

In a master thesis project, ideally for two collaborating students, we wish to investigate a number of possible solution methodologies for the maintenance problem. It is a very large scale linear mixed integer optimization problem, for which several possible lines of attack are potentially interesting. In a collaboration with us you will implement and evaluate them on realistic data provided by VAC.

The masters project is particularly aimed at students in Applied physics (F) at Chalmers, the mathematics program at GU, and a number of international masters programs (e.g., Engineering mathematics, Applied physics, and Foundations of computing), who have taken a sufficiently large number of mathematics and optimization courses with good results. It is especially important that the basic course in Optimization (TMA947) has been taken with good results. Knowledge of optimization modeling tools such as AMPL is a plus.

Sökmotor för billigaste taxiflygalternativen [inlagt 060830]

Sedan starten 2001 har Avinode snabbt etablerat sig som en betydande mjukvaruleverantör för företag verksamma inom taxiflygbranschen. Över 600 företag världen över är anslutna till Avinodes webbaserade marknadsplats. Företaget har idag 12 anställda, varav fem jobbar med teknikutveckling. Vi håller till i moderna lokaler i centrala Göteborg. Mer information finner du på vår webbsida www.avinode.com.

Teknikavdelningen jobbar dels med att vidareutveckla och underhålla företagets marknadsplats, dels med att utöka produktutbudet. Arbetet bedrivs i ett prestigelöst och entusiastiskt team och arbetsuppgifterna är varierande. Avinodes produkter är webbapplikationer byggda på J2EE-plattformen, med MySQL, EJB, Struts, JSP. Vi jobbar enligt Extreme Programming med korta iterationer, automatiserade tester och i nära sammarbete med våra säljare. Mycket av arbetet sker i par eller grupp och arbetet ställer stora krav på ödmjukhet, kommunikationsförmåga, noggrannhet, och förståelse för vad det innebär att långsiktigt utveckla och driva komplicerade webbapplikationer. Utvecklingsarbetet bedrivs med open source-verktyg såsom Ant, JUnit, Struts, Eclipse etc.

En av Avinodes viktigaste tjänster är att ta fram en lista över de billigaste flygplanen för en kunddefinierad rutt. I Avinodes databas finns ett stort antal flygplan som vart och ett har ett schema som beskriver när och var flygplanet är ledigt, och prissättningsparametrar som beskriver hur flygplanet prissätts. Dessutom finns regler för hur varje flygplan får operera. Sökmotorns uppgift är att utifrån kundens villkor och utifrån flygplansdatabasen hitta de billigaste flygplansalternativen som kan utföra flygningen. Dagens sökmotor är skriven i Java och gör en uttömmande sökning bland alla alternativ. Ett ökande antal flygplan i databasen gör att sökningar på rutter med fler än fem flygningar börjar ta alltför lång tid.

Nuvarande prestandaproblem tillsammans med nya funktionella krav, gör att det är dags att utveckla nästa generations sökmotor. Bland nya potentiella krav finns behov av att titta på lösningar som bygger på kombinationer av flygplan, dvs olika flygplansindivider ansvarar för olika delar av en kunds efterfrågade rutt. Krav av den här typen gör att antalet potentiella lösningar ganska snabbt skjuter i höjden. Exjobbet går ut på att att tillsammans med Avinode ta fram en fungerande prototyp för nästa generations sökmotor. Exjobbet innefattar följande moment:

- Förstå problemet och sammanställa de krav som finns på sökmotorn.

- Analysera problemet teoretiskt och ta fram lösningsförslag.

- Utifrån lösningsfarslag utveckla en fungerande prototyp som efter vidareutveckling skall kunna ersätta Avinodes nuvarande sökmotor.

Om du är intresserad av ett exjobb med praktisk förankring och vars slutresultat kommer användas industriellt - då kan det här vara något för dig. Sökande skall ha kunskaper inom optimering och programmering. Detta kan vara ett lämpligt exjobb för studenter med optimeringsinrikting på Teknisk Matematik på Chalmers. Kontakta work@avinode.com för mer information och intresseanmälan.

Resursallokering - en numerisk studie [Ett exjobb tillsatt 1101!]

I ett stort antal optimeringsmodeller inom teknik och ekonomi förekommer ett delproblem som innebär att man skall finna en optimal fördelning av utnyttjande av en given mängd resurser till olika aktiviteter. Optimeringsproblemet kan beskrivas av en differentierbar, konvex funktion som består av en summa av envariabelfunktioner och vars minimum söks på en mängd som ges av ett enda (o)linjärt bivillkor och gränser på variablernas värden.

På grund av problemets enkla form kan man utveckla extremt effektiva algoritmer. De kan väsentligen delas in i två kategorier. I den första betraktar man problemet utan att ta hänsyn till variabelgränserna. Efter att ha löst detta enkla problem kan man visa att vissa variabler som bryter mot gränserna optimalt kan sättas till en av gränserna. Man stryker sedan dessa variabler, justerar resursvillkoret och löser om tills alla variabler har fixerats. (Detta kan sägas vara en primal metod.) I den andra metodiken Lagrangrelaxeras i stället resursbivillkoret och optimeras med hjälp av Lagrangedualitet. Eftersom det endast förekommer en dualvariabel har man att lösa ett (implicit givet) envariabelproblem, som också det kan angripas med en enkel metodik.

Eftersom problemet är så viktigt och förekommer i så många sammanhang har det också föreslagits en stor mängd algoritmer för problemeto och genomförts flera numeriska studier. Det är till och med så att samma algoritm har återupptäckts i flera olika forskarmiljöer genom åren. Dock har ännu ingen genomfört en ambitiös numerisk studie som jämför de olika algoritmerna med varandra. Detta är ämnet för detta examensarbete, som bör genomföras av två studenter gemensamt. Den eller de som vill komma ifråga skall vara skicklig på att programmera för numeriska beräkningar och vara självständiga. Målet är att skriva en forskningsrapport som leder till en publicering.

En utgångspunkt är denna rapport.

Optimering av resursutnyttjande i multi-task [Ett exjobb avslutat!]

Volvo Aero Corporation (VAC), Trollhättan, har anskaffat fem stycken "multi-task"-maskiner tillsammans med ett automatiskt lastbärarsystem. Utrustningen är avancerad och kan utföra en mängd operationer i sekvens. Det är viktigt att dessa dyrbara maskiner nyttjas så effektivt som möjligt, dvs med så högt kapacitetsutnyttjande som möjligt. Detta får dock ej ske på bekostnad av leveransservice och ledtid på producerade produkter. Kopplade till maskinerna finns resurser som gradning och utrustning för verktygsbyten. I dagsläget är det svårt att bedöma var begränsningen i systemet kommer att bli då konceptet är nytt för VAC, men det torde vara av vikt att utflödet ur maskingruppen blir så jämnt som möjligt för att undvika köer i kopplade resurser och efterföljande operationer etc.

Multi-task-maskinerna ger stora valmöjligheter med avseende på hur långa operationssekvenser som kan, och bör, köras. Långa operationssekvenser är skenbart tilltalande då dessa anses medföra en hög produktiv ledtidsandel. Dock glöms lätt att enbart långa operationssekvenser riskerar ge låg flexibilitet, dvs operationerna bli svåra att "pussla ihop". En konsekvens av detta kan bli att efterföljande, beroende, resurser beläggs ojämnt med reducerad slutlig leveransservice som följd. Korta operationssekvenser däremot, ger större möjligheter att förse dessa resurser med en jämn beläggning. Detta dock på bekostnad av beläggningen av multi-task-maskinerna, eftersom större andel av tiden måste nyttjas till att ställa maskinerna.

En optimal mix av korta och långa operationstider är därför eftersträvansvärd. Det torde då finnas goda möjligheter att nyttja den varierande längden på operationssekvenserna för att styra, och utjämna, beläggningen i gradroboten.

Syftet med examensprojektet är att ta fram metodik för att uppskatta den optimala mixen mellan operationssekvenslängder för att balansera slutlig leveransservice (beläggning i efterföljande operationer) med beläggningen i multi-taskmaskinerna. Därtill skall exjobbet studera operationslängdsmixens betydelse för beläggningen i efterföljande operationer och hur denna påverkar den totala leveransservicen.

Examensrapporten finns här.

Optimering inom personalplanering hos Carmen Systems AB [Ett exjobb avslutat!]

Carmen Systems AB är ett framgångsrikt företag, skapat i Göteborg. De arbetar med ett stort antal företag med vilka de samarbetar för att framför allt optimera scheman för personal och fordon, t.ex. inom flyg- och tågtransportbranschen. De optimeringsproblem som måste lösas för att till exempel skapa bra scheman för personal inom ett stort flygbolag är storskaligt (på grund av det stora nätverket och den stora personalstyrkan), komplext (bland på grund av alla regler som omgärdar planeringen av personalens arbetstid) och måste ofta lösas på kort tid (eftersom man vill skapa planen så sent som möjligt så att den är baserad på så korrekt information som möjligt); alla dessa faktorer bidrar till att personalplaneringsproblem är stora utmaningar för en optimeringsalgoritm.

Carmen Systems AB arbetar med en kombination av optimering och "constraint programming" med vilken man kan skapa ett stort antal tillåtna delscheman som sedan kombineras på bästa sätt. Samlingen av tillåtna scheman skapas i en metod som benämns "kolumngenerering", och som innehåller element från "constraint programming" såväl som klassiska teman inom optimering, som till exempel Lagrangerelaxation, subgradientoptimering och dekompositionsmetoder av typen Dantzig-Wolfe. Inom detta examensarbete är syftet att undersöka användandet av stabiliserad kolumngenerering, där det klassiska "master-problemet" begränsas med hjälp av sidovillkor, vars syfte är att föra lösningarna närmare heltalsoptimum (som är det slutliga målet med att använda kolumngenerering och lösandet av master-problem).

Arbetet sker i nära samarbete med experter på Carmen Systems AB, och mestadels på företagets kontor. Examensarbetet innebär en hel del kodning, varför datorvana och särskilt med C- och C++-programmering är ett krav. Arbetet kan starta i början av november.

En teoretisk rapport som bildar grundvalen till det nya schemat återfinns här.

Examensrapporten finns här.

Optimering inom intensitetsmodulerad radioterapi hos Sahlgrenska [Två exjobb avslutade!]

Radiofysik vid Sahlgrenska Universitetssjukhus arbetar med avancerad utrustning vid behandling av vissa typer av cancer, särskild i huvud- och halsområdet. Personalen anger mål för stråldoser inom områden där cancern finns och maximala doser för intilliggande, känsliga organ. En invers optimering utförs sedan automatiskt för att beräkna vilka vinklar varifrån stråldoser skall skickas in i patienten och dessutom med vilka intensiteter. Problemet som därvid löses är typiskt icke-konvext, eftersom man för vissa organ beskriver mål för genomsnittliga doser, vilket ger icke-konvexa bivillkor för stråldoserna. Algoritmerna kan dock alltid förbättras, t.ex. så att också vinklarna bestäms automatiskt; för närvarande används en närmast manuell procedur. Det aktuella problemet är att samtidigt optimera vinklarna och stråldoserna, vilket beskriver ett icke-konvext optimeringsproblem med blandade heltals- och kontinuerliga variabler.

Arbetet sker i nära samarbete med experter på Radiofysik, SU.

Examensrapporten finns här.

Optimering av motorparametrar för Volvo [Två exjobb avslutade!]

Målet med detta examensarbete, som utförs i nära samarbete med och delvis vid Volvo, VCC, är att skapa ett effektivt verktyg för att optimera flera motorparametrar genom att utnyttja simuleringsverktyget WAVE. Ett delmål är att utreda hur många parametrar man praktiskt kan optimera för det motorproblem som studeras. Ett inomvetenskapligt mål är också att utreda om derivatainformation från en PDE kan extraheras (dvs. hur lösningen varierar med små förändringar i indata) och hur tillförlitlig den i så fall är; ett praktiskt mål med detta är att se om informationen rentav är värdefull eller ej för optimeringen.

WAVE löser strömningsekvationerna i tiden och i en rumsdimension. (In- och utdata till WAVE är helt och hållet baserat på ascii-filer.) Beräkningstiden är typiskt 2 till 4 minuter för sugmotorer och 10 till 15 minuter för överladdade motorer. I ett typiskt fall är man intresserad av 6 till 12 olika parametrars inverkan på ett urval av motoregenskaper. Exempel på egenskaper är levererade moment som funktion av varvtal, maxeffekt och bränsleekonomi sammanvägda från ett antal driftspunkter. Det finns egentligen ingen övre gräns för antalet relevanta parametrar; de kan enkelt utökas till både 30 och flera hundra.

Speciell hänsyn måste tas till att vissa parametrar är hårdvaruparametrar, t.ex. geometriska dimensioner som inte kan ändras vid olika driftsfall, medan andra är mjukvaruparametrar som kan ha olika optimala lägen beroende på t.ex. varvtal. Om man skall optimera egenskapen moment över hela varvtalsområdet, så kan mjukvaruparametrarna vara funktioner av varvtal. För de geometriska parametrarna däremot måste en kompromiss finnas, beroende på hur målfunktionen väljs, så att momentet är så bra som möjligt för alla varvtal.

För att på bästa sätt kunna kombinera optimeringsmetod och WAVE är MATLAB en lämplig plattform. Matematik har också tillgång till en programvara, TOMLAB, som används tillsammans med MATLAB och som innehåller en mängd olika optimeringsrutiner som kan vara en utgångspunkt för en undersökning. Bland lösarna återfinns sådana som löser problem till global optimalitet (Direct, Ego, Glcsolve) och sådana som bara garanterar att finna stationära punkter (Filter-SQP, Npsol, Qpopt). Tillgången till fler än en lösare som kan anropas med samma indatafiler gör det möjligt att snabbare utvärdera kvaliteten hos lösningen från en lösare och gör det också möjligt att finna bättre lokala optimallösningar än om man använder bara en lösare som startas i flera punkter.

Några av algoritmerna ovan utnyttjar derivator, andra inte. Eftersom derivator inte finns tillgängliga omedelbart från WAVE behöver arbetet innehålla en del där numeriska derivator skapas med hjälp av WAVE:s utdata.

Examensrapporten finns här.

Duala algoritmer för olinjära nätverksflöden [Ett exjobb avslutat!]

Storskaliga olinjära optimeringsproblem med nätverksstruktur löses rutinmässigt, till exempel vid bildbehandling inom medicin, vid socio-ekonomiska studier av t.ex. rörelser av kapital ("Världsbanksmodellen"), befolkning eller fordon i en region av Sverige, eller för att estimera flöden i vatten-, elektriska, dator- eller trafiknätverk. De problem som studeras blir alltmer komplexa och storskaliga med tiden och algoritmer som ofta används för att lösa dem ("row-action"- eller "relaxations"-algoritmer) börjar nå gränsen för att kunna ge ett "svar" inom rimlig tid.

"Svaret" är flöden i ett nätverk, vilket är den primala optimala lösningen av optimeringsproblemet. Algoritmerna nämnda ovan är duala (koordinat-riktnings- eller gradient-metoder) för en obegränsad Lagrange-dual formulering av problemet; Lagrangemultiplikatorerna som bestäms är ett slags priser. För att lösa det ursprungliga problemet måste priserna "översättas" till primala flöden, via det s.k. Lagrangeduala subproblemet. Vad som börjar bli mer och mer allvarligt är att den ökande storleken på problemen gör att det blir allt svårare att nå (mer eller mindre) exakta duala optimala priser; om "översättningen" utförs från en icke-optimal dual punkt blir med nödvändighet det åstadkomna flödet otillåtet i det primala problemet, vilket naturligtvis försvårar analysen och användandet av resultatet.

Ett sätt att angripa detta problem, vilket hittills inte används, är att utifrån den otillåtna primala lösningen leta sig, med en lokal, kontinuerlig sökning, mot tillåtna nätverksflöden. Detta kan göras med diverse tekniker, som t.ex. kan inbegripa grafsökningar. Om den lokala sökningen är välställd kommer den tillåtna lösningen som åstadkoms på detta sätt att vara näroptimal i ursprungsproblemet när den åstadkoms från näroptimala duala priser. Tanken är att använda denna "tillåtenhetsheuristik" vid upprepade tillfällen för att generera tillåtna flöden när vi tror oss befinna oss nära ett dualt optimum; eftersom vi har tillgång till både ett Lagrangedualt och ett primalt målfunktionsvärde kan vi också konstruera avbrottskriterier för den duala algoritmen baserade på relativa målfunktionsfel. En nyckel är givetvis att tillåtenhetsheuristiken är billig komplexitetsmässigt, eftersom den ska användas upprepade gånger.

I ett tidigare examensarbete utfört vid Linköpings universitet undersöktes några dylika ansatser för lokalsökning. Målet med detta examensarbete är att välja ut de bästa av dessa och inkorporera förbättringar av dem för att skapa ett programverktyg som kan tillfogas de duala algoritmer som används idag. Arbetet innebär alltså implementering, men i lika hög grad innebär det en systematisk utvärdering av olika lokalsökningsmetoder för storskaliga nätverksproblem. Målet är också att experimenten skall bilda en hörnsten i en publicering av arbetet i en högkvalitativ vetenskaplig tidskrift.

Examensrapporten finns här.

Implementering av en bundle-algoritm för konvex optimering [Avslutat!]

Inom grundutbildningen (högre kurser såväl som examensarbeten) förekommer projekt där konvexa, icke-differentierbara funktioner skall minimeras. I de flesta fall kommer, på grund av studenternas tidsbrist, algoritmerna som löser dessa problem att vara rudimentära och mindre effektiva. För att göra projekten mer lyckosamma och för att kunna överföra en större del av arbetet på andra delar av projekten syftar detta examensarbete till att skapa en effektiv kod för en stor klass av konvexa problem, där algoritmen är en bundle-metod. Eftersom alla sorters plattformar och datormiljöer används skall koden kunna överföras på ett enkelt sätt mellan samtliga vanliga plattformar. Algoritmen som skapas kan på sikt också användas inom de mer grundläggande kurserna som en "svart låda", och alltså användas av många.

Detta är ett examensarbete som lämpar sig särskilt för den som är intresserad av kodning för numerisk effektivitet och med ett allmänt intresse för storskalig optimering.

Examensrapporten finns här.

Två-nivå-optimering inom mekanik, ekonomi och regional planering

Vissa optimeringsproblem kan beskrivas som ett spel mellan två eller flera aktörer, var och en optimerande sin egen målfunktion. I en del av dessa fall kan en av spelarna sägas ha en ledande roll, eftersom han eller hon har fullständig kunskap om hur de andra agerar. I ett sådant (Stackelberg) spel väljer ledaren sin strategi givet denna kunskap om hur alla andra agerar, och detta spel kan därför sägas vara ett hierarkiskt (eller två-nivå) optimeringsproblem. Problem av detta slag återfinns i ekonomisk teori, till exempel för att beskriva oligopol, prissättning av infrastruktur och vissa handelsvaror såsom elenergi och kapacitet i telekommunikationsnät och för att beskriva problem inom planering och styrning av trafiksystem. Två-nivå-optimeringsproblem förekommer också inom ingenjörsvetenskaperna, där den undre nivån beskriver jämvikten hos ett mekaniskt, fysikaliskt eller kemiskt system, och den övre nivån beskriver problemet att optimera designen hos detta system. Gemensamt för två-nivå optimeringsproblem är att medan de är viktiga tillämpningsproblem är de också mycket svåra att lösa, eftersom de är icke-konvexa. För sådana problem finns dock lokala algoritmer.

Examensarbetet innebär tillämpningar av lokala algoritmer för viktiga, aktuella applikationsområden, särskilt inom optimal design av mekaniska strukturer och inom regional planering, särskilt styrning av trafik med hjälp av vägtullar.

En rapport som beskriver några modeller för optimal design av mekaniska strukturer finns här.

En två-nivå optimeringsmodell för beräknandet av vägtullar återfinns i följande rapport.

SQP och andra Newton-metoder för begränsad optimering [Ett exjobb avslutat!]

Alla har väl stött på Newtons metod i någon eller flera kurser. Den används flitigt för att numeriskt lösa problem inom snart sagt alla vetenskapliga områden. Ett välkänt problem med dess användning är att den i sin klassiska form endast är lokalt konvergent mot en stationär punkt. På senare år har en snabb utveckling skett när det gäller att skapa globalt konvergenta Newton-metoder, dvs. metoder som konvergerar oavsett val av startpunkt. De modifieringar av den klassiska ansatsen som har föreslagits är samtliga olika versioner av linjesökningar, dvs. i stället för att ta ett enhetssteg väljs steglängden adaptivt så att någon målfunktion avtar. &AUML;ven med denna åtgärd kan metoden fungera dåligt, eftersom kravet på målfunktionens avtagande kan leda till att mycket små steg tas. Aktuell forskning försöker åtgärda detta genom att införa icke-monotona linjesökningar där målfunktionens värde tillåts stiga temporärt, för att åstadkomma att längre steg tas.

Två examensarbeten definieras inom detta område:

SQP (sekventiell kvadratisk programmering) är en Newton-metod för begränsad optimering vars sökriktning bestäms av ett kvadratiskt subproblem i vilket de icke-linjära bivillkor som förekommer i problemet lineariseras. För att återställa tillåtenhet kräver existerande analyser att den målfunktion man använder i uppdateringssteget innehåller en straffunktion med en straffparameter som väljs "stor nog." En ny analys av metoden visar att man kan välja denna parameter godtyckligt liten (inklusive noll) och fortfarande bibehålla den globala konvergensen hos metoden. Nyckeln är att analysen inte kräver att den nya målfunktion som används är avtagande i varje steg. [Avslutat!]

I det andra examensarbetet studeras en nyligen föreslagen alternativ teknik för att förbättra Newtons metod. Den bygger på att linjesökningen ersätts av en multidimensionell sökning över ett underrum som spänns upp av tidigare genererade riktningar. Fördelen med denna ansats gentemot de tidigare är att optimeringen över en mångfald av högre dimension medger att längre steg tas, tack vara att all information som Newtons metod genererar bibehålls, och konvergensen blir därför både snabbare och mer robust.

Examensarbetena kan innebära en konvergensstudie av algoritmen för tillämpningar till begränsad optimering och/eller en algoritmutveckling och -tillämpning på klassiska tillämpningsproblem inom ingenjörsvetenskap och tillämpad matematik.

En rapport som ligger till grund för det första examensarbetet finns här.

En tidigare numerisk studie av en Newton-metod liknande den som behandlas i det andra examensarbetet kan läsas om i följande rapport.

Flygbesättningsoptimering [Ett exjobb avslutat!]

Vid planeringen av besättningar på flygplan måste hänsyn tas till en stor mängd regler som innefattar exempelvis fackliga regler. Vanligen löses planeringsproblemet i två steg: först konstrueras en mycket stor mängd (ofta över 1 miljon) alternativa planer som uppfyller reglerna. Därefter kombineras de så att varje rutt får en fullständig besättning och så att den totala kostnaden minimeras. Detta mycket storskaliga problem är naturligtvis också mycket svårlöst, och därför ägnas speciellt stor energi till att försöka finna vilka av de olika planerna som är bäst att kombinera, för att sedan optimera över denna mycket mindre mängd.

Examensarbetet består i att implementera en ny strategi för att gissa bra planer. För att utvärdera den finns verkliga planeringsdata från Lufthansa, och jämförande värden från tidigare strategier. Arbetet sker i samarbete med personer knutna till projekt inom företaget Carmen, som säljer ett system just för personalplanering inom tåg- och flygtransporter.

Exjobbsrapporten finns här.

Optimalitet och stabilitet hos lösningar till icke-monotona variationsolikheter [Ett exjobb avslutat!]

Ett icke-konvext obegränsat eller begränsat olinjärt optimeringsproblem kan som bekant ha stationära punkter med olika målfunktionsvärden, och ett kvalitetsmått ges just via problemets målfunktion. I icke-konvexa fall kan vissa versioner av Newtons metod garantera konvergens mot en stationär punkt som uppfyller vissa stabilitetsegenskaper, t.ex. att samtliga egenvärden till Hessianen är icke-negativa.

Tyvärr kan inte alla problem beskrivas som optimeringsproblem. Till exempel beskrivs jämviktstillstånd hos fysikaliska och kemiska system men också i system i ekonomiskt teori och regional planering med hjälp av så kallade variationsolikheter. I flera naturliga fall är dessa problem också icke-konvexa (begreppet som används i den världen är icke-monotona), men i avsaknad av en målfunktion är det svårt att avgöra arten eller kvaliteten hos en lösning. Ett mått som skulle kunna användas i samband med applikationer till jämviktssystem är egenskaperna hos egenvärdena hos en lösning, eftersom vi ofta är intresserade av att finna en stabil jämviktslösning.

Examensarbetet innebär en studie i konvergensen hos Newtons metod för applikationer till icke-monotona variationsolikheter, och numeriska beräkningar för verkliga jämviktsproblem inom speciellt regional planering. Det finns också en möjlighet att studera tvånivåmodeller för problemet att finna en stabil lösning.

För exempel på studier av variationsolikheter, tillämpningar såväl som algoritmer, se följande hemsida.

Trafikplanering och -styrning med tullar och ljussignaler [Ett exjobb avslutat!]

För att få en bild av hur förändringar i ett trafiknätverk, som till exempel konstruktionen av en ny vägsträcka, öppnandet av en ny spårvagnslinje, etc., påverkar resenärers beteende, och därmed trafikflöden, kan man med matematiska modeller beräkna tendenser som kan jämföras ungefär med det man får från en känslighetsanalys eller parametrisk analys av ett system eller ett optimeringsproblem. Med dess hjälp kan man besvara frågor av typen "om vi sänker biljettpriserna på spårvägen med en faktor X, vilka vägsträckor kommer att användas i mindre utsträckning och ungefär hur stor blir minskningen i olika delar av nätverket i förhållande till valet av X?" Sådana frågor kan besvaras som grundval för en konsekvensanalys med avseende på det totala systemets miljöpåverkan och andra "kostnader", och är till nytta för planerare av trafiknätverket i våra svenska städer.

Medan en analys av det aktuella tillståndet i trafiken kan göras genom att lösa ett optimeringsproblem som beskriver en trafikjämvikt, utförs den känslighetsanalys som beskrivs här genom att ett optimeringsproblem som liknar/approximerar det första löses. Den underliggande modellen är en nätverksflödesmodell, och även det approximativa problemet kan tolkas som en flödesmodell och kan alltså i princip lösas mycket effektivt.

Två examensarbeten kan definieras inom detta område. Problemet att beräkna känsligheten vid förändringar av vissa parametrar i modellen är ett intressant flödesproblem som måste implementeras på ett sätt som gör beräkningarna effektiva; detta för att om man vill skapa "optimala" parametervärden måste en hel sekvens av sådana problem lösas efter varandra. Ett examensarbete kan alltså fokusera på denna implementering. I vissa algoritmer som kan användas för att finna en optimal styrning av trafiken används generaliserade gradienter, så kallade "subgradienter", till den optimala lösningen till jämviktsproblemet. Att beräkna en subgradient går till på ungefär samma sätt som beräkningen av känsligheten, det vill säga, även det problemet är ett flödesproblem; tillsammans med en effektiv kod för känslighetsanalys kan ett examensarbete leda till konstruktionen av någon effektiv subgradientalgoritm, t.ex. en "bundle"-algoritm. Examensarbetena innebär dels en implementering av flödesmodellen och de approximativa problemen, dels en serie av intressanta tester på scenarier för data tagna från svenska städers trafiknät.

Det approximativa problemet beskrivs i följande rapport.

Examensrapporten finns här.

Stokastisk programmering [Två exjobb avslutade!]

En komplikation i användandet av optimeringsmodeller är att vissa storheter i problemet kanske inte är kända med säkerhet. Exempel på källor till osäkerhet i en matematisk modell är osäkerhet i en framtida ekonomisk utveckling och mätfel i teknisk utrustning. Om modellen skall användas i en beslutssituation kan det vara nödvändigt att ta beslutet innan det framtida scenariot har realiserats och med hänsyn till de fel i indata som finns. För att den implementerade lösningen skall bli så robust och kostnadseffektiv som möjligt för alla de scenarier som kan uppstå måste man ta till andra ansatser än applikationen av en vanlig optimeringsmodell, eftersom den tar hänsyn endast till ett scenario.

Lösningen är att använda en utvidgning av optimeringsmodeller till så kallad stokastisk programmering, vari data modelleras med hjälp av stokastiska variabler. Om fördelningsfunktionen hos dessa, eller en uppsättning scenarier med tillhörande sannolikheter, är känd, kan det stokastiska optimeringsproblemet sättas upp och lösas som en optimeringsmodell, som vanligen är mycket storskalig. Särskilda lösningstekniker används, där parallella algoritmer är vanliga inslag.

Examensarbetet innebär analys av parallella algoritmer för stokastisk programmering samt numeriska tillämpningar till ingenjörs- och ekonomiska problemställningar. Aktuella tillämpningar finns inom framför allt inom finans, där ett aktuellt forskningsprojekt just nu bedrivs tillsammans med ett försäkringsbolag.

Optimering av en vandrande robot

En robot skall vandra mellan två givna punkter med givna start- och sluthastigheter. Hur skall roboten styras så att den totala energiåtgången minimeras? Detta är ett optimeringsproblem där bivillkoren beskrivs med hjälp av robotens dynamiska ekvationer (partiella differentialekvationer) och start- och sluttillstånd. En diskretisering av tidsrummet görs normalt, och robotens trajektoria approximeras med polynom.

Målet med examensarbetet är att lösa optimeringsproblemet så effektivt och robust som möjligt, så att resultatet kan visualiseras i det närmaste i realtid och så att lösningen som presnteras är okänslig för små förändringar i indata. Arbetet skall utföras inom ramen för en existerande implementering av robotens dynamik i MATLAB, och bör utnyttja optimeringsskalet TOMLAB, som innehåller en stor mängd alternativa lösare av olinjära optimeringsproblem. Examensarbetet är en del i ett forskningsprojekt tillsammans med institutioner för datalogi och för robotik vid Université de Versailles och robotik vid Chalmers.

Michael Patriksson
Department of Mathematics,
Chalmers University of Technology,
Gothenburg (Göteborg)
mipat@math.chalmers.se

Back to the Official Michael Patriksson Home Page