Coarse-Graining Large Search Landscapes Using Massive Edge Collapse

A thorough understanding of discrete optimization problem instances is the foundation for the development of successful solving strategies. For this, the analysis of search spaces is a valuable tool. In particular, networks of solutions—referred to as search landscapes—are used in research. Because of the large number of solutions, topological analysis methods are typically restricted to much smaller problem instances than instances that occur in practical applications. In this paper we present a coarse-grained abstraction of search landscapes—the meta landscape—that is accessible for a complete analysis, can be computed easily and preserves relevant properties of the original search landscapes. Thus, detailed topological analysis and visualization become available for problem instances of realistic sizes. We demonstrate the use of our method for search spaces of more than 1050 solutions.