Summer Term 2018

We present different topics of our research every Thursday at 12:00 noon in room 103, Obermarkt 17. For news about the EAD-Lunch talks and seminars please feel free to subscribe to (Register here:!forum/ead-public)


14.03.2018 Markus Ullrich: A generic problem instance generator for discrete optimization problems


To measure the performance of an optimization algorithm, benchmark problems are created. In the area of discrete optimization problems most well-known problems are covered by a huge variety of problem instances already. However, once one dives further into the area of lesser known optimization problems there is usually no sufficient amount or variety of such benchmark instances available. The reasons for this lack of data vary from privacy or confidentiality issues to technical difficulties that prevent the collection of such data. This results in the inability to evaluate new optimization algorithms on matching problem instances. Ideally, the necessary data for a variety of problem instances, covering different scenarios depending on the optimization problem, can be created randomly in advance to measure the performance of a set of algorithms. The benchmark results from this process can further be used by a toolbox to select the optimal algorithm for a given problem instance based on its properties. Random problem instance generators exist for specific problems already, however, generic tools that are applicable to multiple optimization problems are rare and usually restricted to a smaller subset of problems. We propose a novel generic problem instance generator for discrete optimization problems which is easy to configure and simple to expand to cover a broad variety of optimization problems. Automating the process of creating the necessary test data leaves researchers more time to focus on creating and improving an algorithm for a certain problem.

Letzte Änderung:13. März 2018

Direktlinks & Suche