Travelling salesman variation in python

[Erlend Andreas Garberg]

Hi!

I'm trying to code a implementation of a variation of the travelling
salesman problem.

The problem is the following.

I have X nodes.
Each node has a number assosiated with each of the other nodes.

The problem is then:
Construct a ring of the nodes so that the sum of the numbers is the
highest possible.

Example:
Nodes:
A with numbers B->1200, C->2000
B with numbers A->3000, C->4000
C with numbers A->9000, B->5000

The optimal ring is in this case can f.ex. be:
A->1200->B->4000->C->9000->A with sum 14200.

I have implemented this in python in the following way:

hash is a dictionary with node-name as key and node-object as value.
Each node-object has a dictionary speeds with node-name as key and a
number as value. this dict stores the numbers associated with the other
nodes.

-------------------------------------------------------------------
# method xcombinations
def xcombinations(items, n):
if n==0: yield []
else:
for i in xrange(len(items)):
for cc in xcombinations(items[:i]+items[i+1:],n-1):
yield [items]+cc

# help function
func = lambda x,y: int(hash[x].speeds[y])


# code starts here:
bestcomb = []
bestspeed = 0

for comb in xcombinations(hash.keys(),len(hash)):
speed = sum(map(func,comb,comb[1:] + comb[:1]))
if speed > bestspeed:
bestcomb = comb
bestspeed = speed

-----------------------------------------------------------------

My implementation generate all combinations, and check which gives the
highest result.

My problem is that when the number of nodes is higher than 8, the
algorithm slows to a crawl (because of O(n!) complexity). I wonder if
there is some way I can optimize my algorithm to make it run faster?
Currently it takes 20 seconds to compute the best combination with 9
nodes on my hardware.


I would appreciate some comments on this

 

[Josiah Carlson]

I would appreciate some comments on this

Look at current TSP algorithms, and exchange their minimization rutines
for a maximization rutine. TSP is an NP-hard problem, which means that
there is no currently known algorithm for solving it in polynomial time.
You can approximate it or do a search on the solution space, but
solving it requires searching basically all of the solution space.

- Josiah

 

[Erlend Andreas Garberg]

Look at current TSP algorithms, and exchange their minimization rutines
for a maximization rutine. TSP is an NP-hard problem, which means that
there is no currently known algorithm for solving it in polynomial time.
You can approximate it or do a search on the solution space, but
solving it requires searching basically all of the solution space.

- Josiah

An approximate solution would be good enough, do you have any
suggestions about how do do that?

 

[Paul Rubin]

An approximate solution would be good enough, do you have any
suggestions about how do do that?

Is it just an arbitrary graph? Most TSP approximation algorithms
depend e.g. on the triangle inequality, i.e. d(A,C) <= d(A,B) + d(B,C).

Papadimitriou and Stieglitz, "Combinatorial Optimization" was a
standard textbook on this stuff, though is pretty old by now.

 

[Erlend Andreas Garberg]

Is it just an arbitrary graph? Most TSP approximation algorithms
depend e.g. on the triangle inequality, i.e. d(A,C) <= d(A,B) + d(B,C).

Papadimitriou and Stieglitz, "Combinatorial Optimization" was a
standard textbook on this stuff, though is pretty old by now.

The graph is arbitrary, yes..

 

[Günter Jantzen]

Hello Erlend,

in my opinion its not a TSP. In TSP problems a minimum is searched, you
search the maximum
And TSP is usually formulated for undirected graphs. So (for me) its not so
clear if the problem is NP

Did you think about trying a greedy algorithm. Start at some point and go
always the way with the highest value and eliminate the previous note

If you want better results, try it with more combinations. For example
choose the three highest values from every node and follow this ways if
possible

Use backtracking with recursive calls
(explained in many textbooks about discrete mathematics. Typical example -
the 8 queens problem)

Of course I have no idea if this approch will be helpful

Günter

 

[Jeff Epler]

Can't TSP be converted to your problem?

If you have TSP with distance(Xi, Xj)=Dij, then convert it to your
problem by letting distance(X'i, X'j)=distance(X'j, X'i)=-Dij.
or if only positive weights are allowed then use max(D)-Dij.

Jeff

 

[Josiah Carlson]

An approximate solution would be good enough, do you have any

suggestions about how do do that?

One approximate solution to the TSP is the bitonic TSP. That is, start
at the leftmost point, find a path to the rightmost point, then find a
return path to the leftmost point.

Search for 'optimal bitonic tsp' in google, the second entry will have
pseudocode for the algorithm. I've personally converted it to Python
for other uses, but I'll leave it as an exercise for you.

You can convert it into your 'maximum' by changing the line:
if q < b[j - 1, j] then
to:
if q > b[j - 1, j] then


- Josiah

 

[Nick Craig-Wood]

My problem is that when the number of nodes is higher than 8, the
algorithm slows to a crawl (because of O(n!) complexity). I wonder if
there is some way I can optimize my algorithm to make it run faster?
Currently it takes 20 seconds to compute the best combination with 9
nodes on my hardware.

I had to solve exactly this problem when I was at University (many
moons ago now ;-)

I used Simulated Annealing - have a search for the term and you'll see
plenty of references. Its good at finding a (local) minimum.

Just be glad you don't have to write it in Fortran like I did!

 

[Erlend Andreas Garberg]

One approximate solution to the TSP is the bitonic TSP. That is, start
at the leftmost point, find a path to the rightmost point, then find a
return path to the leftmost point.

