Mathematical Problems in Engineering
Volume 2012 (2012), Article ID 897027, 19 pages
Research Article

New Bounds for Ternary Covering Arrays Using a Parallel Simulated Annealing

1Instituto Tecnológico Superior de Salvatierra, Madero 303, 38900 Salvatierra, Guanajuato, Mexico
2Information Technology Laboratory, Cinvestav Tamaulipas, Km. 5.5 Carretera Victoria-Soto La Marina, 87130 Victoria, TAMPS, Mexico
3Instituto de Instrumentación para Imagen Molecular (I3M), Universitat Politècnica de València, Camino de Vera s/n, 46022 Valencia, Spain

Received 24 February 2012; Revised 15 June 2012; Accepted 7 July 2012

Academic Editor: John Gunnar Carlsson

Copyright © 2012 Himer Avila-George et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


A covering array (CA) is a combinatorial structure specified as a matrix of N rows and k columns over an alphabet on v symbols such that for each set of t columns every t-tuple of symbols is covered at least once. Given the values of t, k, and v, the optimal covering array construction problem (CAC) consists in constructing a CA (N; t, k, v) with the minimum possible value of N. There are several reported methods to attend the CAC problem, among them are direct methods, recursive methods, greedy methods, and metaheuristics methods. In this paper, There are three parallel approaches for simulated annealing: the independent, semi-independent, and cooperative searches are applied to the CAC problem. The empirical evidence supported by statistical analysis indicates that cooperative approach offers the best execution times and the same bounds as the independent and semi-independent approaches. Extensive experimentation was carried out, using 182 well-known benchmark instances of ternary covering arrays, for assessing its performance with respect to the best-known bounds reported previously. The results show that cooperative approach attains 134 new bounds and equals the solutions for other 29 instances.