[seqfan] Re: A264041

[Rob Pratt]

If you used an edge-based formulation with constraints of the form x_i + x_j <= 1 for edge (i,j), you might be able to squeeze out a few more terms by instead using a clique-based formulation. Explicitly, precompute all (maximal) cliques and then use constraints sum {i in C} x_i <= 1 for each clique C.  This formulation has a tighter linear programming relaxation.

> On Nov 2, 2015, at 7:18 PM, "israel at math.ubc.ca" <israel at math.ubc.ca> wrote:
> 
> You may find this sequence, which I've just contributed, to be interesting. The Name is "Largest number of vertex-disjoint / and \ that can be packed in an n x n grid". Here we think of / and \ as forming diagonals of grid squares; we don't allow / and \ to be adjacent horizontally or vertically, because they would have a vertex in common (/\ or \/ or \ / or / \) or two / to be diagonally adjacent northeast to southwest, or two \ to be diagonally adjacent northwest to southeast: ./ / or \ .\
> 
> This is equivalent to a Maximum Independent Set problem on a graph with 2*n^2 vertices. The best way I've found to solve it is using Cplex on the corresponding binary linear programming problem: in this way I've obtained a(n) for n up to 26. Optimal solutions for even n have a very regular structure, e.g. for n=4
> 
> ////
> .../
> //./
> ././
> 
> For odd n>=5, patterns similar to that are suboptimal, and the optimal solutions don't seem to have a simple pattern. Strangely enough, however, there is a rather simple empirical generating function (found using Maple's "guessgf") that fits all the data I have:
> (1+2*x+2*x^2+2*x^3+3*x^4+x^5+x^6)*x/(1-x-x^2+x^3-x^6+x^7+x^8-x^9)
> 
> A proof of correctness of this g.f. (or even that it provides a bound) would be welcome. Also welcome would be more terms, or programs to produce them in a reasonable time.
> Cheers,
> Robert
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/