The problem is that all nodes are connected to all the other nodes, and
the weights are in essence random.. So it won't be possible to find
leftmost/rightmost point.

 

[Peter Maas]

I used Simulated Annealing - have a search for the term and you'll see
plenty of references. Its good at finding a (local) minimum.

I used to think that Simulated Annealing avoids local traps and
is good at finding a global minimum, at least with a certain
probability that depends on some temperature function. Am I wrong?

Mit freundlichen Gruessen,

Peter Maas

 

[Diez B. Roggisch]

You could go for local search. First, create a randow tour. Then select a
neighborhood. Find the local minimum for that neighborhood. Do this as
often as you like.

A typical neighborhood for tsps are four nodes where two of them are
adjacent in your tour. Then exchange the nodes so that they still form a
tours. If that has less costs, keep it that way.

--n1--n2--
--n3--n4--

becomes

--n1\/n2--
--n3/\n4--

 

[Peter Hansen]

An approximate solution would be good enough, do you have any
suggestions about how do do that?

I haven't tried it for such a case, but have you considered a
genetic algorithm approach? Since you say an approximate solution
is good enough, I would think a GA could vastly shrink the search
space that has to be covered to get "close", assuming that data is
not such that hidden somewhere in it is a single link which has
an associated number that is vastly higher than the others. (That
would tend to make the GA search even worse than a brute force
approach.)

-Peter

 

[Duncan Smith]

I used to think that Simulated Annealing avoids local traps and
is good at finding a global minimum, at least with a certain
probability that depends on some temperature function. Am I wrong?

Mit freundlichen Gruessen,

Peter Maas

No, you're not. I think simulated annealing is a decent candidate for this
problem. The difficulty (in my experience) is in finding decent parameters
for the cooling schedule, so you can find good solutions in reasonable time.

Duncan

 

[Mitja]

You could go for local search. First, create a randow tour. Then select a
neighborhood. Find the local minimum for that neighborhood. Do this as
often as you like.

A typical neighborhood for tsps are four nodes where two of them are
adjacent in your tour. Then exchange the nodes so that they still form a
tours. If that has less costs, keep it that way.

--n1--n2--
--n3--n4--

becomes

--n1\/n2--
--n3/\n4--

This is more or less just one of the things you'd do with simulated
annealing. And with such a "randomized" problem, this is certainly the one
and only way to go. If there are no rules defining the structure of the
graph, you can't write an optimized code which takes these rules into
account. Anyway, SA is what you want. Google for it, use it.

Mitja

 

[Richard Brodie]

No, you're not. I think simulated annealing is a decent candidate for this
problem. The difficulty (in my experience) is in finding decent parameters
for the cooling schedule, so you can find good solutions in reasonable time.

The book, "Numerical Recipes" contains a description of simulating annealing,
giving the travelling salesman problem as an example. Extracts available online.

 

[Nick Craig-Wood]

I used to think that Simulated Annealing avoids local traps and
is good at finding a global minimum, at least with a certain
probability that depends on some temperature function. Am I wrong?

You aren't wrong... It does avoid local traps - that is what the
simulated annealing bit is for - but it isn't guaranteed to find the
global minimum otherwise you'd have solved an NP-complete problem in
polynomial time...

In practice it works extrememly well!

 

[Terry Reedy]

Example:
Nodes:
A with numbers B->1200, C->2000
B with numbers A->3000, C->4000
C with numbers A->9000, B->5000

The optimal ring is in this case can f.ex. be:
A->1200->B->4000->C->9000->A with sum 14200.

I have implemented this in python in the following way:

hash is a dictionary with node-name as key and node-object as value.
Each node-object has a dictionary speeds with node-name as key and a
number as value. this dict stores the numbers associated with the other
nodes.

If you number (0 -- n-1) rather than name the nodes, then you just need a
nodes array and a speed array for each node. That should make your code a
bit simpler and easier to play with. It should also be a bit faster, but a
good approximation algorithm will be **far** more important. There is at
least one book on the TSP.

Terry J. Reedy

 

[David M. Cooke]

You aren't wrong... It does avoid local traps - that is what the
simulated annealing bit is for - but it isn't guaranteed to find the
global minimum otherwise you'd have solved an NP-complete problem in
polynomial time...

With the right cooling schedule simulated annealing *is* guaranteed to
find the global minimum.

Mind you, that cooling schedule is very slow: the temperature of the
n'th step is T_n = T0/log(n). To get to 1% of your initial
temperature, you'll need about 1e10 steps... polynomial time it ain't.

Most SA cooling schedules you'll see use a quench (T_n = T0*a**n for
some a) or a Cauchy distribution (T_n = T0/n) which are faster, but
aren't guaranteed to give you a global minimum.

 

[Josiah Carlson]

The problem is that all nodes are connected to all the other nodes, and

the weights are in essence random.. So it won't be possible to find
leftmost/rightmost point.

Give them arbitrary x,y positions in 2D space. Whenever you see
something like |p1p2|, that is asking the distance between those two
vertices, and you can make that a lookup into your weight table or a
call to your weight function.

If you look at the algorithm, the only thing that sorting the points in
ascending order based on their x location is doing, is breaking up the
problem into the left to right to left. You can use whatever weights
you want, and because of the way the problem is constructed, you're
going to be checking all possible left to right to left paths on your
way, so you'll find the 'optimal' in your case, bitonic TSP.

- Josiah