Tabu Search and Perturbation Methods in the Construction of Supersaturated Designs

SYNOPTIC ABSTRACT

We adapt the columnwise-pairwise algorithm (CP) of Li and Wu (1997) to the construction of multi- and mixed-level supersaturated designs. One inherent difficulty associated with the use of many heuristic algorithms is premature convergence to a local optima. Meyer and Nachtsheim (1988) discussed the use of simulated annealing method for constructing D-optimal designs. As an extension to their work, this research proposes two modified CP algorithms: tabu-enhanced CP and CP with perturbation. The performance of the two methods is evaluated in the construction of multi-level supersaturated designs. Using these algorithms yields a class of supersaturated designs that is more efficient than existing designs in terms of the optimality criteria. Results are also compared with Fang, Lin, and Ma (2000). The application of the CP algorithms to mixed-level supersaturated designs is examined as well.

Key Words and Phrases:

• CP algorithm
• perturbation method
• supersaturated designs
• tabu search