Column Generation for Interaction Coverage in Combinatorial Software Testing
This addresses the problem of reducing test cases for software developers, though it appears incremental as it builds on existing hybrid optimization techniques.
The paper tackles combinatorial software testing by proposing a column generation framework that combines Mathematical Programming and Constraint Programming to generate covering arrays with interaction coverage guarantees, resulting in a cloud service that won an Oracle challenge and is used by multiple product teams.
This paper proposes a novel column generation framework for combinatorial software testing. In particular, it combines Mathematical Programming and Constraint Programming in a hybrid decomposition to generate covering arrays. The approach allows generating parameterized test cases with coverage guarantees between parameter interactions of a given application. Compared to exhaustive testing, combinatorial test case generation reduces the number of tests to run significantly. Our column generation algorithm is generic and can accommodate mixed coverage arrays over heterogeneous alphabets. The algorithm is realized in practice as a cloud service and recognized as one of the five winners of the company-wide cloud application challenge at Oracle. The service is currently helping software developers from a range of different product teams in their testing efforts while exposing declarative constraint models and hybrid optimization techniques to a broader audience.