[seqfan] Re: A264041

israel at math.ubc.ca israel at math.ubc.ca
Fri Nov 6 02:11:40 CET 2015


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.




More information about the SeqFan mailing list