This reply was supposed to go over the mailing list.

br,

Joris

---------- Forwarded message ----------
From: Joris Kinable <deus87@gmail.com>
Date: Wed, Apr 23, 2014 at 1:38 PM
Subject: Re: [jgrapht-users] Bug in HamiltonianCycle
To: Simon Heinen <simon.heinen@gmail.com>


Hi Simon,

In your post you have several questions.

Q1: Is there also a Hamiltonian cycle algorithm implementation which produces an exact solution?
No there is not. HC is an NP-hard problem, meaning that it is very difficult to solve. There are entire libraries dedicated to solving just this problem, which is way beyond jgrapht. What you might want to do is to look into Concorde (http://www.math.uwaterloo.ca/tsp/concorde.html) which currently is the fastest solver. It can solve the HC problem to optimality for very large instances in reasonable time.

Q2: Is there an implementation which yields better but not necessary optimal solutions?
Currently not, but I've checked the implementation and there are fairly easy ways to improve the quality of the solutions with a reasonable increase in runtime. What you could do is take the solution produced by the Hamiltonian cycle implementation and run a local search on top of it, thereby performing a certain number of so-called 2-opt moves (http://en.wikipedia.org/wiki/2-opt). This procedure is known to give good results in general (but obviously doesn't guarantee to find the optimal solution).
What I would do is the following:
1. Use HamiltonianCycle.java to get a initial solution
2. Given the tour, find the best 2-opt move out of all possible 2-opt moves. If this move improves the solution, perform the move. If not, stop.
This is very easy and fast to implement, especially if you are dealing with complete graphs. This would also make a nice extension of the HamiltonianCycle class implementation :). 


Q3: Is there a bug in the code? That's difficult to say from your example as there are so many data points. From the looks of it, the solution seems to satisfy the definition of a hamiltonian cycle:
-every vertex has an incoming and an outgoing edge
-there are no subtours e.g. it's one tour, not a collection of several tours.
Check whether your solution meets these criteria.
Due to the greedy nature of the algorithm the resulting tour may however be very far away from any optimal solution. In the example you showed us, performing 2-opt moves will most likely provide you with the optimal solution.
Note: the HamiltonianCycle class requires that your graph is complete (check this!), see comment below. Also, to guarantee a 2-approximation, all edge weights must satisfy the triangle inequality.


Note to developers:
We should update the java doc of HamiltonianCycle.java. In the code I found this:
     * This method will return an approximate minimal traveling salesman tour
     * (hamiltonian cycle). This algorithm requires that the graph be complete
     * and the triangle inequality exists (if x,y,z are vertices then
     * d(x,y)+d(y,z)<d(x,z) for all x,y,z) then this algorithm will guarantee a
     * hamiltonian cycle such that the total weight of the cycle is less than or
     * equal to double the total weight of the optimal hamiltonian cycle. The
     * optimal solution is NP-complete, so this is a decent approximation that
     * runs in polynomial time.
This should be mentioned in the javadoc as well, preferably at the beginning. If I have a bit of spare time in the weekend I'll write a brief description for the algorithm used in the HamiltonianCycle class. There should also be a note on the runtime complexity. 

br,

Joris


On Tue, Apr 22, 2014 at 4:51 AM, Simon Heinen <simon.heinen@gmail.com> wrote:
Hello jGraphT users,
I think I found a bug in the HamiltonianCycle algorithm. I wrote it
down in detail here:

https://github.com/jgrapht/jgrapht/issues/83

If someone has an idea why this happens, it would be great to get some
feedback about this.

Thanks,
Simon

------------------------------------------------------------------------------
Start Your Social Network Today - Download eXo Platform
Build your Enterprise Intranet with eXo Platform Software
Java Based Open Source Intranet - Social, Extensible, Cloud Ready
Get Started Now And Turn Your Intranet Into A Collaboration Platform
http://p.sf.net/sfu/ExoPlatform
_______________________________________________
jgrapht-users mailing list
jgrapht-users@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/jgrapht-users