TSP with python-mip, running time?

[Paul Cezanne]

I'm running a 53 node TSP problem using the sample code on https://docs.python-mip.com/en/latest/examples.html

It's been running for 16 hours now, MacBook Pro, 2.8 GHz Quad-Core Intel Core i7. It appears to be using only one core.

But 16 hours?  The best solution now is still 6% my "by hand" solution, so I know it is getting better. Is this an expected run time?

[Luciano Rigolin de Almeida]

Hi.

Are you using the standard solver (CBC)? Have you tried with gurobi?

Att,

Luciano

[Paul Cezanne]

Standard solver, not gorubi. I do not have a gorubi license. (61 hours running so far...)

[Wit Jakuczun]

Check code from this section - https://docs.python-mip.com/en/latest/custom.html MIP is not the best approach to TSP problem but lazy constraints and initial solutions and cuts help a lot. 

Best regards

--
[ Wit Jakuczun  http://www.linkedin.com/in/jakuczunwit  ]

--
You received this message because you are subscribed to the Google Groups "Python-MIP" group.
To unsubscribe from this group and stop receiving emails from it, send an email to python-mip+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/python-mip/64c95034-e5c6-49b6-a082-2e9d8c2e4ce0n%40googlegroups.com.

[Paul Cezanne]

Thanks, I’ll check that out!

[Luciano Rigolin de Almeida]

You can use the academic license as a test.

[Paul Cezanne]

> On Jan 25, 2021, at 7:06 AM, Wit Jakuczun <wit.ja...@gmail.com> wrote:
>

> Check code from this section - https://docs.python-mip.com/en/latest/custom.html MIP is not the best approach to TSP problem but lazy constraints and initial solutions and cuts help a lot.
>
> Best regards
> --
> [ Wit Jakuczun http://www.linkedin.com/in/jakuczunwit ]
>

Thank you Wit!

I was able to generate the bi-directional distance matrix from my real-world problem and successfully got that data into tsp_cuts.py and ran it. With 53 nodes my problem only took 12 seconds to find an optimal solution. This is wonderful.

I know the distance, but I can find the solutinon. I drill down through the model variable in the python, looking for an array of that shows the order of the 53 nodes and it doesn’t seem to be there. It has to be, but I’m not seeing it.

What am I missing? How can I extract the path, not just the distance, from the TSP solver?

Thanks!

[Wit Jakuczun]

The path is encoded in matrix x. This TSP version is not directed so to have the order you have: a) select one node as starting, b) walk through matrix x and check which connection is selected to find a successor. You could also investigate variable y which ensures nodes are in order.

I hope that helps.

Best regards

--
[ Wit Jakuczun  http://www.linkedin.com/in/jakuczunwit  ]

[Paul Cezanne]

Thanks for the quick response. I ran it again with n=5, not n=53 and it x is far easier to understand. I’ll code up a solution after work tonight.

Thanks again!

[Wit Jakuczun]

Good luck! :)

