Prediction algorithm runtimes

Can algorithm runtimes be predicted?

An interview with Katharina Brennig

Katharina Brennig is currently in the 4th semester of her Master Degree Course in MIS (Management Information Systems) at Paderborn University and already has a Bachelor degree in International Business Studies.  Katharina has been working part-time at OPTANO GmbH since 2018 and has become an invaluable member of the OPTANO team, assuming responsibility for technical documentation, among others. Inspired by her work at OPTANO, she wrote a successful student research assignment as part of her course entitled Algorithm Runtime Prediction: Are machine learning techniques suitable for predicting the runtime of optimization models?

We wanted to find out more about Katharina’s assignment and, in particular, to what extent her findings can benefit OPTANO:

Katharina Brennig

Hi Katharina! Let’s begin by asking where you got the idea for your research assignment?

Well, I wanted a project that was practice-based and which could be of real benefit to the company and this is why I chose to write my assignment with OPTANO. I discussed the various options with my mentor and we agreed on a subject which was related to a project I was already familiar with as I had written the technical documentation for it. I really wanted to do something different, to work on a project from which I could learn and that would produce new findings – in this case:  to find out whether machine learning techniques are suitable for predicting the runtime of optimization models.

Why is it important to be able to predict the runtime of optimization algorithms?

When it comes to solving a specific problem, algorithms often exhibit extremely long and varied runtimes, despite identical instances and data sizes. For this reason, it’s often difficult to predict the amount of time an algorithm needs to solve a problem. Also, it’s not easy to determine exactly which factors cause the variations in runtime. Therefore, being able to predict the runtime of an optimization algorithm could be hugely beneficial.

And why is this especially relevant for OPTANO?

At the moment, despite the many studies that have been conducted, it still isn’t possible to estimate the runtime of an optimization problem. This applies to the OPTANO platform, too, which is why it is interesting to consider implementing a model in the OPTANO platform which can provide information on the predicted runtime of an optimization job. This would allow the user to decide whether to start the optimization or not. In addition, it is of interest for the application, especially when it comes to distributing multiple optimization jobs on multiple servers. Being able to predict the runtime could help determine whether it is necessary to start up a second server to run an optimization or whether it is worth waiting until the first server has completed the optimization, to run another one on the first server.

To solve this problem I began to focus on the topic of machine learning and tried to investigate whether machine learning techniques are suitable for predicting the runtime of optimization algorithms.

Can you tell us more about machine learning? What is it exactly and how does it work in general?

 In recent years, the concept of machine learning has become one of the most popular technologies in the field of artificial intelligence. So the general aim is to derive knowledge from existing data sets and examples by learning from historical data to improve the performance of a specific task. The goal of machine learning, therefore,  is to make predictions for new data, not to replicate data. Thereby, machine learning methods are developed to automatically recognize structures in data and solve similar cases by making use of the theory of statistics.

In general a set of features is used as the input of the model. Those features are used to find ou the relation between the input features and the related target.  Through training, the algorithm extracts a structure from the features relations that is useful for the task at hand. Once the learning phase has been completed, the newly acquired information can be generalized and patterns which have been uncovered can be applied to new problems or to predict the future data of a similar type.

In this context I should perhaps mention that there are different types of machine learning, such as supervised and unsupervised machine learning. However, I made use of supervised learning which tries to predict events in the future on the basis of past experience.

Did you know…?

  • Netflix saved $1 billion in 2018 recommending personalized TV shows and movies to subscribers as a result of its Machine Learning algorithm.
  • By the 2030s, PWC predicts that around 38% of all U.S. jobs could be replaced by AI and automation.
  • Machine Learning is in the background of almost everything people do. This ranges from filtering spam emails and recommending friends on social media to recommending personalized TV shows and movies on platforms like Netflix.

How did you proceed with your assignment?

I was inspired by the approach of empirical performance models, which play an emerging role when talking about algorithm runtime prediction and have already been evaluated and used in other studies dealing with this problem. Those models are statistical models that describe the performance of an algorithm as a function of its inputs. They also provide an insight into which factors are responsible for the performance of an algorithm.

The procedure of these models starts by selecting an algorithm and ends with training a machine learning model. As the optimization algorithm and given project had already been chosen, I started evaluating which features could be important for making predictions. While searching for relevant features, I had already tried not to focus on existing studies and evaluated features that were known before the optimization starts, such as properties of the data used to create the matrix for calculating the optimal solution. After selecting the relevant features I considered several machine learning algorithms provided by ML.NET. While training the different models, I also performed Feature Selection methods to eliminate uninformative features. This led to a further improvement of the machine learning algorithms. In this way, I focussed on the three best performing algorithms until no further improvement was possible.

Did your research come up with any new insights for OPTANO?

Yes, it resulted in new insights into the study of algorithm runtime prediction for OPTANO. Based on the project and data it was possible to roughly predict the runtime of the optimization algorithm used in the project.  To be quite sure that the use of machine learning methods are a suitable approach to the  problem, I conducted tests on other more trivial methods. However, I realized that the use of trivial methods was not sufficient to adequately predict the runtime of the optimization algorithm and that machine learning makes more precise predictions.

So will your work be useful for future OPTANO projects?

 The knowledge I’ve gained here can also be applied to other OPTANO projects in the future.  However, since each project is individual and has different influential factors, the features have to be specified anew for other projects and the machine learning algorithm has to be trained again. So you could say that each empirical performance model is specific for a given problem. That’s why I’ve drawn up a guideline for other projects which can be adapted to facilitate the selection of relevant and non-relevant features. It is important to know that there should be enough data available from which the machine learning algorithm can learn.

What did you, personally, gain from your work on the project –  besides the specific knowledge of the subject, of course? 

Well, I encountered one major challenge, which was that I had to learn how to do programming, something I wasn’t really familiar with at all. At first I was completely overwhelmed by it all  but it became a lot easier once I had found my bearings. That has definitely given my confidence a major boost, knowing that I can overcome a challenge on my own, although I have to add that the OPTANO team were there to offer their support if I needed it. And while I was generally interested in machine learning, I never expected it to be as fascinating as it eventually turned  out to be.

Katharina, thanks for the interview and good luck with your Masters Degree.

“Katharina’s research paper is highly impressive and has already been tried and tested in our OPTANO projects. Projects such as this one mean that  OPTANO can work more closely together with the university and they further underline our desire for OPTANO to be at the forefront of optimization issues. By the way, this is actually the first time we have considered using open source for a project right from the start. Also, we wanted to make our mark by applying the MIT license, which gives users extensive rights.”

Jens Peter KempkesCEO at OPTANO

Author: Alisa Temme

Are you interested in the OPTANO Algorithm Tuner?
Then read our interview with the developers of the tuner.

Other articles you may also find interesting…