Exact methods for covering array generation

Abstract

Covering Arrays sind interessante kombinatorische Objekte, die Bekanntheit erlangt haben durch ihre Anwendbarkeit für kombinatorisches Testen, einem Zweig von Software Testen. Die Generierung von Covering Arrays wird normalerweise als Optimierungsproblem betrachtet, wo es gewünscht ist, ein Covering Array mit einer minimalen Anzahl von Zeilen zu finden. Durch Fortschritte in den vergangenen Jahren wurden exakte Methoden sehr effizient und anpassungsfähig, das heißt sie können bei zahlreichen Problemen angewandt werden. Für Covering Array Generierung mittels exakter Methoden existieren mehrere Kodierungen. Die Anwendung von exakten Methoden für einzelne Teile eines Covering Array Generierungsalgorithmus dagegen wurde nur selten untersucht. Der Zweck dieser Arbeit ist eine Untersuchung der Möglichkeit, Algorithmen zur Erzeugung von Covering Arrays mit exakten Methoden zu verbessern. Im Zuge dieser Arbeit wurden zwei neue Algorithmen entwickelt, die exakte Methoden, genauer gesagt SAT solving, pseudo-Boolean constraint solving und MaxSAT solving, anwenden, um Teilprobleme von Covering Array Generierungsalgorithmen zu lösen. Der vorgestellte ClassifyBalancedCAs Algorithmus kann Covering Arrays klassifizieren, also alle nicht-äquivalenten Covering Arrays einer gegebenen Größe zählen, und diese Menge von Covering Arrays generieren. In einigen Fällen ist der ClassifyBalancedCAs Algorithmus schneller als alle existierenden Algorithmen zur Klassifizierung von Covering Arrays, besonders wenn eine Optimierung namens balancebasiertes Pruning verwendet wird. Zusätzlich wurde der IPO-MAXSAT Algorithmus entwickelt, bei dem MaxSAT verwendet wird, um optimale Lösungen für Teilprobleme der In-Parameter-Order (IPO) Strategie zu finden. Dadurch, dass optimale Lösungen für Teilprobleme verwendet werden, können die Fähigkeiten und Limitierungen der IPO Strategie untersucht werden. Experimente zeigen, dass die Verwendung von optimalen Lösungen für Teilprobleme die Qualität der produzierten Covering Arrays erhöht. Sie zeigen aber auch, dass die generierten Covering Arrays dennoch nicht optimal sind. Die präsentierten Algorithmen demonstrieren, dass es vorteilhaft sein kann, existierende Covering Array Algorithmen mit exakten Methoden zu erweitern.

Covering arrays are interesting combinatorial objects that gained much popularity due to their application in combinatorial testing, which is a branch of software testing. The generation of covering arrays is usually treated as an optimization problem, where it is desired to find a covering array with a minimal number of rows. Over the past years exact methods have evolved to be efficient and highly adaptive, meaning they can be applied to many different problems. While several encodings for covering array generation with some exact methods exist, the application of exact methods for only part of a covering array generation algorithm has rarely been studied. The purpose of this thesis is examining the possibility of enhancing covering array generation algorithms with exact methods. In the course of this thesis two new algorithms were developed applying exact methods, in particular SAT solving, pseudo-Boolean constraint solving and MaxSAT solving, to subproblems occurring in algorithms for covering array generation. The proposed algorithm ClassifyBalancedCAs is capable of covering array classification, that is counting all non-equivalent covering arrays of a given size, and exhaustive generation of all such covering arrays. In several cases the ClassifyBalancedCAs algorithm is faster than all existing covering array classification algorithms, especially when an optimization called balance-based pruning is used. Additionally, the IPO-MAXSAT algorithm was developed, where MaxSAT is used to find optimal solutions for subproblems occurring in the greedy In-Parameter-Order (IPO) strategy. Using optimal solutions for subproblems allows to investigate the capabilities and limitations of the IPO strategy. Experiments show that better solutions for subproblems lead to higher quality of the generated covering arrays, however, using optimal solutions for subproblems is not sufficient to generate optimal covering arrays. The presented algorithms show that enhancing covering array generation algorithms with exact methods can be beneficial.