--
[ Wit Jakuczun  http://www.linkedin.com/in/jakuczunwit  ]

[Paul Cezanne]

> On Feb 17, 2021, at 8:01 AM, Paul Cezanne <notthedead...@gmail.com> wrote:
>
> Thanks for the quick response. I ran it again with n=5, not n=53 and it x is far easier to understand. I’ll code up a solution after work tonight.
>
> Thanks again!

hmm, big failure. It was easy to code up to find the solution, but the solution is garbage.

for nodeIndex, node in enumerate(x):
for nextNodeIndex, nextNode in enumerate(node):
if nextNode.x != 0:
print(coords[nextNodeIndex])

coords is a list that has the latitude/longitude of the map locations. When plotted in google maps I get this.

http://www.notthepainter.com/wp-content/uploads/2021/02/badMap.png

That’s clearly not correct. I need to debug this some, but walking the list x seemed for simple. Inspection in the debugger showed that x was a list of n items (where n was 53 in my case since I had 53 locations) and each item in that list had n items, one of which had a property x that was 1, all the others were zero. I guess I need to work with a smaller data set and do it all by hand.

[Paul Cezanne]

> On Feb 17, 2021, at 5:59 PM, Paul Cezanne <notthedead...@gmail.com> wrote:
>
>
>
>> On Feb 17, 2021, at 8:01 AM, Paul Cezanne <notthedead...@gmail.com> wrote:
>>
>> Thanks for the quick response. I ran it again with n=5, not n=53 and it x is far easier to understand. I’ll code up a solution after work tonight.
>>
>> Thanks again!
>
> hmm, big failure. It was easy to code up to find the solution, but the solution is garbage.
>
> for nodeIndex, node in enumerate(x):
> for nextNodeIndex, nextNode in enumerate(node):
> if nextNode.x != 0:
> print(coords[nextNodeIndex])

yeah, this isn’t the rigth way to walk it. I’m debugging now… might not finish tonight though.

[Paul Cezanne]

hmm, big failure. It was easy to code up to find the solution, but the solution is garbage.

for nodeIndex, node in enumerate(x):
for nextNodeIndex, nextNode in enumerate(node):
if nextNode.x != 0:
print(coords[nextNodeIndex])

yeah, this isn’t the rigth way to walk it. I’m debugging now… might not finish tonight though.

I’m certainly confused. I’m not able to find a way to decode the path by looking at the x property. For example, if you use this an input matrix:

p = [
   [0, 21082, 65713, 88747, 94863, 94812, 118470, 85507, 54992, 52002, ],
   [21082, 0, 47097, 70131, 76247, 76196, 92801, 66891, 36376, 35638, ],
   [65713, 47097, 0, 39508, 45624, 45611, 69268, 62966, 49637, 53121, ],
   [88747, 70131, 39508, 0, 7789, 21907, 43901, 48506, 69068, 72552, ],
   [94863, 76247, 45624, 7789, 0, 25477, 36837, 59444, 75185, 78668, ],
   [94812, 76196, 45611, 21907, 25477, 0, 24386, 26661, 55051, 62567, ],
   [118470, 92801, 69268, 43901, 36837, 24386, 0, 38228, 68479, 73749, ],
   [85507, 66891, 62966, 48506, 59444, 26661, 38228, 0, 37080, 46277, ],
   [54992, 36376, 49637, 69068, 75185, 55051, 68479, 37080, 0, 7849, ],
   [52002, 35638, 53121, 72552, 78668, 62567, 73749, 46277, 7849, 0, ],
]

You get a solution of:

status: OptimizationStatus.OPTIMAL route length 303767

The x matrix is much easier to understand visually. 

I’ve outlined all 1.0 values in orange. I’ve been interpreting it by starting at row 0 (Ashuelot Bridge is the name of the location). The 1.0 value is in column 5, so I go to column and say that that’s the next node on my route, which is Berment Bridge. Berment has it’s 1.0 in column 4 so the next location is Railroad Bridge and so on.

This is not an optimal path, if you graph the 9 on a real map it is clearly wrong. But lets use our distances.

426,705 is the sum which is not the same as the 303767 we had output by the python.

So my method of interpreting the x value is clearly incorrect.

Here’s my python to print out the order as shown above.

def nextNodeIndex( node ):
"Returns the index of the first element in the node that has x != 0"
for index, value in enumerate (node):
if value.x > 0:
return index
return index

# the final path is in variable x, we need to walk x once, looking for
# the next node and walk it to see the subsequent node
solutionNodes = [0]
nextNode = 0

for nodeIndex in range(0, n-1):
    nextNode = nextNodeIndex(x[nextNode])
    solutionNodes.append(nextNode)
# the start node is also the end node
solutionNodes.append(0)

I also tried look at the y variable, but that isn’t making any sense to me. I see a single array of 10 elements, all of which name a node, but one of the nodes appears twice, so I’m not at all sure how to interpret that.

So my question remains, once I have a solution, how can I determine the path that makes up that solution?

[Paul Cezanne]

> On Feb 26, 2021, at 5:19 PM, Paul Cezanne <notthedead...@gmail.com> wrote:
>
>
> So my question remains, once I have a solution, how can I determine the path that makes up that solution?

Wow, there is a write method on model. If the filename ends in .sol it writes a solution!

Feasible solution - objective 0.0
0 var(5) 1.0 109667.0
1 var(10) 1.0 29814.0
2 var(28) 1.0 15162.0
3 var(37) 1.0 4582.0
4 var(46) 1.0 28833.0
5 var(54) 1.0 72.0
6 var(63) 1.0 37382.0
7 var(72) 1.0 27993.0
8 var(89) 1.0 3080.0
9 var(91) 1.0 47182.0
10 var(102) 3.0 0.0
11 var(103) 5.0 0.0
12 var(104) 7.0 0.0
13 var(105) 8.0 0.0
14 var(106) 6.0 0.0
15 var(107) 4.0 0.0
16 var(108) 2.0 0.0
17 var(109) 1.0 0.0

Yikes. I didn’t expect 18 items. But the first nine are interesting and they do sum to the same number that is printed out, but that’s really confusing since one of them is 72.0 and I don’t have any distances that are 72.0!

But let me see which nodes var(5), 10, 28 etc refer to.

[Paul Cezanne]

The answer is to give the nodes names when creating them. In my case this is done with the line

x = [[model.add_var(var_type=BINARY, name=coords[i]) for j in V] for i in V]

coords is an array of the lat/long of each item. This is the correct solution!

[Paul Cezanne]

> On Feb 26, 2021, at 6:09 PM, Paul Cezanne <notthedead...@gmail.com> wrote:
>
> The answer is to give the nodes names when creating them. In my case this is done with the line

and that’s not working when n is large, more debugging ahead...

[Paul Cezanne]

I’m still at a loss here. It isn’t clear how to walk through matrix x looking for the next connection, I’ve been looking for patterns in the data structure but I don’t see anything that would indicate what the next node would be.

I even changed how x was generated, adding the “name” parameter so I could have human readable names, not just “var(0)” and “var(1)” but this doesn’t seem to work either.

x = [[model.add_var(var_type=BINARY, name=places[i] + "--" + places[j]) for j in V] for i in V]

(I have the human readable place names in a list called “places”)

This gives me a .sol file like this:

Ashuelot Bridge, Winchester--Prentiss Bridge, Langdon : 1.0
County Bridge, Hancock--Sawyer's Crossing, Swanzey : 1.0
Railroad Bridge, Hopkinton--Bement Bridge, Bradford : 1.0
Mcdermott Bridge, Langdon--Corbin Bridge, Newport : 1.0
Rowell's Bridge, Hopkinton--County Bridge, Hancock : 1.0
Bement Bridge, Bradford--Rowell's Bridge, Hopkinton : 1.0
Corbin Bridge, Newport--Cilleyville Bridge, Andover : 1.0
Cilleyville Bridge, Andover--Railroad Bridge, Hopkinton : 1.0
Sawyer's Crossing, Swanzey--Ashuelot Bridge, Winchester : 1.0
Prentiss Bridge, Langdon--Mcdermott Bridge, Langdon : 1.0

Now the curious thing is, I can read this and find the path. For example, if you start at "Ashuelot Bridge, Winchester” and travel to "Prentiss Bridge, Langdon” then you have to find the line that has Prentiss, which is the last one, and extract “Mcdermott”, then find “Mcdermott’s” line which brings you to Corbin.

So clearly the solution is there, it just isn’t apparent how to extract that, especially since, without my modification above, to be able to map var(123) to a node pair. The .sol file has the solution but it is jumbled.

> On Feb 17, 2021, at 7:49 AM, Wit Jakuczun <wit.ja...@gmail.com> wrote:
>
> The path is encoded in matrix x. This TSP version is not directed so to have the order you have: a) select one node as starting, b) walk through matrix x and check which connection is selected to find a successor. You could also investigate variable y which ensures nodes are in order.
>
> I hope that helps.
>
> Best regards
> --
> [ Wit Jakuczun http://www.linkedin.com/in/jakuczunwit ]
>
>

[Paul Cezanne]

mmmm, it does seem that each row in the matrix x has a variable named x which is 1.0 if that is part of the solution. But I’m still going to need to do some work here.

[Paul Cezanne]

> On Mar 7, 2021, at 4:37 PM, Paul Cezanne <notthedead...@gmail.com> wrote:
>
>
>

> Now the curious thing is, I can read this and find the path. For example, if you start at "Ashuelot Bridge, Winchester” and travel to "Prentiss Bridge, Langdon” then you have to find the line that has Prentiss, which is the last one, and extract “Mcdermott”, then find “Mcdermott’s” line which brings you to Corbin.
>
> So clearly the solution is there, it just isn’t apparent how to extract that, especially since, without my modification above, to be able to map var(123) to a node pair. The .sol file has the solution but it is jumbled.

I’m managed to extract the solution, both from .sol file and the model.vars property. This code will do it

solutionIndices = []
for v in model.vars:
if abs(v.x) > 1e-6: # only printing non-zeros
solutionIndices.append(v.idx % n)
print('{} : {}-{}'.format(v.name, v.idx % n, int(v.idx / n)))

print('')

fromNode = 0
for i in list(range(n)):
toNode = solutionIndices[fromNode]
print(places[toNode])
fromNode = toNode

print(‘')

This gives an identical result to the answer in the .sol file.

The problem is is that the answer is wrong, it is demonstrably not the shortest path. I don’t know how to proceed here.