TSP solver without triangle inequality
I am interested in solving the TSP for (small) grid graphs. Any sort of library will do for me, but this seems to be harder than expected. I tried a couple of solvers I found out there (including concorde), but they all seem to have problems when the triangle inequality does not hold.

For instance, I would like the solver to output the tour (0, 1, 2, 1, 4, 3) for the graph (with unit edge weights) below:

    0-1-2
    | |
    3-4

In this particular case, I told concorde that the edge (2, 4) had weight 1000 and concorde promptly produced the tour (0, 1, 2, 4, 3) of cost 1004. This is clearly not what I am looking for.

Ideally, there would be some simple (possibly brute force) implementation in Java, but anything which works will actually do. Can anyone point me to some code or do I really have to go an implement this myself?

Edit: also, it is important that I get an exact solution, not some approximation.

TSP solver without triangle inequality
===

I am interested in solving the TSP for (small) grid graphs. Any sort of library will do for me, but this seems to be harder than expected. I tried a couple of solvers I found out there (including concorde), but they all seem to have problems when the triangle inequality does not hold.

For instance, I would like the solver to output the tour (0, 1, 2, 1, 4, 3) for the graph (with unit edge weights) below:

    0-1-2
    | |
    3-4

In this particular case, I told concorde that the edge (2, 4) had weight 1000 and concorde promptly produced the tour (0, 1, 2, 4, 3) of cost 1004. This is clearly not what I am looking for.

Ideally, there would be some simple (possibly brute force) implementation in Java, but anything which works will actually do. Can anyone point me to some code or do I really have to go an implement this myself?

Edit: also, it is important that I get an exact solution, not some approximation.
