  Orthogonal arrays play a fundamental role in many applications. However,
constructing orthogonal arrays with the required parameters for an application
usually is extremely difficult and, sometimes, even impossible. Hence there is
an increasing need for a relaxation of orthogonal arrays to allow a wider
flexibility. The latter has lead to various types of arrays under the name of
``nearly-orthogonal arrays'', and less often ``almost orthogonal arrays''. The
aim of this paper is twofold. On the one hand, we review all the existing
relaxations, comparing and discussing them in depth. On the other hand, we
explore how to find almost orthogonal arrays three ways: using integer
programming, local search meta-heuristics and algebraic methods. We compare all
our search results with the ones existing in the literature, and we show that
they are competitive, improving some of the existing arrays for many
non-orthogonality measures. All our found almost orthogonal arrays are
available at a public repository.
