Opened 11 years ago
Closed 9 years ago
#2203 closed enhancement (fixed)
Add a traveling salesman problem solver
Reported by: | jason | Owned by: | ncohen |
---|---|---|---|
Priority: | major | Milestone: | sage-4.4.4 |
Component: | graph theory | Keywords: | |
Cc: | Merged in: | sage-4.4.4.alpha0 | |
Authors: | Nathann Cohen | Reviewers: | Jason Grout, David Joyner, Minh Van Nguyen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Concorde is a state-of-the-art traveling salesman problem solver and it's GPL! :)
http://www.tsp.gatech.edu/concorde/index.html
I have a student that might be interested in implementing an interface, so email me if you plan on working on this and I'll forward it to him.
Apply:
Attachments (2)
Change History (34)
comment:1 Changed 11 years ago by
comment:2 Changed 11 years ago by
- Summary changed from Integrate concorde in Sage to make an optional package for concorde in Sage
comment:3 Changed 11 years ago by
- Milestone changed from sage-2.10.2 to sage-wishlist
comment:4 Changed 10 years ago by
- Owner changed from rlm to jason
comment:5 Changed 10 years ago by
Another option for a Traveling Salesman Problem solver is the code here:
http://www.cs.utoronto.ca/~neto/
Specifically, http://www.cs.utoronto.ca/~neto/research/lk/
It is GPL.
comment:6 Changed 10 years ago by
- Summary changed from make an optional package for concorde in Sage to Add a traveling salesman problem solver
comment:7 Changed 10 years ago by
Also, the student referenced above does not currently have the time to work on this, so if you want to work on it, go right ahead.
comment:8 Changed 10 years ago by
This package of algorithms seems to be very famous in the world of TSP solvers : http://www.cs.sunysb.edu/~algorith/implement/tsp/distrib/tsp_solve/tsp_solve-1.3.6.tar.gz It contains both exact and heuristical solvers.. The thing is that I read nowhere it was licensed under the GPL license, but the beginning of the README file contains : TspSolve? -- Copyright(c) 1994 Free Software Foundation
Still< i do not knwo what it means ;-)
comment:9 Changed 10 years ago by
The README file also has the distribution license, near the bottom of the file. It appears to be GPL-compatible but slightly stronger than the modified BSD.
I agree that "Copyright(c) 1994 Free Software Foundation" at the top of the file is odd!
comment:10 Changed 10 years ago by
I tried to send an email to the author but his mail address seems to be outdated.... I found another and was not luckier.. In the end, is it SAGE-Compatible ? ;-)
Nathann
comment:11 Changed 10 years ago by
I just sent an email to the author. (It seems he has just used a commercial spam filter so you have to jump through a few hoops to get his email to be actually delivered to his inbox.)
Yes, the license is GPL-compatible, hence Sage-compatible. I pointed out in my email to his that IANAL but it seems to me that he (the author) cannot both assign the copyright to someone else and also issue a distribution license of *his* own choosing.
comment:12 Changed 9 years ago by
- Report Upstream set to N/A
- Status changed from new to needs_review
I'm pretty glad to have found a way to write this as a linear programs without having to define too many constraints, and without having to use column generation... So here are the long-awaited functions ! :-))))))))
If anyone is interested in steiner trees, they should not be hard to write either...
Well, clearly Concorde is miles above this function, but I have attempted to interface it 3 times so far, and each time I left my office cursing their (abscence of) documentation... :p
Nathann
comment:13 Changed 9 years ago by
- Milestone changed from sage-wishlist to sage-4.3.3
comment:14 Changed 9 years ago by
Nice!
A small comment: I think "is_*" functions should return either True or False. We have is_hamiltonian() returning False or an object. I think it would be more consistent to have a hamiltonian_cycle() function that returns a TSP or False, and maybe also an is_hamiltonian function that just returns True and False.
comment:15 Changed 9 years ago by
Here is my dilemma : I first thought of having an argument cycle=True in is_hamiltonian to make it return the cycle whenever possible, then noticed that if Graph() would work well anyway, so it wouldn't matter in the end. The thing is that a hamiltonian_cycle function would be a complete alias of travelling_salesman_problem, and also that I always feel bad talking about "cycles" when this function returns a "circuit" (in a digraph). So from my point of view, hamiltonian_cycle is not meant to be applied to directed graphs....
Well, if you can find your way through all this... :-)
Nathann
comment:16 Changed 9 years ago by
( ... after some email ... )
Ok, ok, I got it !! Here is the new version of this patch ! ;-)
Nathann
comment:17 Changed 9 years ago by
I installed it and ran sage -testall. No Failures.
Then I installed glpk and ran sage -testall --optional and got (among lots of other failures which are presumably unrelated) this:
jeeves:sage-4.3.2 wdj$ ./sage -t --optional "devel/sage/sage/graphs/generic_graph.py" sage -t --optional "devel/sage/sage/graphs/generic_graph.py" ********************************************************************** File "/Users/wdj/sagefiles/sage-4.3.2/devel/sage/sage/graphs/generic_graph.py", line 4097: sage: g.vertex_disjoint_paths(0,1) # optional - requires GLPK or CBC Exception raised: Traceback (most recent call last): File "/Users/wdj/sagefiles/sage-4.3.2/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/Users/wdj/sagefiles/sage-4.3.2/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/Users/wdj/sagefiles/sage-4.3.2/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_69[3]>", line 1, in <module> g.vertex_disjoint_paths(Integer(0),Integer(1)) # optional - requires GLPK or CBC###line 4097: sage: g.vertex_disjoint_paths(0,1) # optional - requires GLPK or CBC File "/Users/wdj/sagefiles/sage-4.3.2/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 4101, in vertex_disjoint_paths [obj, flow_graph] = self.flow(s,t,value_only=False, integer=True, use_edge_labels=False, vertex_bound=True) File "/Users/wdj/sagefiles/sage-4.3.2/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 3986, in flow [p.add_constraint([flow[X][v] for X in g[v]],max=1) for v in g if v!=x and v!=y] File "mip.pyx", line 670, in sage.numerical.mip.MixedIntegerLinearProgram.add_constraint (sage/numerical/mip.c:5462) AttributeError: 'list' object has no attribute 'f' ********************************************************************** 1 items had failures: 1 of 4 in __main__.example_69 ***Test Failed*** 1 failures. For whitespace errors, see the file /Users/wdj/.sage//tmp/.doctest_generic_graph.py [29.4 s] ---------------------------------------------------------------------- The following tests failed: sage -t --optional "devel/sage/sage/graphs/generic_graph.py"
Is this a related failure?
comment:18 Changed 9 years ago by
No, it is not. This comes from something internal to MixedIntegerLinearProgram?, which has been corrected somewhere already... It could be #7311 though I am not sure. The point is that I have seen it for some time, and I stopped worrying a while ago. So this is bound to mean I already fixed it :-)
Nathann
comment:19 Changed 9 years ago by
- Status changed from needs_review to needs_work
Although I am not really competent in this area, I am changing this back to needs work since it does not have an example where the graph is weighted (other than all weights being equal to 1). Since this is a parameter option, it really should be tested. It would be nice to have an example where there is a choice of circuits (eg, with the hypercube graph) but only one which is cheapest.
comment:20 Changed 9 years ago by
- Status changed from needs_work to needs_review
With a brand new example ! ;-)
Nathann
comment:21 Changed 9 years ago by
This had the same (unrelated?) failures as before. The docstrings look much better now and the added functionalit is very nice!
It looks good to me but I prefer to let Jason Grout have the final say.
comment:22 Changed 9 years ago by
A couple of somewhat picky notes from just reading through the code:
- "traveling" is spelled with one 'l' in American English. See English Dictionary, "Derivatives, as travelled, -er, -ing, etc. are usually spelt with ll in Gr. Britain, with single l in America." With no offense to those across the Great Pond, it seems that we've standardized on American English for spelling.
- I don't think there is a need for the "is_hamiltonian" note in the TSP function.
- If these functions require an optional package, it should probably mention that as a note or warning in the documentation.
I'll try applying this patch soon to have a more thorough review. It looks really nice!
comment:23 Changed 9 years ago by
This new patch is now written in american, even though it hurts (I so love english people). I also removed the comment from the TSP function.
Concerning the note in the docstrings about optional packages, well.. My opinion is that we may consider LP to be optional, but that many recent patches added very useful functionalities requiring the user to install at least one LP solver, so to be honest these packages, one can less and less do without these packages, which are to be named "optional" because of license incompatibilities...
If you feel it is really necessary, though, it looks like we should "normalize" the Graph class and add comments to each function which uses LP or depends on it :-)
Nathann
comment:24 follow-up: ↓ 25 Changed 9 years ago by
I added a few lines to support multigraphs.... Before this, the problem failed if you added to each edge a paralell one, while it should only help ;-)
Nathann
Changed 9 years ago by
comment:25 in reply to: ↑ 24 Changed 9 years ago by
Replying to ncohen:
I added a few lines to support multigraphs.... Before this, the problem failed if you added to each edge a paralell one, while it should only help ;-)
Nathann
This new patch passes the same tests as before.
Again, I leave it to Jason to give the final okay.
comment:26 Changed 9 years ago by
- Owner changed from jason to ncohen
For an explanation of the Linear Program used to solve this problem, see the LP chapter from : http://code.google.com/p/graph-theory-algorithms-book/
Nathann
comment:27 Changed 9 years ago by
- Status changed from needs_review to positive_review
I retested this on 4.4.2.a0. Looks good to me.
comment:28 Changed 9 years ago by
- Description modified (diff)
- Reviewers set to Jason Grout, David Joyner, Minh Van Nguyen
- Status changed from positive_review to needs_work
I got a hunk failure when applying the patch on top of #8364 and #8166 in that order:
[mvngu@sage sage-main]$ hg tip changeset: 14321:1451c00a8d44 tag: tip user: Minh Van Nguyen <nguyenminh2@gmail.com> date: Wed May 19 00:55:29 2010 -0700 summary: 4.4.2 [mvngu@sage sage-main]$ hg qimport http://trac.sagemath.org/sage_trac/raw-attachment/ticket/8364/trac_8364.patch && hg qpush adding trac_8364.patch to series file applying trac_8364.patch now at: trac_8364.patch [mvngu@sage sage-main]$ hg qimport http://trac.sagemath.org/sage_trac/raw-attachment/ticket/8364/trac_8364-reviewer.patch && hg qpush adding trac_8364-reviewer.patch to series file applying trac_8364-reviewer.patch now at: trac_8364-reviewer.patch [mvngu@sage sage-main]$ hg qimport http://trac.sagemath.org/sage_trac/raw-attachment/ticket/8166/trac_8166-rebase.patch && hg qpush adding trac_8166-rebase.patch to series file applying trac_8166-rebase.patch now at: trac_8166-rebase.patch [mvngu@sage sage-main]$ hg qimport http://trac.sagemath.org/sage_trac/raw-attachment/ticket/2203/trac_2203.patch && hg qpush adding trac_2203.patch to series file applying trac_2203.patch patching file sage/graphs/generic_graph.py Hunk #1 FAILED at 3637 1 out of 2 hunks FAILED -- saving rejects to file sage/graphs/generic_graph.py.rej patch failed, unable to continue (try -v) patch failed, rejects left in working dir errors during apply, please fix and refresh trac_2203.patch
I have rebased ncohen's patch on top of #8364 and #8166. See the ticket description for instructions on how to apply the rebased patch. Someone other than myself needs to have a look through my rebase patch to make sure I didn't mess up anything. Because of this, I'm putting the ticket in "needs review". The code introduced by ncohen's patch (equivalently the code in the rebased patch) needs some clean-ups, but I won't do that here.
comment:29 Changed 9 years ago by
- Status changed from needs_work to needs_review
comment:30 Changed 9 years ago by
Is this rebase to work on top of 4.4.2? I can't even get the first patch to apply. I assume only the last patch of 8364 is to be applied first. If not, please list exactly which patches and in what order to test this.
comment:31 Changed 9 years ago by
- Status changed from needs_review to positive_review
It applies nicely on my 4.4.2 using Minh's commnds.. I did not even know hg accepted urls instead of files ;-)
Positive review !
Nathann
comment:32 Changed 9 years ago by
- Merged in set to sage-4.4.4.alpha0
- Resolution set to fixed
- Status changed from positive_review to closed
I take that back, concorde is *not* GPL. From the readme:
in the ANSI C programming language and it is available for academic research use; for other uses, contact bico@… for licensing options.
So maybe it could be a optional package unless we can get a GPL version.