Opened 11 years ago

Closed 10 years ago

# Constraint Generation for TSP/Hamiltonian Cycle

Reported by: Owned by: ncohen jason, ncohen, rlm major sage-4.7.2 graph theory sage-4.7.2.alpha2 Nathann Cohen Leonardo Sampaio N/A #10044

Hello everybody !!!

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

Apply:

### comment:1 Changed 11 years ago by ncohen

• Status changed from new to needs_review

### comment:2 Changed 11 years ago by 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.

### comment:3 Changed 11 years ago by ncohen

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

Thanks !

Nathann

### comment:4 Changed 11 years ago by 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.

### comment:5 Changed 11 years ago by ncohen

• Description modified (diff)

Perfectly right !

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

Nathann

### comment:6 Changed 10 years ago by lsampaio

• Reviewers set to Leonardo Sampaio
• Status changed from needs_review to positive_review

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

### comment:7 Changed 10 years ago by ncohen

Wouhouuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu !!!!

### comment:8 Changed 10 years ago by jdemeyer

• Dependencies set to #10044
• Description modified (diff)
• Milestone changed from sage-4.7.1 to sage-4.7.2

### comment:9 Changed 10 years ago by jdemeyer

• Merged in set to sage-4.7.2.alpha2
• Resolution set to fixed
• Status changed from positive_review to closed

### comment:10 Changed 10 years ago by kini

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

### comment:11 Changed 10 years ago by 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

### comment:12 Changed 10 years ago by kini

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

### comment:13 Changed 10 years ago by kini

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

### comment:14 Changed 10 years ago by 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

### comment:15 Changed 10 years ago by kini

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

### comment:16 Changed 10 years ago by 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

### comment:17 Changed 10 years ago by 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...

### comment:18 Changed 10 years ago by 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

### comment:19 Changed 10 years ago by kini

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

Note: See TracTickets for help on using tickets.