Speaker: Alexander Ek, OPTIMA-University of Melbourne

High-Level Modelling and Solving for Online and Real-Time Combinatorial Optimisation

Online optimisation approaches are popular for solving optimisation problems where not all data is considered at once because it is computationally prohibitive, or because new data arrives in an ongoing fashion. Online optimisation approaches have to deal with this uncertainty and dynamism. It does so by iteratively solving the continuously changing, and growing problem to (a) improve or revise previous decisions and (b) take new ones. Typically, building an online decision-making system requires substantial problem-specific and ad-hoc coding to ensure valid and applicable solutions are computed. We define instead a general framework for automatically solving online optimisation problems. This is achieved by extending a model of the offline optimisation problem, from which an online version is automatically constructed, thus requiring no further modelling effort. We overcome three challenges: (1) how a new decision relates to the existing decisions and constraints, (2) how an existing decision can and cannot change (from implicit temporal constraints), and (3) how to identify and remove old and irrelevant decisions (avoiding system slow-down) without affecting the correctness of the end solution. These are especially challenging in a generic framework, which explains the prevalent use of problem-specific approaches. Our contribution simplifies the modelling and solving of online optimisation problems significantly, making it more efficient for experienced modellers and more accessible for novices. And we formalise many of the concepts that arise in online optimisation.

Bio:
Alexander Ek is a final year PhD candidate in the Optimisation Group at the Dept. of Data Science and AI, Monash University. He received a BSc and MSc in computer science at Uppsala University, Sweden. His research interests include combinatorial optimisation, high-level modelling, solving technologies, uncertainty and dynamism, online and real-time optimisation, multi-agent and multi-objective optimisation, fair division and resource allocation.

WED 23 FEBRUARY 4PM – 5PM AEST

ZOOM MEETING ID: 873 1557 5255; PASSWORD: 778635