Name
Title | ||
|---|---|---|
Finding Orthogonal Arrays Using Satisfiability Checkers and Symmetry Breaking Constraints |
Abstract | ||
|---|---|---|
Orthogonal arrays are very important combinatorial objects which can be used in software testing and other areas. Mathematical methods for constructing such arrays have been studied extensively in the past decades. In contrast, computer search techniques, in particular exhaustive search methods, are rarely used to solve the problem. In this paper, we present an algorithm which finds orthogonal arrays of given sizes or shows their non-existence. The algorithm is essentially a backtrack search procedure, but enhanced with some novel symmetry breaking (isomorphism elimination) techniques. The orthogonal array is generated column by column, and the constraints are checked by an efficient SAT solver or pseudo-Boolean constraint solver. We have implemented a tool called BOAS (Backtrack-style OA Searcher) using MiniSat and PBS. Experimental results show that our tool can find many orthogonal arrays quickly, especially those with strength higher than 2. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-89197-0_25 | PRICAI |
Keywords | Field | DocType |
isomorphism elimination,pseudo-boolean constraint solver,backtrack-style oa searcher,particular exhaustive search method,orthogonal array,efficient sat solver,backtrack search procedure,computer search technique,finding orthogonal,satisfiability checkers,important combinatorial object,sat solver,software testing,exhaustive search,symmetry breaking,satisfiability | Orthogonal array,Symmetry breaking,Brute-force search,Computer science,Boolean satisfiability problem,Satisfiability,Algorithm,Constraint satisfaction problem,Isomorphism,Computer search | Conference |
Volume | ISSN | Citations |
5351 | 0302-9743 | 3 |
PageRank | References | Authors |
0.42 | 9 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Feifei Ma | 1 | 58 | 13.64 |
| Jian Zhang | 2 | 288 | 24.45 |