OPTANO Algorithm Tuner – An interview with the developers

The OPTANO Algorithm Tuner is here and available free of charge. We wanted to know exactly how it works and what you can actually tune and decided to find out by asking its developers, Britta Heymann and Jannick Lange.

Britta Heymann

Britta Heymann

Britta Heymann is an OR-expert. She is mainly repsonsible for optimization but also works in software development. She developed the OPTANO Algorithm Tuner as a student worker at OPTANO and in her Master thesis.

Jannick Lange

Jannick Lange

Jannick Lange works in software development and is repsonsible for Operations Research for client projects and OPTANO Modeling. He already worked on the OPTANO Algorithm Tuner during his time as a student worker at OPTANO.

Good morning! Thanks for finding the time to tell me more about our new Algorithm Tuner. Can you explain why the Algorithm Tuner is needed?

Britta Heymann: Well, there’s a nice analogy to explain this, namely Formula 1 Racing. The teams can do a great deal of tuning on their cars, depending on how straight the racing track is, how many tight curves it has, or depending on what the weather is like, etc. So the car is retuned and tested before every race. The algorithm is the car and we can tune the parameters in different ways, depending on what the algorithm is going to be used for. In a sense, the Algorithm Tuner lets a lot of Formula 1 cars be driven and it looks to see which combination of parameters is best for the problem at hand.

Britta, you’ve been involved in the project right from the start. Where  did the idea of developing the Algorithm Tuner come from?

Britta Heymann: Algorithm tuning is an incredibly fascinating subject with very many use cases. We were given the opportunity to tackle the subject with the university a few years ago. For us, it was important to be able to focus primarily on the aspects which were significant for our purposes. That’s why we decided to develop our own tuning software. I was able to apply the first phase of the project in my degree course to some extent and later on, the Algorithm Tuner was also a part of my Master thesis.

When did you join the project, Jannick?

Jannick Lange: I joined the project after  GGA had already been implemented and I incorporated GGA++ to partly extend our algorithm tuner during a student research project I did for Professor Tierney.

What is GGA and how does it work?

Britta Heymann: The basic idea is that the tuner starts with a lot of parameter configurations and it cleverly improves these bit by bit. Configurations are tested in each procedure. Here, the algorithm calculates a certain number of input values with the configurations. The results are then compared and the best configurations are used to update the number of configurations using combinations. This is repeated again and again until we have reached an exit condition.

Jannick Lange: When new configurations are created from the best ones, this is determined randomly with GGA. The parameters of both configurations generally have a fixed probability of being selected for the new configuration. Machine learning is deployed in the case of GGA++.  Tens of thousands of random configurations are generated and “easily predicted” (this is the machine learning part) to see how well they behave. Then, the configuration with the best prediction is used. In this way, you can generate good configurations faster instead of random configurations.

The great thing about the Algorithm Tuner is that every user can choose whether to use GGA or GGA++ or a combination of the two.

And what can you do with them? Make algorithms faster?

GGA stands for Gender-Based Genetic Algorithm

Britta Heymann: Yes. (laughs) Basically, the idea of Algorithm Tuning is to configure an existing algorithm, which you might already be using, so that it is precisely tuned to the field of application or a particular type of input data you already have. You can often set any parameter for algorithms and the values which have been preset there, are, on average, also very good! However, you can find even better settings for your own, individual application. Better – you can decide for yourself what better means.  Of course this often means that the runtime is shorter. But it may also be that when you have an algorithm that only gives you proposals instead of an exact result, you will want to improve the quality of these proposals.

So in practice, you have to invest a lot of computing time at the beginning to find a good configuration. In the use phase of the algorithm, you benefit from each runtime so that overall, resources can be saved.

Is it possible to shorten the computing time at the beginning?

Britta Heymann: Parallelization is the most important thing! We can either execute parallel evaluations at the same time on one computer or we even use several computers in one computing network. This is what I would recommend –  in connection with Cloud-Computing, for example.

As far  as the runtime is concerned with tuning, we can even terminate evaluations early on if parallel results show us that the associated configuration may not be one of the best.

It’s also important to ensure that you can terminate an evaluation after a certain time. Otherwise the tuner might spend too much time on a run which has, quite by chance, started with a very poor configuration and where it is actually clear early on that it will produce a very bad result.

Which algorithms is tuning particularly suitable for? Or are there any algorithms for which it isn’t suitable?

Jannick Lange: It’s always a good idea for algorithms which have a relatively long runtime or if you have so-called run-time critical algorithms. For example, when you have a model that needs to be solved within a specific runtime. Sometimes this is only possible with tuning.

Hmm, what isn’t suitable? Well basically, an algorithm naturally has to provide parameters which the behavior can be influenced with.
Tuning is also diffcult if only very few instances are available or if individual evaluations require several hours or days. In the first case there’s a risk of overfitting, that means a parameter combination which is too specific for the training instances and generally offers no benefits. In the second case it could well be that the time required to perform tuning increases astronomically. One possible solution to this problem would be to use “smaller” instances from the same problem class for tuning – assuming that the configurations found are transferrable based on their structural similarity.

Britta Heymann: Basically, you have to decide whether you want to invest the time in tuning at the beginning. I think it’s the most useful if the algorithm fulfills a short runtime or if you use the algorithm very often. Then it’s worth it because you benefit from every run.

The faster the algorithm is from the start, the faster the tuner finds good configurations. That means that even algorithms which are realtively fast can benefit from tuning because tuning itself then works more quickly.

 Is there anything about the tuner you are particularly pleased with or especially proud of?

Britta Heymann: I’m proud of the fact that the tuner really has become as adaptable as we had imagined! And I’m so pleased that it has now been launched  – and even more so that it’s open source.

Oh yes, open source – how did that come about?

Jannick Lange: In this way, the maximum number of users that the tuner is available to is very large, irrespective of its budget. And users can easily give us feedback via Github, or propose features or even work on the code with us. We think that using the tuner keeps the hurdles low and we hope that a lot of people will use it and be able to benefit from it.

The OPTANO Algorithm Tuner is available as open source. Simply download it and try it out!

And what happens now?

Britta Heymann:  The more we work on it, the more ideas we get. (laughs). We have a couple of ideas about how we can make parallelization even better so that the tuner works even faster. Together with Bielefeld University, we’re working on improving its content: this is called graybox tuning. Here we start collecting the data even during the evaluation stage so that it can be terminated earlier. We’re excited to discover to what extent this will work and how much faster tuning will become.

Other articles you may also find interesting…