[seqfan] Re: A264041

[Rob Pratt]

382 <= a(27) <= 383

a(29) = 440

For n in {2,4,...,100}, a(n) = n(n+1)/2

Let b(n) denote the number of optimal solutions.  Then b(1) = 2, b(2) = 4, b(3) = 28, b(4) = 108, b(5) = 2, b(6) = 13968, b(7) = 480, b(8) > 14000, b(9) > 5000.

-----Original Message-----
From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Neil Sloane
Sent: Saturday, November 07, 2015 3:54 PM
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
Subject: [seqfan] Re: A264041

Robert, A264041 is indeed a lovely sequence.

When n is odd, you say there can be more than one solution.

For odd n >= 7, there is quite a contrast between the pictures on the left (for n odd) and on the right (for n even).

On the left the examples you give have no symmetry at all. If there are a lot of solutions, is it possible that there are symmetric solutions that you didn't see? For small odd n, 5, 7, 9, say, do you have a feeling for how big the solution space is?

If it is the case that for some odd n the solution is unique AND ugly, that would be an interesting fact

[This is of course a question that often arises in packing problems. Are optimal solutions necessarily beautiful? But it is rare to see a problem where half the time the solution is beautiful, half the time not.]

Best regards
Neil

Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com


On Thu, Nov 5, 2015 at 8:11 PM, <israel at math.ubc.ca> wrote:

> Thanks, Rob. That seems like a good idea: this problem has maximal 
> 4-cliques (corresponding to slashes meeting at an interior vertex) as 
> well as 2-cliques. However, it still doesn't look like Cplex is going 
> to manage to compute a(27) on my computer.
>
> Cheers,
> Robert
>
> On Nov 4 2015, Rob Pratt wrote:
>
> 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.
>>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>

_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/