Tänja på gränserna för storskalig diskret optimering: Ny matematik och algoritmer för metoder som används tillsammans med Dantzig-Wolfe-dekomposition
Under de senaste decennierna har det skett en imponerande utveckling av metoder för att lösa diskreta optimeringsproblem. Speciellt så har Mixed-Integer Programming (MIP)-lösare—såsom Gurobi och SCIP—utvecklats till exceptionellt kraftfulla verktyg som kan lösa en mängd utmanande och praktiskt relevanta problem. Det är dock fortfarande vanligt att dessa lösare misslyckas med att leverera en lösning för utmanande instanser även inom veckor eller år av beräkningstid, på grund av att problemen är NP-svåra. För dessa typer av problem kan användningen av dekompositionsmetoder som utnyttjar problemstruktur vara lösningen. Istället för att lösa ett stort problem så löser man en serie enklare problem på ett sätt som ger en konvergens till att lösa det ursprungliga problemet. Mer specifikt så handlar vårt projekt om Dantzig-Wolfe-dekomposition, vilket är en standardmetod för beräkningsmässigt utmanande problem inom viktiga tillämpningsområden såsom fordonsruttning och flygplanering, där det är känt att MIP-lösare inte presterar tillräckligt bra.
MIP-lösare kan inte användas direkt i kombination med Dantzig-Wolfe-dekomposition, och istället används Branch-and-Price(-and cut)-lösare. Även om generiska lösare av denna typ visar stor potential så är de inte lika mogna som MIP-lösarna och forskning behövs för att både förbättra beräkningsprestanda och göra dem mer anpassningsbara till olika typer av problemstrukturer. Syftet med detta projekt är att utveckla ny matematisk teori och algoritmkomponenter för att förbättra beräkningsprestandan hos optimeringsmetoder som används i kombination med Dantzig-Wolfe-dekomposition.
Projektinformation
Detta projekt finansieras som ett akademiskt doktorandprojekt inom WASP för Diana Gutierrez Diaz. Huvudhandledare är Elina Rönnberg och biträdande handledare är Marco Lübbecke (RWTH Aachen University).
