A Max-SAT-Based Approach to Constructing Optimal Covering Arrays

This paper investigates a new exact method for constructing optimal covering arrays based on first encoding the problem as a Partial MaxSAT instance, and then solving the resulting instance with a state-of-the-art MaxSAT solver. To this end, we define an original MaxSAT encoding for covering arrays, and report on the experimentation performed to evaluate our MaxSAT-based approach. The obtained results indicate that MaxSAT is a good alternative for constructing optimal covering arrays, and it is worth to further investigate this new research direction in the area of combinatorial designs. © 2013 The authors and IOS Press. All rights reserved.Peer Reviewe