a sequence that needs extending

[Rob Pratt]

On Sun, 27 Jul 2003, Dean Hickerson wrote:

> > 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.
>
> Thanks for the information.
>
> Does your computation give you a list of some or all of the matrices which
> achieve those values?


The optimization terminates once it finds one optimal solution and
verifies optimality, so we obtain just one matrix (of perhaps many) for
each value of n.  But the method can be altered to give all optimal
solutions, simply by adding a constraint that excludes a given solution.
Alternatively, constraint programming is useful for generating all optimal
solutions.


> > 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.
>
> Based on your experience with a(6) and a(7), do you expect that the upper
> bound will gradually decrease as the program runs, or make a sudden drop
> to the correct value when the program finishes?


The upper bound gradually decreases.  I now know that a(8) <= 29.


If any other properties of these matrices are known, the search could be
made faster by incorporating more constraints.  For example, is it known
that every row and column will have some cell occupied, as appears to be
true from empirical evidence?


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

rpratt at email.unc.edu

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