Abstract

A constraint satisfaction problem, namely the generation of Balanced Incomplete Block Designs ( v, b, r, k, λ )-BIBDs, is cast in terms of function optimization. A family of cost functions that both suit the problem and admit a neural implementation is defined. An experimental comparison spanning this repertoire of cost functions and three neural relaxation strategies (Down-Hill search, Simulated Annealing and a new Parallel Mean Search procedure), as applied to all BIBDs of up to 1000 entries, has been undertaken. The experiments were performed on a Connection Machine CM-200 and their analysis required a careful study of performance measures. The simplest cost function stood out as the best one for the three strategies. Parallel Mean Search, with several processors searching cooperatively in parallel, could solve a larger number of problems than the same number of processors working independently, but Simulated Annealing yielded overall the best results. Other conclusions, as detailed in the paper, could be drawn from the comparison, BIBDs remaining a challenging problem for neural optimization algorithms.