a sequence that needs extending

[Rob Pratt]

Regarding sequence A070214 (Maximal number of occupied cells in all
monotonic matrices of order n), I have confirmed the first five values of
a(n) and also determined that a(6) = 14 and a(7) = 19.  My method of
attack is integer programming.  I came up with the following symmetric
formulation that reveals the interchangeability of the roles of row,
column, and color.

The (binary) decision variables are x(i,j,k) for i in 1..n, j in 1..n,
k in 1..n.  The interpretation is that x(i,j,k) = 1 if cell (i,j) is
colored k, and x(i,j,k) = 0 if cell (i,j) is unoccupied/uncolored.

The objective function to be maximized is
sum [i in 1..n, j in 1..n, k in 1..n] x(i,j,k).

We have six sets of constraints.

At most one color per cell:
sum [k in 1..n] x(i,j,k) <= 1 for i in 1..n, j in 1..n

No zero slope:
sum [j in 1..n] x(i,j,k) <= 1 for i in 1..n, k in 1..n

No infinite slope:
sum [i in 1..n] x(i,j,k) <= 1 for j in 1..n, k in 1..n

Rows increasing:
x(i,j_1,k_1) + x(i,j_2,k_2) <= 1
for i in 1..n, 1 <= j_1 < j_2 <= n, 1 <= k_2 < k_1 <= n

Columns decreasing:
x(i_1,j,k_1) + x(i_2,j,k_2) <= 1
for 1 <= i_1 < i_2 <= n, j in 1..n, 1 <= k_1 < k_2 <= n

No negative slope:
x(i_1,j_1,k) + x(i_2,j_2,k) <= 1
for 1 <= i_1 < i_2 <= n, 1 <= j_1 < j_2 <= n, k in 1..n

After optimization, the color of cell (i,j) can be recovered as
sum [k in 1..n] k * x(i,j,k), where color 0 means unoccupied/uncolored.

A nice feature of an integer programming approach is that upper bounds are
available throughout the computation, so that we have some measure of the
quality of the current best known solutions.  For example, I know that
a(8) <= 30, so Dean's 23-cell solution is at most 7 away from optimal.

Rob Pratt
Department of Operations Research
The University of North Carolina at Chapel Hill

rpratt at email.unc.edu

http://www.unc.edu/~rpratt/