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 mvngu)

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:

  1. #8364
  2. #8166
  3. trac_2203-rebase.patch

Attachments (2)

trac_2203.patch (12.1 KB) - added by ncohen 9 years ago.
trac_2203-rebase.patch (12.1 KB) - added by mvngu 9 years ago.
rebase of previous patch

Download all attachments as: .zip

Change History (34)

comment:1 Changed 11 years ago by jason

I take that back, concorde is *not* GPL. From the readme:

The code is written

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.

comment:2 Changed 11 years ago by jason

  • Summary changed from Integrate concorde in Sage to make an optional package for concorde in Sage

comment:3 Changed 11 years ago by rlm

  • Milestone changed from sage-2.10.2 to sage-wishlist

comment:4 Changed 10 years ago by rlm

  • Owner changed from rlm to jason

comment:5 Changed 10 years ago by jason

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 jason

  • 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 jason

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 ncohen

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 wdj

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 ncohen

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 wdj

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 ncohen

  • 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 ncohen

  • Milestone changed from sage-wishlist to sage-4.3.3

comment:14 Changed 9 years ago by jason

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 ncohen

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 ncohen

( ... after some email ... )

Ok, ok, I got it !! Here is the new version of this patch ! ;-)

Nathann

comment:17 Changed 9 years ago by wdj

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 ncohen

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 wdj

  • 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 ncohen

  • Status changed from needs_work to needs_review

With a brand new example ! ;-)

Nathann

comment:21 Changed 9 years ago by wdj

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 jason

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 ncohen

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: Changed 9 years ago by 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

Changed 9 years ago by ncohen

comment:25 in reply to: ↑ 24 Changed 9 years ago by wdj

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 ncohen

  • 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 wdj

  • Status changed from needs_review to positive_review

I retested this on 4.4.2.a0. Looks good to me.

Changed 9 years ago by mvngu

rebase of previous patch

comment:28 Changed 9 years ago by mvngu

  • Authors set to Nathann Cohen
  • 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 mvngu

  • Status changed from needs_work to needs_review

comment:30 Changed 9 years ago by wdj

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 ncohen

  • 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 mhansen

  • Merged in set to sage-4.4.4.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.