Opened 8 years ago

Closed 7 years ago

Last modified 7 years ago

#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 jdemeyer)

Hello everybody !!!

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

Apply:

Attachments (2)

trac_10497.patch (16.0 KB) - added by ncohen 8 years ago.
trac_10497-density.patch (2.7 KB) - added by ncohen 8 years ago.

Download all attachments as: .zip

Change History (21)

comment:1 Changed 8 years ago by ncohen

  • Status changed from new to needs_review

Changed 8 years ago by ncohen

comment:2 Changed 8 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 8 years ago by ncohen

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

Thanks !

Nathann

comment:4 Changed 8 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.

Changed 8 years ago by ncohen

comment:5 Changed 8 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 7 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 7 years ago by ncohen

Wouhouuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu !!!!

comment:8 Changed 7 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 7 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 7 years ago by kini

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

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

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

comment:13 Changed 7 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 7 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 7 years ago by kini

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

comment:16 Changed 7 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 7 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 7 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 7 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.