Or-tools: segmentation fault: 11 with OOP in python

[bendichter]

It seems that running routing.SolveWithParameters() within a method is causing a segmentation fault. I got a toy vehicle routing script working perfectly. Then I tried to run the optimization inside a method of a class, and I got a Segmentation fault: 11 error. I then took the methods and copy/pasted them into a script in the order that they were evaluated and it works fine. Here are the files for comparison:

class version:

from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
from itertools import chain
from collections import Counter

import pdb

def distance(x1, y1, x2, y2):
    # Manhattan distance
    return abs(x1 - x2) + abs(y1 - y2)

# Distance callback
class CreateDistanceCallback(object):
    """Create callback to calculate distances between points."""

    def __init__(self, locations):
        """Initialize distance array."""
        size = len(locations)
        self.matrix = {}

        for from_node in range(size):
            self.matrix[from_node] = {}
            for to_node in range(size):
                if from_node == to_node:
                    self.matrix[from_node][to_node] = 0
                else:
                    x1 = locations[from_node][0]
                    y1 = locations[from_node][1]
                    x2 = locations[to_node][0]
                    y2 = locations[to_node][1]
                    self.matrix[from_node][to_node] = distance(x1, y1, x2, y2)

    def distance(self, from_node, to_node):
        return self.matrix[from_node][to_node]

# spefific dimensions for individual shipments
class CreateDemandCallback:
    """
    dimenstion for a specific shipment
    """
    def __init__(self, i: int, shipment: tuple):
        self.i = i
        self.shipment = shipment

    def demand(self, a, b):
        if a == 2 * self.i:
            return self.shipment[3]
        elif a == 2 * self.i + 1:
            return -1 * self.shipment[3]
        else:
            return 0

    def negdemand(self, a, b):
        return -1 * self.demand(a, b)

