[DMO] Esther Julien: Neur2RO: Neural two-stage robust optimization

14 December 2023 14:00 till 15:00 - Location: Elektron, 01.230 | Add to my calendar

Robust optimization provides a mathematical framework for modeling and computing solutions to decision-making problems under worst-case uncertainty. In this talk I will present recent work in two-stage robust optimization (2RO) problems, wherein first-stage and second-stage decisions are made before and after uncertainty is realized. This results in a nested min-max-min optimization problem, which generally means that we are dealing with computationally challenging problems, especially in case of integer decisions. Together with my co-authors, we propose Neur2RO, an efficient machine learning-based algorithm. We learn to estimate the value function of the second-stage problem via a neural network architecture designed to construct an easy-to-solve surrogate optimization problem. Our computational experiments on two 2RO benchmarks demonstrate that we can find near-optimal solutions among different sizes of instances, often within orders of magnitude less computing time.
In this talk we mostly focus on multi-colouring. An (n,k)-colouring of a graph is an assignment of a k-subset of {1, 2, . . . , n} to each vertex such that adjacent vertices receive disjoint subsets. And the question we are looking at is: given a graph G that is (n,k)-colourable, how large can we guarantee an (n',k')-colourable induced subgraph to be (for some given (n',k'))? Answering that question leads to having to look at combinatorial objects such as set systems and Kneser graphs, and is connected to several open problems in those areas.
This is joint work with Xinyi Xu.