#10497 closed enhancement (fixed)
Constraint Generation for TSP/Hamiltonian Cycle
Reported by: | ncohen | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-4.7.2 |
Component: | graph theory | Keywords: | |
Cc: | Merged in: | sage-4.7.2.alpha2 | |
Authors: | Nathann Cohen | Reviewers: | Leonardo Sampaio |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #10044 | Stopgaps: |
Description (last modified by )
Hello everybody !!!
This patch adds another way to compute through LP a hamiltonian cycle.
Apply:
Attachments (2)
Change History (21)
comment:1 Changed 9 years ago by
- Status changed from new to needs_review
Changed 9 years ago by
comment:2 Changed 9 years ago by
comment:3 Changed 9 years ago by
Oh.. On which graphs did you test them ? Could you provide them, or the timings ?
Thanks !
Nathann
comment:4 Changed 9 years ago by
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.
Changed 9 years ago by
comment:5 Changed 9 years ago by
- Description modified (diff)
Perfectly right !
Here is a new patch to add on top of the former :-)
Nathann
comment:6 Changed 9 years ago by
- 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 9 years ago by
Wouhouuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu !!!!
comment:8 Changed 9 years ago by
- Dependencies set to #10044
- Description modified (diff)
- Milestone changed from sage-4.7.1 to sage-4.7.2
comment:9 Changed 9 years ago by
- Merged in set to sage-4.7.2.alpha2
- Resolution set to fixed
- Status changed from positive_review to closed
comment:10 Changed 8 years ago by
Why have you changed "Hamiltonian" to "hamiltonian"? And why have you added French in the docstring?
comment:11 Changed 8 years ago by
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 8 years ago by
I noticed only because your patch at #12942 somehow breaks these doctests, it seems... o_O
comment:13 Changed 8 years ago by
Oh, of course - you changed the default parameters of traveling_salesman_problem()
in your patch for #12942, that's why.
comment:14 Changed 8 years ago by
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 8 years ago by
Can you refactor that change out into a followup to this ticket?
comment:16 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
comment:19 Changed 8 years ago by
Sorry, I didn't think it would be so much trouble or I would have just done it myself... :( Thanks for doing it.
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.