An efficient algorithm for pairwise test case generation in presence of constraints

Constraints handling problem in combinational testing is an intensive computation process. In this paper, we present an effective algorithm, called IPO SAT (In-Parameter-Order-Satisfiability), for pairwise test case generation in presence of constraints. In our strategy, constraints are denoted as forbidden tuples, which are converted to conjunctive normal form. Then, the combination test cases which meet the constraints are found out by calling Boolean satisfiability(SAT) solvers. Besides, an optimization upon the process is given, in order to improve the performance of IPO SAT by reducing the number of times of calling SAT solver and avoiding checking irrelevant constraints. Finally, experimental results show that the proposed IPO SAT algorithm is efficient and the optimization has obvious improvements on reducing time cost.