TCS / Research / Publications / Constructing Combinatorial Designs by Local Search
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

Constructing Combinatorial Designs by Local Search


Kari J. Nurmela. Constructing combinatorial designs by local search. Research Report A27, Helsinki University of Technology, Digital Systems Laboratory, Espoo, Finland, November 1993.


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.


Combinatorial designs, combinatorial optimization, great deluge algorithm, record-to-record travel

Suggested BibTeX entry:

    address = {Espoo, Finland},
    author = {Kari J. Nurmela},
    institution = {Helsinki University of Technology, Digital Systems Laboratory},
    month = {November},
    number = {A27},
    pages = {76},
    title = {Constructing Combinatorial Designs by Local Search},
    type = {Research Report},
    year = {1993},

NOTE: Reprint of Master's thesis; see URL below.
PostScript (649 kB)
GZipped PostScript (167 kB)
See ...

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 19 January 2010.