## Linear Programming Bound for OOAs

In [1] the linear programming bound for orthogonal arrays is generalized to ordered orthogonal arrays (OOAs).

### An Alternative Formulation of the LP Bound for OOAs

An alternative formulation of the LP bound is as follows [2, Section 3]: Fix a depth T , a length/dimension s, and a base b. Let

F = {(f0,…, fT ) ⊂ ℕ0T +1  :  fi = s}

be the set of all types, let the size |⋅| : F→ℕ0 and breadth : F→ℕ0 of a type be defined by

|(f0,…, fT )| := ifi

and

(f0,…, fT ) := fi = sf0,

and define 0 := (s, 0,…, 0) ∈ F. Let the multi-variate Krawtchouk polynomial or type (f0,…, fT ) ∈ F be defined as

K(f0,…, fT )(X0,…, XT ) := bf-fKfi(Xi−1, Xi + (Xjfj))

where

Ki(X, Y) := ( – 1)j(b – 1)ij

denotes the normal Krawtchouk polynomial of degree i.

Suppose we can find a polynomial p in T + 1 variables of the form

p(X0,…, XT ) = cfPf(X0,…, XT )

such that cf ≥ 0 for all fF, c0 = 1, and p(e) ≤ 0 for all eF with | e| ≥ k + 1. Then the number of code words in any ((s, T ), N, k + 1)-NRT code satisfies

Np(0)

and the number of runs in any OOA(M, s, Sb, T , k) satisfies

MbTs/p(0).

### Explicit Solutions of the LP Bound for OOAs

Based on the alternative formulation of the LP bound stated above one can derive explicit bounds for OOAs and NRT-codes by finding suitable polynomials p. The following bounds can be derived in this manner:

### Bounds Established Using an LP-Solver

By solving the linear program (LP) described above, a lower bound on the number of runs of an OOA with given base b, depth T , strength k, and number of factors s is obtained. Solving such an LP is a computationally involved process, especially if s and T are large, because the number of variables of the LP is given by − 1. A second problem is that the LP is numerically unstable, therefore arbitrary precision arithmetic has to be used in order to obtain reliable results.

The first attempt to solving the LP directly was made by Martin and Stinson. In [1] they use Maple with exact arithmetic for solving the LPs for s ≤ 10 for depth T = 2 and for s ≤ 5 for depth T = 4, all for base b = 2 and strength k ≤ 8. This article also contains the solution of an LP for base b = 3 and depth T = 4.

In [3] the computational problems of solving the linear program are discussed. Martin uses CPLEX for obtaining an initial numerical approximation to the solution of the LP, which serves as a starting point for obtaining a feasible solution of the dual LP using exact arithmetic in Maple. Using this method, bounds on the LP bound are obtained for s ≤ 25 for depth T = 2 and for s ≤ 15 for T = 3, all in base b = 2.

For our own calculations (see [4] for details) we use the computer algebra system Mathematica® with the built-in operation “LinearProgramming”. Currently, MinT contains the following results:

• For depth T = 1, see the linear programming bound for OAs

• For depth T = 2 we have calculated all LP bounds for s ≤ 25 as well as all bounds for k ≤ 15 and s ≤ 35.

• For depth T = 3 we have calculated all LP bounds for s ≤ 11 as well as all bounds for k ≤ 20 and s ≤ 15.

• For depth T = 4 we have calculated all LP bounds for s ≤ 8 and k ≤ 19.