A bit-parallel tabu search algorithm for finding E($s^2$)-optimal and minimax-optimal supersaturated designs

Abstract

We prove the equivalence of two-symbol supersaturated designs (SSDs) with $N$ (even) rows, $m$ columns, $s_{\max }=4t+i$, where $i\in \{0,2\}$, $t\in {\mathbb{Z}}^{\ge 0}$ and resolvable incomplete block designs (RIBDs) whose any two blocks intersect in at most $(N+4t+i)/4$ points. Using this equivalence, we formulate the search for two-symbol E($s^2$)-optimal and minimax-optimal SSDs with $s_{\max }\in \{2,4,6\}$ as a search for RIBDs whose blocks intersect accordingly. This allows developing a bit-parallel tabu search (TS) algorithm. The TS algorithm found E($s^2$)-optimal and minimax-optimal SSDs achieving the sharpest known E($s^2$) lower bound with $s_{\max }\in \{2,4,6\}$ of sizes $(N,m)=(16,25),(16,26),(16,27),(18,23),(18,24),(18,25),(18,26),(18,27),(18,28),$ $(18,29),(20,21),(22,22),(22,23),(24,24)$, and $(24,25)$. In each of these cases no such SSD could previously be found.