Modelling constant weight codes using tabu search

AbstractIn this paper a recently developed combinatorial optimisation technique known as tabu search is used to investigate lower bounds on the optimal sizes of some constant weight codes. A feature of tabu search is the use of a memory facility that inhibits entrapment of the search by local optima, enabling the algorithm to continue searching for global optima. It is shown how tabu search may be formulated in a context appropriate to the modelling of constant weight codes. Furthermore a comparison with results obtained using simulated annealing shows that, in some instances, tabu search may give better (i.e., higher) lower bounds on code sizes