Date: November 1993
Pages: 76
In this work probabilistic search heuristics are used in search for covering designs, packing designs and t-designs. Each covering design gives an upper bound for C_\lambda (v,m,k,t), the minimum size of a t-(v,m,k,\lambda ) covering design, while each packing design gives a lower bound for D_\lambda (v,m,k,t), the maximum size of a t-(v,m,k,\lambda) packing design, and each t-design establishes the existence of such a design. The designs are constructed using probabilistic combinatorial optimization methods including simulated annealing, tabu search, threshold accepting, great deluge algorithm and record-to-record travel. Implementation issues of these algorithms, such as cost functions and neighborhood structures are discussed. Comparisons of the performance of these algorithms on some designs is carried out. Some elementary search methods including steepest descent algorithm and random walk are included in the comparisons. Finally, the results of the searches are tabulated. The object class hierarchy of the program (written in C++) and brief class descriptions are presented in the appendix.
Keywords: Combinatorial designs, combinatorial optimization, great deluge algorithm, record-to-record travel.