| proposed by | Toby Walsh tw@cs.york.ac.uk |
With periodic boundary conditions, the situation is better. The tight connection between the correlations of periodic binary sequences and mathematical objects called cyclic difference sets can be exploited to get some exact analytical results about the states. The density of states for n up to 41 can be found at http://itp.nat.uni-magdeburg.de/~mertens/bernasconi/cyclic.shtml.
These problems pose a significant challenge to local search methods. Natural objective functions have a ``golf course'' shape, with holes in this landscape that are extremely isolated in configuration space. However, Steven Prestwich reports good results with an hybrid algorithm.