a sequence that needs extending

[Rob Pratt]

On Tue, 29 Jul 2003, Dean Hickerson wrote:

> > 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?
>
> As far as I know that hasn't been proved, but I'd be very surprised if it
> turned out to be false.
>
> Have you tried dropping the requirement that x(i,j,k) be 0 or 1, and instead
> let it be any real number in [0,1]?  That should make the program faster,
> right?  I wonder if it gives any useful bounds on a(n).

Yes, in fact, this is the starting point for solving the integer
program--solve the linear programming relaxation obtained by ignoring
integrality.  More accurately, this step occurs after some preprocessing
and cutting plane generation (automatically added constraints that improve
the formulation).

At least for small n, the bound from solving the LP relaxation is n^2.

Another empirical property gleaned from the optimal solutions I've seen is
that cell (1,1) is colored 1 and cell (n,n) is colored n.  Can this
property be shown to hold without loss of optimality?

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

rpratt at email.unc.edu

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