Skip to main content
SpringerLink
Log in

Constraint Models for the Covering Test Problem

  • Published:
Constraints Aims and scope Submit manuscript

Abstract

Covering arrays can be applied to the testing of software, hardware and advanced materials, and to the effects of hormone interaction on gene expression. In this paper we develop constraint programming models of the problem of finding an optimal covering array. Our models exploit global constraints, multiple viewpoints and symmetry-breaking constraints. We show that compound variables, representing tuples of variables in our original model, allow the constraints of this problem to be represented more easily and hence propagate better. With our best integrated model, we are able to either prove the optimality of existing bounds or find new optimal solutions, for arrays of moderate size. Local search on a SAT-encoding of the model is able to find improved solutions and bounds for larger problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Bacchus, F., & van Beek, P. (1998). On the conversion between non-binary and binary constraint satisfaction problems. Proceedings of the 15th National Conference on Artificial Intelligence, AAAI 98 (pp. 311–318).

  2. Bryce, R., Colbourn, C., & Cohen, M. (2005). A framework of greedy methods for constructing interaction tests. The 27th International Conference on Software Engineering (ICSE 2005) (pp. 146–155).

  3. Cha, B., & Iwama, K. (1996). Adding new clauses for faster local search. In Proceedings of the 13th National Conference on Artificial Intelligence, AAAI 96, Vol. 1 (pp. 332–337).

  4. Chateauneuf, M., & Kreher, D. (2002). On the state of strength-three covering arrays. J. Comb. Des. 10(4), 217–238.

    Article  MathSciNet  Google Scholar 

  5. Cheng, B. M. W., Choi, K. M. F., Lee, J. H. M., & Wu, J. C. K. (1999). Increasing constraint propagation by redundant modeling: An experience report. Constraints 4, 167–192.

    Article  Google Scholar 

  6. Cohen, D. M., Dalal, S. R., Fredman, M. L., & Patton, G. C. (1997). The AETG system: an approach to testing based on combinatorial design. IEEE Trans. Softw. Eng. 23(7), 437–444.

    Article  Google Scholar 

  7. Cohen, D. M., Dalal, S. R., Parelius, J., Patton, G. C. (1996). The combinatorial design approach to automatic test generation. IEEE Software 13(5), 83–88.

    Article  Google Scholar 

  8. Cohen, M. B., Gibbons, P. B., Mugridge, W. B. & Colbourn, C. J. (2003). Constructing test suites for interaction testing. ICSE ’03: Proceedings of the 25th International Conference on Software Engineering, (pp. 38–48). IEEE Computer Society.

  9. Colbourn, C. J., Cohen, M., & Turban, R. (2004). A deterministic density algorithm for pair wise interaction coverage. The IASTED International Conference on Software Engineering (pp. 242–252).

  10. Colbourn, C. J. (2005) Combinatorial aspects of covering arrays. Le Matematiche (Catania), to appear.

  11. Dechter, R., & Pearl, J. (1989). Tree clustering for constraint networks. Artif. Intell. 38, 353–366.

    Article  MathSciNet  Google Scholar 

  12. Flener, P., Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., Pearson, J., & Walsh, T. (2002). Breaking row and column symmetry in matrix models. In P. van Hentenryck, (Ed.), Principles and Practice of Constraint Programming - CP-2002), LNCS 2470 (pp. 462– 476). Springer.

  13. Flener, P., Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., & Walsh, T. (2002). Matrix modelling: exploiting common patterns in constraint programming. In A. Frisch, (Ed.), Proceedings of the International Workshop on Reformulating Constraint Satisfaction Problems (pp. 27–41).

  14. Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., & Walsh, T. (2002). Global constraints for lexicographic orderings. In P. van Hentenryck, (Ed.), Principles and Practice of Constraint Programming—CP-2002, LNCS 2470 (pp. 93–108). Springer.

  15. Gent, I. P., & Walsh, T. (1995). Unsatisfied variables in local search. In J. Hallam, (Ed.), Hybrid Problems, Hybrid Solutions (pp. 73–85). IOS Press.

  16. Hartman, A., & Raskin, L. (2004). Problems and algorithms for covering arrays. Discrete Math. 284(1–3), 149–156.

    Article  MathSciNet  Google Scholar 

  17. Hnich, B., Prestwich, S. D., & Selensky, E. (2005). Constraint-based approaches to the covering test problem. In B. Faltings, A. Petcu, F. Fages, & F. Rossi, (Eds.), Recent Advances in Constraints, Joint ERCIM/CoLogNet International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2004, LNCS 3419 (pp. 172–186). Springer.

  18. Kask, K., & Dechter, R. (1995). GSAT and local consistency. In C. Mellish, (Ed.), Proceedings of the 14th International Joint Conference on Artificial Intelligence, IJCAI 95 (pp. 616–622).

  19. Lei, Y., & Tai, K. C. (1998). In-parameter-order: a test generation strategy for pairwise testing. In Third IEEE International High-Assurance Systems Engineering Symposium (pp. 161–254).

  20. Meagher, K., & Stevens, B. (2005). Group construction of covering arrays. J. Comb. Des. 13(1), 70–77.

    Article  MathSciNet  Google Scholar 

  21. Kobayashi, N. (2002). Design and Evaluation of Automatic Test Generation Strategies for Functional Testing of Software. PhD thesis, Osaka University.

  22. Nurmela, K. (2004). Upper bounds for covering arrays by Tabu search. Discrete Appl. Math. 138, 143–152.

    Article  MATH  MathSciNet  Google Scholar 

  23. Prestwich, S. (2003). Negative effects of modeling techniques on search performance. Ann. Oper. Res. 118, 137–150.

    Article  MATH  MathSciNet  Google Scholar 

  24. Régin, J. (1996). Generalized arc consistency for global cardinality constraints. Proceedings of the 13th National Conference on Artificial Intelligence, AAAI 96, (pp. 209–215). AAAI Press/The MIT Press.

  25. Rényi, A. (1971). Foundations of Probability. Wiley.

  26. Selman, B.,Kautz, H. A., & Cohen, B. (1994). Noise strategies for improving local search. Proceedings of the 12th National Conference on Artificial Intelligence, AAAI 94, Vol. 1 (pp. 337–343).

  27. Selman, B., Levesque, H., & Mitchell, D. (1992). A new method for solving hard satisfiability problems. Proceedings of the 10th National Conference on Artificial Intelligence, AAAI 92 (pp. 440–446).

  28. Seroussi, G., & Bshouty, N. (1988). Vector sets for exhaustive testing of logic circuits. IEEE Trans. Info. Theory IT-34, 513–522.

    Article  MathSciNet  Google Scholar 

  29. Sloane, N. J. A. (1993). Covering arrays and intersecting codes. J. Comb. Des. Vol. 1, 51–63.

    MATH  MathSciNet  Google Scholar 

  30. Smith, B. M. (2002). A dual graph representation of a problem in ‘Life.’ In P. van Hentenryck (Ed.), Principles and Practice of Constraint Programming—CP-2002, LNCS 2470 (pp. 402–414). Springer.

  31. Tung, Y.-W., & Aldiwan, W. (2000). Automating test case generation for the new generation missionsoftware system. Proceedings IEEE Aerospace Conference, Vol. 1 (pp. 431–437).

  32. Williams, A. W. (2000). Determination of test configurations for pair-wise interaction coverage. Proceedings of the 13th International Conference on the Testing of Communicating Systems (TestCom 2000) (pp. 59–74).

Download references

Author information

Authors and Affiliations

  1. Faculty of Computer Science, Izmir University of Economics, Izmir, Turkey

    Brahim Hnich

  2. Cork Constraint Computation Centre, University College, Cork, Ireland

    Steven D. Prestwich & Barbara M. Smith

  3. Vidus Limited, Ipswich, UK

    Evgeny Selensky

Authors
  1. Brahim Hnich
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Steven D. Prestwich
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Evgeny Selensky
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Barbara M. Smith
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Brahim Hnich.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hnich, B., Prestwich, S.D., Selensky, E. et al. Constraint Models for the Covering Test Problem. Constraints 11, 199–219 (2006). https://doi.org/10.1007/s10601-006-7094-9

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10601-006-7094-9

Keywords

Search

Navigation