#10497: Constraint Generation for TSP/Hamiltonian Cycle
----------------------------+-----------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.7.1
Component: graph theory | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author: Nathann Cohen
Merged: | Dependencies:
----------------------------+-----------------------------------------------
Comment(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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10497#comment:4>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
