Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

A generic problem instance generator for discrete optimization problems

: Ullrich, Markus; Weise, Thomas; Awasthi, Abhishek; Lässig, Jörg


Association for Computing Machinery -ACM-:
GECCO 2018, Genetic and Evolutionary Computation Conference Companion. Proceedings : Kyoto, Japan, July 15 - 19, 2018
New York: ACM, 2018
ISBN: 978-1-4503-5764-7
Genetic and Evolutionary Computation Conference (GECCO) <2018, Kyoto>
Conference Paper
Fraunhofer IOSB ()

Measuring the performance of an optimization algorithm involves benchmark instances of related problems. In the area of discrete optimization, most well-known problems are covered by a large variety of problem instances already. However, while exploring the area of lesser-known optimization problems there is usually not a 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 these problems. Ideally, the necessary data for a variety of problem instances can be created randomly in advance to measure the performance of a set of algorithms. 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 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. We show the capabilities of our tool by creating exemplary configurations for the TSP, Max-SAT and a real-world load allocation problem to generate random problem instances.