Constructing Covering Designs by Simulated Annealing

Reference:

Kari J. Nurmela and Patric R. J. Östergård. Constructing covering designs by simulated annealing. Technical Report B10, Helsinki University of Technology, Digital Systems Labora tory, Espoo, Finland, January 1993.

Abstract:

A t-(v,m,k,lambda) covering design is a pair (X,A), where X is a set of v elements (called points) and A is a multiset of k-subsets of X (called blocks), such that every m-subset of X intersects at least lambda members of A in at least t points. It is required that v >= k >= t and v >= m >= t. Such a covering design gives an upper bound on C_lambda(v,m,k,t), the number of blocks in a minimal t-(v,m,k,lambda ) covering design. In this work it is shown how simulated annealing can be used in searches for covering designs. A cost function and a neighborhood structure needed by the algorithm are presented. The space complexity of the implementation and the time complexity of the cost change calculation are also given. Several options to increase the performance of the algorithm are tested. A performance comparison to local optimization is carried out. Finally, a description how to obtain, compile and use the computer program cover, which has been developed during the research, is given.

Keywords:

Combinatorial optimization, covering design, simulated annea ling

Suggested BibTeX entry:

@techreport{HUT-TCS-B10,
    address = {Espoo, Finland},
    author = {Kari J. Nurmela and Patric R. J. {\"O}sterg{\aa}rd},
    institution = {Helsinki University of Technology, Digital Systems Labora tory},
    month = {January},
    number = {B10},
    pages = {25},
    title = {Constructing Covering Designs by Simulated Annealing},
    type = {Technical Report},
    year = {1993},
}