solve.py

def solve(self):
    #   Now, the model is missing of the subtour elimination constraints.
    #   The number of these constraints is 2^N-2 where N is the number of cities selected. Too many.
    #   What we can do is:
    #       1. Solve the problem without the Subtour elimination constraints
    #       2. Get the solution and see if there are subtours of length lower than N
    #       3. Add the constraints that exclude those subtours
    #       4. Goto 1 and repeat until there are no more subtours
    while True:
        self.santa.solve(solvers.PULP_CBC_CMD(msg=True))

        G = self.build_graph_from_current_solution()
        pos = nx.get_node_attributes(G, 'pos')
        nx.draw(G, pos, node_size=200)
        plt.show()
        if self.add_subtour_constraints():
            break
    print("Solution Found")