class CreateWeightCallback:
    """
    dimension for weight of all shipments
    """
    def __init__(self, shipments: list):
        self.shipments = shipments

    def weight(self, a, b):
        if a >= len(self.shipments * 2):  # depot
            return 0
        else:
            if not a % 2:  # pick up
                return self.shipments[a//2][3]
            else:  # drop off
                return -1 * self.shipments[a//2][3]

class VRP:
    def __init__(self, shipments: list, depots: list, truck_cap=200):

        self.assignment = None
        self.shipments = shipments
        self.depots = depots
        self.truck_cap = truck_cap

        self.nodes = list(chain(*[(s[1], s[2]) for s in shipments])) + depots

        self.num_nodes = len(self.nodes)
        self.depot_indices = [x + 2 * len(shipments) for x in range(len(depots))]
        self.ntrucks = len(depots)

        self.model_parameters = pywrapcp.RoutingModel.DefaultModelParameters()

        self.routing = pywrapcp.RoutingModel(self.num_nodes, self.ntrucks, self.depot_indices, self.depot_indices,
                                             self.model_parameters)

        dist_between_nodes = CreateDistanceCallback(self.nodes)
        self.dist_callback = dist_between_nodes.distance
        self.routing.SetArcCostEvaluatorOfAllVehicles(self.dist_callback)

        # Adding capacity dimension constraints.
        # individual shipments
        for i, shipment in enumerate(shipments):
            demand_callback = CreateDemandCallback(i, shipment).demand
            self.routing.AddDimension(demand_callback, 0, self.truck_cap, True, shipment[0])

        # weight
        weight_callback = CreateWeightCallback(shipments).weight
        self.routing.AddDimension(weight_callback, 0, self.truck_cap, True, 'weight')

    def run_opt(self, search_params=None):

        # Setting first solution heuristic: the
        # method for finding a first solution to the problem.
        if not search_params:
            search_params = pywrapcp.RoutingModel.DefaultSearchParameters()
            search_params.first_solution_strategy = (
                 routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

        # The 'PATH_CHEAPEST_ARC' method does the following:
        # Starting from a route "start" node, connect it to the node which produces the
        # cheapest route segment, then extend the route by iterating on the last
        # node added to the route.

        self.assignment = self.routing.SolveWithParameters(search_params)

    def print_results(self):
        if self.assignment:
            # Display solution.
            for vehicle_nbr in range(self.ntrucks):
                current_shipments = Counter()
                index = self.routing.Start(vehicle_nbr)
                index_next = self.assignment.Value(self.routing.NextVar(index))
                route = ''
                route_dist = 0
                route_shipments = []

                while not self.routing.IsEnd(index_next):
                    node_index = self.routing.IndexToNode(index)
                    node_index_next = self.routing.IndexToNode(index_next)

                    # Add the distance to the next node.
                    route_dist += self.dist_callback(node_index, node_index_next)
                    index = index_next
                    index_next = self.assignment.Value(self.routing.NextVar(index))

                    if node_index < 2 * len(self.shipments):
                        shipment = self.shipments[node_index // 2]
                        if not node_index % 2:
                            current_shipments[shipment[0]] += shipment[3]
                            route_shipments.append(shipment[0])
                        else:
                            current_shipments[shipment[0]] += -1 * shipment[3]

                        ship_str = str({key: value for key, value in current_shipments.items() if value})
                        if self.nodes[node_index] != self.nodes[node_index_next]:
                            route += str(node_index) + str(self.nodes[node_index]) + " -" + ship_str + "-> "
                        else:
                            route += str(self.nodes[node_index]) + " -> "

                node_index = self.routing.IndexToNode(index)
                node_index_next = self.routing.IndexToNode(index_next)
                route += str(self.nodes[node_index]) + " -> " + str(self.nodes[node_index_next])
                route_dist += self.dist_callback(node_index, node_index_next)
                print("Route for vehicle " + str(vehicle_nbr) + ":\n\n" + route + "\n")
                print("Distance of route " + str(vehicle_nbr) + ": " + str(route_dist))
                print("Shipments made by vehicle " + str(vehicle_nbr) + ": " + str(route_shipments) + "\n")
        else:
            print('No solution found.')


def main():

    # name, from, to, weight
    shipments = [('a', (2, 1), (2, 3), 50),
                 ('b', (2, 2), (2, 4), 50),
                 ('c', (1, 1), (2, 5), 50),
                 ('d', (-6, -5), (-5, -5), 100)]
    depots = [(0, 0), (-6, -6)]
    vrp = VRP(shipments, depots)
    vrp.run_opt()
    #vrp.print_results()


if __name__ == '__main__':
    main()

script version:

from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
from itertools import chain
from collections import Counter
from abc import ABC

def distance(x1, y1, x2, y2):
    # Manhattan distance
    return abs(x1 - x2) + abs(y1 - y2)


# Distance callback
class CreateDistanceCallback(object):
    """Create callback to calculate distances between points."""

    def __init__(self, locations):
        """Initialize distance array."""
        size = len(locations)
        self.matrix = {}

        for from_node in range(size):
            self.matrix[from_node] = {}
            for to_node in range(size):
                if from_node == to_node:
                    self.matrix[from_node][to_node] = 0
                else:
                    x1 = locations[from_node][0]
                    y1 = locations[from_node][1]
                    x2 = locations[to_node][0]
                    y2 = locations[to_node][1]
                    self.matrix[from_node][to_node] = distance(x1, y1, x2, y2)

    def distance(self, from_node, to_node):
        return self.matrix[from_node][to_node]


# spefific dimensions for individual shipments
class CreateDemandCallback:
    """
    dimenstion for a specific shipment
    """
    def __init__(self, i: int, shipment: tuple):
        self.i = i
        self.shipment = shipment

    def demand(self, a, b):
        if a == 2 * self.i:
            return self.shipment[3]
        elif a == 2 * self.i + 1:
            return -1 * self.shipment[3]
        else:
            return 0

    def negdemand(self, a, b):
        return -1 * self.demand(a, b)


class CreateWeightCallback:
    """
    dimension for weight of all shipments
    """
    def __init__(self, shipments: list):
        self.shipments = shipments

    def weight(self, a, b):
        if a >= len(self.shipments * 2):  # depot
            return 0
        else:
            if not a % 2:  # pick up
                return self.shipments[a//2][3]
            else:  # drop off
                return -1 * self.shipments[a//2][3]


self = ABC()  # arbitrary class to facilitate copy/paste


# from main
shipments = [('a', (2, 1), (2, 3), 50),
             ('b', (2, 2), (2, 4), 50),
             ('c', (1, 1), (2, 5), 50),
             ('d', (-6, -5), (-5, -5), 100)]
depots = [(0, 0), (-6, -6)]
truck_cap= 200


# from vrp.__init__
self.assignment = None
self.shipments = shipments
self.depots = depots
self.truck_cap = truck_cap

self.nodes = list(chain(*[(s[1], s[2]) for s in shipments])) + depots

self.num_nodes = len(self.nodes)
self.depot_indices = [x + 2 * len(shipments) for x in range(len(depots))]
self.ntrucks = len(depots)

self.model_parameters = pywrapcp.RoutingModel.DefaultModelParameters()

self.routing = pywrapcp.RoutingModel(self.num_nodes, self.ntrucks, self.depot_indices, self.depot_indices,
                                     self.model_parameters)

dist_between_nodes = CreateDistanceCallback(self.nodes)
self.dist_callback = dist_between_nodes.distance
self.routing.SetArcCostEvaluatorOfAllVehicles(self.dist_callback)

# Adding capacity dimension constraints.
# individual shipments
for i, shipment in enumerate(shipments):
    demand_callback = CreateDemandCallback(i, shipment).demand
    self.routing.AddDimension(demand_callback, 0, self.truck_cap, True, shipment[0])

# weight
weight_callback = CreateWeightCallback(shipments).weight
self.routing.AddDimension(weight_callback, 0, self.truck_cap, True, 'weight')

# from vrp.run_opt
search_params = None
# Setting first solution heuristic: the
# method for finding a first solution to the problem.
if not search_params:
    search_params = pywrapcp.RoutingModel.DefaultSearchParameters()
    search_params.first_solution_strategy = (
         routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

# The 'PATH_CHEAPEST_ARC' method does the following:
# Starting from a route "start" node, connect it to the node which produces the
# cheapest route segment, then extend the route by iterating on the last
# node added to the route.

self.assignment = self.routing.SolveWithParameters(search_params)


# from vrp.print_results
if self.assignment:
    # Display solution.
    for vehicle_nbr in range(self.ntrucks):
        current_shipments = Counter()
        index = self.routing.Start(vehicle_nbr)
        index_next = self.assignment.Value(self.routing.NextVar(index))
        route = ''
        route_dist = 0
        route_shipments = []

        while not self.routing.IsEnd(index_next):
            node_index = self.routing.IndexToNode(index)
            node_index_next = self.routing.IndexToNode(index_next)

            # Add the distance to the next node.
            route_dist += self.dist_callback(node_index, node_index_next)
            index = index_next
            index_next = self.assignment.Value(self.routing.NextVar(index))

            if node_index < 2 * len(self.shipments):
                shipment = self.shipments[node_index // 2]
                if not node_index % 2:
                    current_shipments[shipment[0]] += shipment[3]
                    route_shipments.append(shipment[0])
                else:
                    current_shipments[shipment[0]] += -1 * shipment[3]

                ship_str = str({key: value for key, value in current_shipments.items() if value})
                if self.nodes[node_index] != self.nodes[node_index_next]:
                    route += str(node_index) + str(self.nodes[node_index]) + " -" + ship_str + "-> "
                else:
                    route += str(self.nodes[node_index]) + " -> "

        node_index = self.routing.IndexToNode(index)
        node_index_next = self.routing.IndexToNode(index_next)
        route += str(self.nodes[node_index]) + " -> " + str(self.nodes[node_index_next])
        route_dist += self.dist_callback(node_index, node_index_next)
        print("Route for vehicle " + str(vehicle_nbr) + ":\n\n" + route + "\n")
        print("Distance of route " + str(vehicle_nbr) + ": " + str(route_dist))
        print("Shipments made by vehicle " + str(vehicle_nbr) + ": " + str(route_shipments) + "\n")
else:
    print('No solution found.')

[sairamkrish]

This issue still exists in latest version 6.8.5452.

Unable to run routing.SolveWithParameters() or routing.Solve() from within a python Class. It throws Segmentation fault.

Exact same code runs fine when run as a script (like above).
I am new to ortools. Can someone explain why this happens ? What is the difference ?

[Mizux]

Hi,

When you create some callbacks (e.g. AddDimension(<your_callback>)), you MUST keep a reference on it to keep it alive otherwise it will be Garbage Collected by python interpreter.

@@ -42,42 +42,42 @@ class VRP:
          # Adding capacity dimension constraints.
         # individual shipments
+        self.demand_callback = {}
         for i, shipment in enumerate(shipments):
-            demand_callback = CreateDemandCallback(i, shipment).demand
-            self.routing.AddDimension(demand_callback, 0, self.truck_cap, True, shipment[0])
+            self.demand_callback[i] = CreateDemandCallback(i, shipment).demand
+            self.routing.AddDimension(self.demand_callback[i], 0, self.truck_cap, True, shipment[0])

         # weight
-        weight_callback = CreateWeightCallback(shipments).weight
-        self.routing.AddDimension(weight_callback, 0, self.truck_cap, True, 'weight')
+        self.weight_callback = CreateWeightCallback(shipments).weight
+        self.routing.AddDimension(self.weight_callback, 0, self.truck_cap, True, 'weight')

     def run_opt(self, search_params=None):
         # Setting first solution heuristic: the
         # method for finding a first solution to the problem.
         if not search_params:

note: not a "real" patch since I also remove few lines here and there but I test it and it doesn't crash anymore.

It works in the script version since the callback are declared in the main() function scope so they are alive until the end. In your case callback are created in the init of class VRP and.... are G.B. just after the init function stop...
TLDR: OrTools is a C++ library wrapped in python through SWIG and the wrapper code don't own the callback but just keep a pointer on it, so YOU have to keep alive any callback you pass (e.g. keeping a reference on it)...

ProTips: use ```python when writing code block to have syntax coloration (I try to fixed few of your comments but if you can do it yourself ;))
src: https://help.github.com/articles/creating-and-highlighting-code-blocks/#syntax-highlighting