Pulp Exception: problem Not Solved & heuristic_only returns different solution than shown in preview

[lmarie48]

Hi, I am trying to use VRPy for a CVRP with one depot and 421 client locations. I created a 423x423 numpy array and a graph from this based on the OR-tools example from the documentation. I want to minimize the routes' total length, as well as include restrictions on the maximum length of every route which I tried to implement via the "time" attribute via the following code. I am using Gurobi as a solver which I has worked previously for another optimisation.

G = from_numpy_matrix(D, create_using=nx.DiGraph())

set_node_attributes(G, values=load, name="demand")

G = relabel_nodes(G {0: "Source", 422: "Sink"})

for (u, v) in G.edges():
       G.edges[u, v]["time"] = G.edges[u, v]["length"]
       G.edges[u, v]["cost"] = G.edges[u, v]["length"]

prob = VehicleRoutingProblem(G, load_capacity=load_max)))
prob.duration = 10000
prob.solve(solver=solver)

When I run the optimisation it shows initial solutions for the Clarke & Wright and Greedy algorithm but then stops with the error message shown below.

INFO:vrpy.vrp:new upper bound : max num stops = 423
INFO:vrpy.vrp:Clarke & Wright solution found with value 144482.0922427434 and 18 vehicles
INFO:vrpy.vrp:Greedy solution found with value 128950.17631003427 and 13 vehicles
Traceback (most recent call last):
File "<input>", line 16, in <module>
File "C:\Users\_\anaconda3\envs\data_analysis\lib\site-packages\vrpy\vrp.py", line 254, in solve
  self._solve(dive, solver)
File "C:\Users\_\anaconda3\envs\data_analysis\lib\site-packages\vrpy\vrp.py", line 493, in _solve
  self._column_generation()
File "C:\Users\_\anaconda3\envs\data_analysis\lib\site-packages\vrpy\vrp.py", line 516, in _column_generation
  self._find_columns()
File "C:\Users\_\anaconda3\envs\data_analysis\lib\site-packages\vrpy\vrp.py", line 540, in _find_columns
  duals, relaxed_cost = self.masterproblem.solve(
File "C:\Users\_\anaconda3\envs\data_analysis\lib\site-packages\vrpy\master_solve_pulp.py", line 52, in solve
  raise Exception("problem " + str(pulp.LpStatus[self.prob.status]))
Exception: problem Not Solved

I do realize that the graph size is quite large but I thought with Gurobi solver I should be able to compute it. However, to get at least one feasible solution I tried to set the heuristic_only attribute as True but this returns a number of 62 routes which is significantly higher than what is shown in the preview if I try to run the full optimisation. Any idea what the error could result from and how I could solve it? I also checked the entries of my matrix so I am sure that every location is close enough to the source/sink for the model not being entirely infeasible. Please let me know if it would help to see the matrix. Going forward I would also be happy to use the results from Greedy algorithm as interim solution if I could extract this result somehow. I also tried setting the num_iter attribute to 0 but this also only results in the error message shown above.

[Kuifje02]

Hi there ! Thanks for you feedback !

Could you share your data so that we can try tro replicate the error ?

[lmarie48]

Sure! attached the values of distance matrix D. I declared it as following

D = np.array(dist_matrix, dtype=[("length", int)])

dist_matrix.txt

[Kuifje02]

Could you please provide a minimal reproducing example ? (just like the one in your first post, but with the bit of code that reads the distance matrix). Thanks !

[lmarie48]

Sure!

D = np.array(np.zeros([423, 423]), dtype=[("length", float)])

Dtxt = np.loadtxt(open("dist_matrix.txt", "rb"), delimiter=",")

for source in range(len(D)):
    for target in range(len(D)):
        D[source, target] = Dtxt[source, target]

[Kuifje02]

Thanks. The code is still incomplete for replication:

import numpy as np
import networkx as nx
from vrpy import VehicleRoutingProblem

D = np.array(np.zeros([423, 423]), dtype=[("length", float)])

Dtxt = np.loadtxt(open("dist_matrix.txt", "rb"), delimiter=",")

for source in range(len(D)):
    for target in range(len(D)):
        D[source, target] = Dtxt[source, target]

G = nx.from_numpy_matrix(D, create_using=nx.DiGraph())

nx.set_node_attributes(G, values=load, name="demand")

G = nx.relabel_nodes(G, {0: "Source", 422: "Sink"})

for (u, v) in G.edges():
       G.edges[u, v]["time"] = G.edges[u, v]["length"]
       G.edges[u, v]["cost"] = G.edges[u, v]["length"]

prob = VehicleRoutingProblem(G, load_capacity=load_max)))
prob.duration = 10000
prob.solve(solver="CBC")

load_max and load are undefined. Please correct the above code and make sure it works so that I can try and replicate the issue :)

[lmarie48]

Ahh true sorry! Please see below the complete code. Thank you for your time!

load = 0.03
load_max = 3.89

D = np.array(np.zeros([423, 423]), dtype=[("length", float)])

Dtxt = np.loadtxt(open("dist_matrix.txt", "rb"), delimiter=",")

for source in range(len(D)):
    for target in range(len(D)):
        D[source, target] = Dtxt[source, target]

peak_load = {
    key: load
    for key in list(range(1, len(D)-1))
}

G = from_numpy_matrix(D, create_using=nx.DiGraph())

set_node_attributes(G, values=peak_load, name="demand")

G= relabel_nodes(G, {0: "Source", 422: "Sink"})

for (u, v) in G.edges():
       G.edges[u, v]["time"] = G.edges[u, v]["length"]
       G.edges[u, v]["cost"] = G.edges[u, v]["length"]

prob = VehicleRoutingProblem(G, load_capacity=int(np.round(load_max)))
prob.duration = 10000
prob.solve(solver=solver)

[Kuifje02]

I think the error comes from the fact that the name of the solve should be in lower case. Try with "gurobi" or "cplex" or "cbc", it should work.

Will add a check to raise an error is the solver's name is incorrect.

This should also be more clear in the docs.

[Kuifje02]

Also, you are right, using heuristic_only = True yields a different solution than the one shown in the log when not using the option. The version used in this case is more sophisticated. This should be changed.

To get this solution, set a time_limit to say 30 sec with heuristic_only=False.

[lmarie48]

Now it works! Perfect, thank you so much!