Constraint Models for the Covering Test Problem |
| |
Authors: | Brahim Hnich Steven D Prestwich Evgeny Selensky Barbara M Smith |
| |
Affiliation: | (1) Faculty of Computer Science, Izmir University of Economics, Izmir, Turkey;(2) Cork Constraint Computation Centre, University College, Cork, Ireland;(3) Vidus Limited, Ipswich, UK |
| |
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. |
| |
Keywords: | Modelling Covering arrays Symmetry Local search Testing Chanelling constraints Global constraints |
本文献已被 SpringerLink 等数据库收录! |
|