Constraint Generation for TSP/Hamiltonian Cycle

[ncohen]

Hello everybody !!!

This patch adds another way to compute through LP a hamiltonian cycle.

Apply:

• trac_10497.patch
• trac_10497-density.patch

[lsampaio]

I reviwed the patch and its correct and working fine. On the other hand, I compared the performances of the previous algorithm and the constraint generation in some examples and the second seemed to be always slower than the first. So I am not sure of why to keep the constraint generation as the default algorithm. Besides this, I believe the patch is ready to be merged with sage.

[ncohen]

Oh.. On which graphs did you test them ? Could you provide them, or the timings ?

Thanks !

Nathann

[lsampaio]

Ok, here are some of the graphs in which I've been testing the algorithms, and the corresponding timings:

#Random GNP with 30 vertices and p = 0.3 (density 0.31)

sage: g = graphs.RandomGNP(30, .3) sage: g.density() 136/435 sage: %timeit g.traveling_salesman_problem(constraint_generation = True) 25 loops, best of 3: 35 ms per loop sage: %timeit g.traveling_salesman_problem(constraint_generation = False) 5 loops, best of 3: 184 ms per loop

#Random GNP with 30 vertices and p = 0.5 (density 0.51)

sage: g = graphs.RandomGNP(30, .5) sage: g.density() 224/435 sage: %timeit g.traveling_salesman_problem(constraint_generation = True) 5 loops, best of 3: 101 ms per loop sage: %timeit g.traveling_salesman_problem(constraint_generation = False) 5 loops, best of 3: 396 ms per loop

#Random GNP with 30 vertices and p = 0.7 (density 0.68)

sage: g = graphs.RandomGNP(30, .7) sage: g.density() 20/29 sage: %timeit g.traveling_salesman_problem(constraint_generation = True) 5 loops, best of 3: 574 ms per loop sage: %timeit g.traveling_salesman_problem(constraint_generation = False) 5 loops, best of 3: 621 ms per loop

#Complete multipartite graph with 4 parts of size 10 each(density = 0.77)

sage: g = graphs.CompleteMultipartiteGraph?([10, 10, 10, 10]) sage: g.density() 10/13 # = 0.77 sage: %timeit g.traveling_salesman_problem(constraint_generation = True) 5 loops, best of 3: 6.03 s per loop sage: %timeit g.traveling_salesman_problem(constraint_generation = False) 5 loops, best of 3: 1.96 s per loop

#Complete graph on 30 vertices (density = 1)

sage: g = graphs.CompleteGraph?(30) sage: g.density() 1 sage: %timeit g.traveling_salesman_problem(constraint_generation = True) 5 loops, best of 3: 4.76 s per loop sage: %timeit g.traveling_salesman_problem(constraint_generation = False) 5 loops, best of 3: 870 ms per loop

Its clear that as the graph becomes very dense, constraint_generation tends to be much slower. What we could do is to check the density of the graph before in order to decide which algorithm use, when no algorithm was specified in the function call. In my opinion the best would be to use constraint generation when density is smaller than 0.7 and use the other algorithm otherwise.

[ncohen]

Perfectly right !

Here is a new patch to add on top of the former :-)

Nathann

[lsampaio]

In my opinion the patch is ready to be merged to sage =)

[ncohen]

Wouhouuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu !!!!

[kini]

Why have you changed "Hamiltonian" to "hamiltonian"? And why have you added French in the docstring?

[ncohen]

In this 9months old patch ? O_o

No idea O_o

Though if I remember correctly the french lines have been removed recently in an unrelated patch by David Coudert :-D

it meant "with constraint generation" and "without constraint generation". I should have changed it before sending the patch but probably forgot :-)

Nathann

[kini]

I noticed only because your patch at #12942 somehow breaks these doctests, it seems... o_O

[kini]

Oh, of course - you changed the default parameters of traveling_salesman_problem() in your patch for #12942, that's why.

[ncohen]

Oh yeah, that's because the doc said one parameter was the default even though it was not, and because a sentence stopped in the middle of something for some reason O_o

Nathann

[kini]

Can you refactor that change out into a followup to this ticket?

[ncohen]

O_o

What's the point ? This ticket it 9 months old, the function could have been touched 1000 times in the meantime, and the change is 2 lines long O_o

Nathann

[kini]

By "followup to this ticket" I don't mean it needs to actually be based on this ticket, of course... just base it on Sage 5.0.rc1. Just for logical separation of changes it would be good to do cleanup of the traveling salesman problem in a different place than implementation of the Balaban 10-cage, surely...

[ncohen]

This ticket is now #12944, and #12942 has been updated. But I really think that it's just more work for anybody, and that those two lines did not deserve it ^^;

Nathann

[kini]

Sorry, I didn't think it would be so much trouble or I would have just done it myself... :( Thanks for doing it.