Getting a lot of crashes or fatal errors running or-tools on reasonably simple problems? Also very slow?
902 views
Skip to first unread message
Nick Talbot
Jan 18, 2016, 7:13:16 AM1/18/16
to or-tools-discuss
Hi all,
I'm using or-tools so solve a TSP problem of around 35 locations, with just over 150 'edges', i.e. the mesh of links between the 35 locations is limited to 150 specific links, usually the nearest neighbours, with calculated links from the depot directly to each other location (so about 115 inter-location links plus 35 links from depot to locations). All non-defined links are forbidden.
This appears to be about the limit of locations that or-tools can solve in a reasonable time, with a solution taking about 2 minutes to produce on a fast machine. 34 locations is considerably quicker, e.g. 20 seconds, and 36 locations appears unsolvable.
I though or-tools could compute TSP results in the thousands of nodes? This isn't my experience so far.
Also, the or-tools engine seems quite brittle, I often get crashes or failures, which if then run again with the same data pass ok. I keep getting either:
java(28609,0x700000d3b000) malloc: *** error for object 0x7feb438c89d0: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
Abort trap: 6
or:
#
# A fatal error has been detected by the Java Runtime Environment:
#
# SIGSEGV (0xb) at pc=0x000000011c848df3, pid=32057, tid=14339
#
# JRE version: Java(TM) SE Runtime Environment (8.0_51-b16) (build 1.8.0_51-b16)
# Java VM: Java HotSpot(TM) 64-Bit Server VM (25.51-b03 mixed mode bsd-amd64 compressed oops)
# Problematic frame:
# C [libjniortools3719024839913606973.jnilib+0x56df3] _ZN19operations_research12RoutingModelD2Ev+0x23
#
# Failed to write core dump. Core dumps have been disabled. To enable core dumping, try "ulimit -c unlimited" before starting Java again
#
# An error report file with more information is saved as:
# /Users/nick/Documents/Development/Backbone_git/tspServer2/hs_err_pid32057.log
#
# If you would like to submit a bug report, please visit:
# The crash happened outside the Java Virtual Machine in native code.
# See problematic frame for where to report the bug.
#
Abort trap: 6
I can post the model if it helps, but it the cost calculator basically produces a value for the valid links, and 0 for anything else. Missing links are removed from the model.
I'm using either the default Heuristic or ROUTING_GUIDED_LOCAL_SEARCH, and first solution ROUTING_PATH_CHEAPEST_ARC
Does anyone have any tips how to speed up the results and / or increase location capacity into the hundreds or thousands, or shed any light on the occasional crashes?
Many thanks!
Nick Talbot
Vincent Furnon
Jan 18, 2016, 7:24:32 AM1/18/16
to or-tools...@googlegroups.com
Concerning the crashes, I wouldn't be surprised if the callbacks (such as the cost callbacks) you pass to the model get garbage-collected by Java during the search; keep a global reference to them.
Java will also be slower than native code (C++) due to the cross-language callbacks, however your running times are a bit surprising.
--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
Nick Talbot
Jan 18, 2016, 8:31:21 AM1/18/16
to or-tools-discuss
Hi Vincent, thanks for the reply!
Forbidden paths are removed by calling the .removeValue() function on the IntPtr nodes as appropriate.
I realise that having removed paths makes the route problem and solution constrained by definition, is or-tools better possibly at solving totally unconstrained problems? Would be it be better to return a very high cost for missing links rather than explicitly removing them?
Thanks
Nick
Vincent Furnon
Jan 18, 2016, 9:11:03 AM1/18/16
to or-tools...@googlegroups.com
On Mon, Jan 18, 2016 at 5:31 AM, Nick Talbot <solu...@magichat.biz> wrote:
Hi Vincent, thanks for the reply!The Cost callbacks etc are implemented as Java inherited classes of the NodeEvaluator2 class, and passed to the routing.setCost(costs) function. The parameter passed is also already kept referenced in a separate variable in the Java code, so I'm not sure if GC is the problem. Can you elaborate on what the C++ crash points to?
I can only speculate at this point since I don't have enough information from your error message. It clearly seems there's a memory corruption issue due to the java/C++ mix.
In any case can you share the code of your cost callback class ?
Forbidden paths are removed by calling the .removeValue() function on the IntPtr nodes as appropriate.I realise that having removed paths makes the route problem and solution constrained by definition, is or-tools better possibly at solving totally unconstrained problems? Would be it be better to return a very high cost for missing links rather than explicitly removing them?
High values might help guided local search a bit, it's worth testing.
Nick Talbot
Jan 18, 2016, 10:18:57 AM1/18/16
to or-tools-discuss
Hi Vincent, the code is in Scala, so there isn't much to show, here you are:
case class Edge(from: Int, to: Int, duration: Int)
case class Request(edges: Seq[Edge], loop: Boolean, vehicles: Int)
class Costs (request: Request) extends NodeEvaluator2 {
def nodes = request.edges.map(_.to).max + 1
override def run(from: Int, to: Int) = {
val matchingEdge = (edge: Edge) => (edge.from == from && edge.to == to) || (edge.from == to && edge.to == from)
request.edges.find(matchingEdge) match {
case Some(edge) => edge.duration
case None => 0
}
}
}
class Handler {
def process(request: Request) = Try {
val costs = new Costs(request)
val problem = new RoutingModel(costs.nodes, request.vehicles)
problem.setCost(costs)
problem.setMetaheuristic(RoutingModel.ROUTING_GUIDED_LOCAL_SEARCH)
problem.setFirstSolutionStrategy(RoutingModel.ROUTING_PATH_CHEAPEST_ARC)
problem.closeModel()
problem.solve()
}
}
I've missed out the code that deleted links, but they just IntPtr.removeValue()
Once we get passed 35 or so locations, the solve() call fails and returns null!
Nick
Vincent Furnon
Jan 19, 2016, 10:22:15 AM1/19/16
to or-tools...@googlegroups.com
I have no idea how Scala works but note that cost callbacks should be really fast (as they are being called pretty intensively) so request.edges.find() could be slowing things down in the Costs class.
Nick Talbot
Jan 22, 2016, 8:10:16 AM1/22/16
to or-tools-discuss
Hi Vincent,
Scala is a statically typed JVM-based language that ultimately compiles down to Java byte-code, the same as vanilla Java. Being typed means that it also makes quick direct calls via vtable lookup the same as C++, versus a slower dynamic dispatch based mechanism (e.g. Groovy, Ruby etc).
request.edges.find() is a simple linear search of an List/Sequence looking for a match based on the supplied condition, i.e. a quick lookup. I would be surprised if this is the cause of any problems.
It's a great pity that these problems are present in the current or-tools implementation. It would appear that or-tools is not currently as mature as other similar offerings, e.g. OptaPlanner.
or-tools currently seems to have stability issues (lots of failures and general protection faults), and also doesn't seem very quick either. I haven't been able to obtain a result of a constrained (via missing links) graph of e.g. 40 locations using or-tools, whereas OptaPlanner can quickly solve problems containing hundreds of nodes/locations.
It looks like I should stick with OptaPlanner for now, and maybe or-tools will achieve similar functionality and performance in the next few years? I must admit I'm quite surprised that a Google-backed project doesn't seem quite as good as competitor offerings!
Many thanks for all your help so far,
Nick
Vincent Furnon
Jan 22, 2016, 8:27:33 AM1/22/16
to or-tools...@googlegroups.com
On Fri, Jan 22, 2016 at 2:10 PM, Nick Talbot <solu...@magichat.biz> wrote:
Hi Vincent,
Scala is a statically typed JVM-based language that ultimately compiles down to Java byte-code, the same as vanilla Java. Being typed means that it also makes quick direct calls via vtable lookup the same as C++, versus a slower dynamic dispatch based mechanism (e.g. Groovy, Ruby etc).request.edges.find() is a simple linear search of an List/Sequence looking for a match based on the supplied condition, i.e. a quick lookup. I would be surprised if this is the cause of any problems.
Linear lookup is not a quick lookup. This can be improved by specifying cache_callbacks=true in RoutingParameters which can be set with SetGlobalParameters.
It's a great pity that these problems are present in the current or-tools implementation. It would appear that or-tools is not currently as mature as other similar offerings, e.g. OptaPlanner.or-tools currently seems to have stability issues (lots of failures and general protection faults), and also doesn't seem very quick either. I haven't been able to obtain a result of a constrained (via missing links) graph of e.g. 40 locations using or-tools, whereas OptaPlanner can quickly solve problems containing hundreds of nodes/locations.
Concerning stability issues, the native C++ code has been pretty intensively tested and is very stable. I think the issues you are encountering come from the cross-language layer.
On the performance side, the solver is being used to solve problems with thousands of nodes with no particular issues (and smaller problems in matter of ms or s).,
So your results are surprising, although my experience is mainly based on using the native C++ api.
Nick Talbot
Jan 22, 2016, 5:10:53 PM1/22/16
to or-tools-discuss
Hi Vincent, again thanks for the reply.
I can certainly believe that there may be a problem in the SWIG /Java translation layer rather than the core C++ code. If it's the case that I can get good results out of or-tools by using a C++ implementation rather than a Java / JVM one, I could certainly go down that road. It's been a good few years since I wrote any serious C++ (!), but I'm happy to do that if it gets the best results.
I have narrowed down a sample set of data, i.e. a specific model example that my Java / Scala implementation using or-tools fails to calculate a TSP route. (I have also successfully used this code and or-tools to solve a similar sized problem, but this particular model is not solved by or-tools).
My example 'problem' test model 170 edges/links between 39 locations (including the start/finish depot location of id 0). The links are treated as two-way symmetric, e.g. if a link is defined one way, it counts in the reverse direction as well. The depot location 0 has links to every other node in the model, but all the other nodes have limited links to other nodes, i.e. all non-depot nodes do not have a links to all other nodes, only a few neighbours.
This 170 edge graph is solved by my current OptaPlanner-based solver in under 2 seconds, but fails to be solved by or-tools. (However, or-tools does solve other similarly sized and configure models).
Do you think this graph below should be solvable by or-tools (using a purely C++ based client) in a short amount of time? (The graph is expressed below as a JSON array of from/to zero-based index edges with associated distance/cost. Only explicitly mentioned links are allowed, all others are forbidden).
JSON below, what do you think?
{
"edges":[
{
"from":0,
"to":1,
"distance":20
},
{
"from":0,
"to":2,
"distance":34
},
{
"from":0,
"to":3,
"distance":68
},
{
"from":0,
"to":4,
"distance":137
},
{
"from":0,
"to":5,
"distance":173
},
{
"from":0,
"to":6,
"distance":170
},
{
"from":0,
"to":7,
"distance":192
},
{
"from":0,
"to":8,
"distance":197
},
{
"from":0,
"to":9,
"distance":241
},
{
"from":0,
"to":10,
"distance":246
},
{
"from":0,
"to":11,
"distance":268
},
{
"from":0,
"to":12,
"distance":238
},
{
"from":1,
"to":2,
"distance":36
},
{
"from":0,
"to":13,
"distance":187
},
{
"from":0,
"to":14,
"distance":218
},
{
"from":0,
"to":15,
"distance":292
},
{
"from":0,
"to":16,
"distance":267
},
{
"from":0,
"to":17,
"distance":284
},
{
"from":0,
"to":18,
"distance":210
},
{
"from":0,
"to":19,
"distance":231
},
{
"from":0,
"to":20,
"distance":209
},
{
"from":0,
"to":21,
"distance":134
},
{
"from":0,
"to":22,
"distance":124
},
{
"from":2,
"to":3,
"distance":33
},
{
"from":0,
"to":23,
"distance":98
},
{
"from":0,
"to":24,
"distance":121
},
{
"from":0,
"to":25,
"distance":177
},
{
"from":0,
"to":26,
"distance":186
},
{
"from":0,
"to":27,
"distance":257
},
{
"from":0,
"to":28,
"distance":243
},
{
"from":0,
"to":29,
"distance":237
},
{
"from":0,
"to":30,
"distance":181
},
{
"from":0,
"to":31,
"distance":71
},
{
"from":0,
"to":32,
"distance":13
},
{
"from":1,
"to":22,
"distance":104
},
{
"from":0,
"to":33,
"distance":15
},
{
"from":3,
"to":4,
"distance":83
},
{
"from":0,
"to":34,
"distance":158
},
{
"from":0,
"to":35,
"distance":267
},
{
"from":0,
"to":36,
"distance":293
},
{
"from":0,
"to":37,
"distance":267
},
{
"from":0,
"to":38,
"distance":293
},
{
"from":1,
"to":32,
"distance":23
},
{
"from":4,
"to":2,
"distance":96
},
{
"from":4,
"to":5,
"distance":83
},
{
"from":5,
"to":3,
"distance":121
},
{
"from":5,
"to":7,
"distance":52
},
{
"from":6,
"to":1,
"distance":151
},
{
"from":3,
"to":32,
"distance":80
},
{
"from":3,
"to":33,
"distance":89
},
{
"from":6,
"to":5,
"distance":32
},
{
"from":6,
"to":8,
"distance":64
},
{
"from":5,
"to":22,
"distance":78
},
{
"from":4,
"to":33,
"distance":124
},
{
"from":4,
"to":34,
"distance":25
},
{
"from":7,
"to":6,
"distance":40
},
{
"from":6,
"to":21,
"distance":121
},
{
"from":6,
"to":22,
"distance":73
},
{
"from":7,
"to":12,
"distance":65
},
{
"from":8,
"to":4,
"distance":84
},
{
"from":8,
"to":5,
"distance":58
},
{
"from":8,
"to":7,
"distance":32
},
{
"from":8,
"to":9,
"distance":61
},
{
"from":8,
"to":10,
"distance":66
},
{
"from":8,
"to":12,
"distance":88
},
{
"from":6,
"to":34,
"distance":101
},
{
"from":9,
"to":6,
"distance":92
},
{
"from":9,
"to":7,
"distance":52
},
{
"from":9,
"to":10,
"distance":31
},
{
"from":7,
"to":34,
"distance":112
},
{
"from":10,
"to":7,
"distance":53
},
{
"from":10,
"to":11,
"distance":63
},
{
"from":11,
"to":7,
"distance":93
},
{
"from":11,
"to":9,
"distance":84
},
{
"from":9,
"to":37,
"distance":128
},
{
"from":12,
"to":9,
"distance":58
},
{
"from":12,
"to":11,
"distance":27
},
{
"from":10,
"to":35,
"distance":99
},
{
"from":10,
"to":36,
"distance":82
},
{
"from":10,
"to":38,
"distance":119
},
{
"from":13,
"to":16,
"distance":96
},
{
"from":13,
"to":20,
"distance":81
},
{
"from":13,
"to":21,
"distance":83
},
{
"from":14,
"to":13,
"distance":38
},
{
"from":14,
"to":17,
"distance":87
},
{
"from":14,
"to":18,
"distance":54
},
{
"from":15,
"to":11,
"distance":177
},
{
"from":14,
"to":21,
"distance":97
},
{
"from":15,
"to":14,
"distance":99
},
{
"from":15,
"to":16,
"distance":69
},
{
"from":16,
"to":14,
"distance":64
},
{
"from":16,
"to":17,
"distance":38
},
{
"from":17,
"to":15,
"distance":65
},
{
"from":16,
"to":26,
"distance":225
},
{
"from":17,
"to":19,
"distance":83
},
{
"from":17,
"to":26,
"distance":223
},
{
"from":18,
"to":17,
"distance":66
},
{
"from":18,
"to":19,
"distance":38
},
{
"from":18,
"to":20,
"distance":51
},
{
"from":18,
"to":21,
"distance":97
},
{
"from":18,
"to":26,
"distance":172
},
{
"from":21,
"to":1,
"distance":144
},
{
"from":20,
"to":14,
"distance":46
},
{
"from":19,
"to":25,
"distance":83
},
{
"from":20,
"to":16,
"distance":66
},
{
"from":20,
"to":17,
"distance":83
},
{
"from":19,
"to":27,
"distance":214
},
{
"from":20,
"to":19,
"distance":68
},
{
"from":20,
"to":23,
"distance":107
},
{
"from":22,
"to":7,
"distance":112
},
{
"from":21,
"to":20,
"distance":64
},
{
"from":21,
"to":24,
"distance":78
},
{
"from":22,
"to":20,
"distance":148
},
{
"from":22,
"to":21,
"distance":98
},
{
"from":22,
"to":23,
"distance":94
},
{
"from":23,
"to":21,
"distance":57
},
{
"from":24,
"to":19,
"distance":145
},
{
"from":24,
"to":23,
"distance":49
},
{
"from":24,
"to":26,
"distance":122
},
{
"from":25,
"to":21,
"distance":79
},
{
"from":25,
"to":23,
"distance":77
},
{
"from":25,
"to":24,
"distance":60
},
{
"from":26,
"to":15,
"distance":288
},
{
"from":25,
"to":26,
"distance":126
},
{
"from":26,
"to":19,
"distance":166
},
{
"from":26,
"to":27,
"distance":91
},
{
"from":26,
"to":29,
"distance":111
},
{
"from":27,
"to":28,
"distance":68
},
{
"from":28,
"to":19,
"distance":259
},
{
"from":28,
"to":30,
"distance":85
},
{
"from":31,
"to":1,
"distance":75
},
{
"from":29,
"to":27,
"distance":96
},
{
"from":29,
"to":28,
"distance":60
},
{
"from":30,
"to":19,
"distance":185
},
{
"from":29,
"to":30,
"distance":70
},
{
"from":29,
"to":31,
"distance":162
},
{
"from":32,
"to":2,
"distance":47
},
{
"from":30,
"to":26,
"distance":58
},
{
"from":30,
"to":27,
"distance":86
},
{
"from":33,
"to":1,
"distance":34
},
{
"from":31,
"to":21,
"distance":77
},
{
"from":33,
"to":2,
"distance":44
},
{
"from":31,
"to":23,
"distance":44
},
{
"from":31,
"to":24,
"distance":60
},
{
"from":31,
"to":25,
"distance":101
},
{
"from":31,
"to":28,
"distance":192
},
{
"from":31,
"to":30,
"distance":130
},
{
"from":31,
"to":32,
"distance":59
},
{
"from":32,
"to":23,
"distance":85
},
{
"from":34,
"to":3,
"distance":111
},
{
"from":32,
"to":24,
"distance":107
},
{
"from":34,
"to":5,
"distance":67
},
{
"from":34,
"to":8,
"distance":60
},
{
"from":33,
"to":23,
"distance":112
},
{
"from":35,
"to":8,
"distance":75
},
{
"from":35,
"to":9,
"distance":116
},
{
"from":33,
"to":31,
"distance":84
},
{
"from":33,
"to":32,
"distance":27
},
{
"from":36,
"to":9,
"distance":108
},
{
"from":36,
"to":11,
"distance":44
},
{
"from":36,
"to":15,
"distance":204
},
{
"from":37,
"to":11,
"distance":55
},
{
"from":37,
"to":12,
"distance":79
},
{
"from":37,
"to":15,
"distance":207
},
{
"from":35,
"to":36,
"distance":158
},
{
"from":38,
"to":11,
"distance":77
},
{
"from":38,
"to":15,
"distance":201
},
{
"from":36,
"to":37,
"distance":50
},
{
"from":37,
"to":38,
"distance":26
},
{
"from":38,
"to":36,
"distance":73
}
]
}
Vincent Furnon
Mar 8, 2016, 1:09:47 PM3/8/16
to or-tools...@googlegroups.com
Hi Nick,
I finally had time to test your data with C++ code (sorry for the delay). Using the SAVINGS heuristic with no special tuning I get to a local minimum in 8ms with a solution cost of 2340; if I let it run with guided local search, it gets to 2336 in 400ms and 2312 in 22s (this could probably be sped up with some tuning).
Vincent
Reply all
Reply to author
Forward
0 new messages