Download

With non-periodic boundary conditions, problems have only been solved by exhaustive enumeration of all configurations. This has found ground states up to n=50. The ground states for n from 17 to 50 can be found at http://itp.nat.uni-magdeburg.de/~mertens/bernasconi/open.dat.

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.

Recently (September 2008), Steven Halim, Roland H.C. Yap and Felix Halim proposed a Stochastic Local Search algorithm (Tabu Search) called TSv7 (C source code) which performs at the state-of-the-art level. They report their findings in their paper and website.

 n  E(s)  F(s)  Runtime   Limit  Best Found LABS in Run Length Notation
61   226  8.23      3 m   1.1 h  33211112111235183121221111311311
62   235  8.18      8 m   1.5 h  112212212711111511121143111422321
63   207  9.59      4 m   2.0 h  2212221151211451117111112323231
64   208  9.85     47 m   2.7 h  223224111341121115111117212212212
65   240  8.80    2.2 h   3.7 h  132323211111711154112151122212211
66   265  8.22    3.1 h   4.9 h  24321123123112112124123181111111311
67   241  9.31    4.1 h   6.6 h  12112111211222B2221111111112224542
68   250  9.25    6.6 h   8.8 h  11111111141147232123251412112221212
69   274  8.69    8.2 h  11.8 h  111111111141147232123251412112221212
70   295  8.31   12.4 h  15.8 h  232441211722214161125212311111111
------------------------------------------------------------------------
71   275  9.17    7.8 h  10.0 h  241244124172222111113112311211231121
72   300  8.64    2.4 h  10.0 h  1111114111444171151122142122224222
73   308  8.65    1.2 h  10.0 h  1111112311231122113111212114171322374
74   349  7.85    0.2 h  10.0 h  11321321612333125111412121122511131111
75   341  8.25    8.0 h  10.0 h  12122132121211211111131111618433213232
76   338  8.54    4.6 h  10.0 h  111211112234322111134114212211221311B11
77   366  8.10    3.9 h  10.0 h  111111191342222431123312213411212112112