Combinatorial optimisation under uncertainty: a Q&A with Franziska Eberle

What happens if the algorithm solving a problem does not have full knowledge of the problem’s parameters?

 Franziska Eberle is a Research Officer in the Department of Mathematics

Franziska Eberle 747 x 560
Franziska Eberle              

What are you currently researching?

I am mostly interested in combinatorial optimisation under uncertainty. In other words, I consider classical combinatorial optimisation problems and ask myself what happens if the algorithm solving the problem does not have complete knowledge of or full access to the problem parameters.

One example is the scheduling of computational tasks on servers, where the service provider does not know the tasks before they are submitted to the system. How should the operator assign a particular task to a machine when future tasks are still unknown?

Why did you choose this area of study?

Classical combinatorial optimisation problems model a wide range of real-world applications such as routing, scheduling, or packing. However, we cannot foretell the future, which makes these everyday tasks much harder.

Considering uncertainty when solving combinatorial optimisation problems bridges the gap between abstract mathematical models and real-world applicable solutions. 

How will your research improve or have a wider impact on society? 

To be completely honest, social impact in both theoretical computer science, which I did my PhD in, and mathematics is hard to predict and even harder to plan for. We lay the theoretical foundations for problems or develop mathematical models for technologies that have yet to be formulated or developed.

One example is Dijkstra’s algorithm solving the shortest path problem: Edsger W. Dijkstra designed the algorithm to figure out the shortest route from Groningen to Rotterdam in 1956. However, he surely did not imagine that 60 years later almost everyone would use his algorithm daily  to find the shortest path between two places on their smartphones.

So, we like to solve problems because of their inherent beauty, and in the best-case scenario our solutions will help some scientist or engineer in the future looking for the right “language” to answer their research question or to improve their invention.  

What have been the highlights of your research so far? 

For me, a highlight and of course also a motivation of my research is the feeling of gaining a better understanding of the problem I am currently working on; this feeling covers everything from making small progress or finding the overall solution to simplifying a proof.

What has been your biggest challenge so far?

My biggest challenge so far was motivating myself to finish my PhD thesis in a global pandemic where I had not seen my supervisor or my colleagues in person for several months. 

What advice would you give to prospective students on the most effetive way to approach research and keep stress levels down? 

In general, I guess that the most important aspect is to find a topic about which you are curious and to find colleagues who share this curiosity. 

For me personally, my approach to research is best described by the following quote by Elizabeth Gilbert: “I believe that inspiration will always try its best to work with you—but if you are not ready or available, it may indeed choose to leave you and to search for a different human collaborator.”

For me, this means, even on days when I feel extremely unproductive, I still show up to do research to make sure that I am available if inspiration decides to pay me a visit. Since these visits can happen quite unexpectedly, when inspiration does strike , I take it seriously and delay weekend or evening plans in favour of doing research. However, after such intense research periods , I rest for several days no matter the actual day of the week. 

The only long-term effective way for me to reduce stress is exercise, preferably in nature.