[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