Lazy constraint callback error

alex st

unread,

Mar 20, 2019, 7:28:41 AM3/20/19

to Gurobi Optimization

Hi all,

I have modeled a vehicle routing problem which seems to be working just fine.

After that I want to add an extra assignment (consisting of a pickup point and a delivery point).

I use an insertion method which inserts the assignment in one of the routes, namely the route where the least amount of extra distance is travelled.

For that I use the variable y[i,j,k], where i is the assignment number (zero in this case, as i only have 1 assignment), k is the route in which the job should be inserted and j is the node in route k after which the assignment is inserted.

I let the model run and it finds that the optimal solution is: zero for all values of y[i,j,k] except for y[0,1,0] which equals 1. This makes sense since there is only 1 job to be assigned and when I plot it, this result seems very plausible.

Now I add a callback function with a lazy constraint. This lazy constraint has the goal to cut off the solutions that exceed the trucks load capacity or do not honor the time windows (each node has a time window in which it should be visited). Now something very strange happens. The first part of my callback function goes like this:

def time_and_capacity_constraint(model,where):

if where == GRB.callback.MIPSOL:

print(model.cbGetSolution(model._vars))

for i in range(A):

for k in range(K):

for j in range(L[k]-1):

sol = model.cbGetSolution(model._vars[i,j,k])

if sol > 0.9:

print('i = ' + str(i))

print('j = ' + str(j))

print('k = ' + str(k))

As you can see I print the solution in the third line. Now in the output console I read that the solution that it checks first only has y[0,1,1] as a value of 1. I already think this is weird, why would the solution not be y[0,1,0] from the start? It then gives the following error:

sol = model.cbGetSolution(model._vars[i,j,k])

KeyError: (1, 2, 1)

This does not make sense to me either since the values of i,j and k are 0,1,1 and not 1,2,1. So of course it can not find the solution of model_vars[1,2,1] because there is only 1 job! It does not exist.

After this is starts over and returns y[0,0,0] as the solution, this also does not make sense to me. This does not give any errors however.

After this it does it again but now returns y[0,1,0] as the solution. Then the output returns:

Exception ignored in: 'gurobipy.callbackstub'

Traceback (most recent call last):

File "callback.pxi", line 183, in gurobipy.CallbackClass.callback

File "C:/Users/alexs/Desktop/Universiteit/MSc/Research Assignment/three_routes_each_one_truck_combined_with_time_windows.py", line 609, in capacity_constraint

sol = model.cbGetSolution(model._vars[i,j,k])

KeyError: ((1, 2, 1),)

And eventually my callback function and lazy constraint dont work. Can anybody explain this to me?

My entire callback function:

def time_and_capacity_constraint(model,where):

if where == GRB.callback.MIPSOL:

print(model.cbGetSolution(model._vars))

for i in range(A):

for k in range(K):

for j in range(L[k]-1):

sol = model.cbGetSolution(model._vars[i,j,k])

if sol > 0.9:

print('i = ' + str(i))

print('j = ' + str(j))

print('k = ' + str(k))

Q=1.5

load_2 = load_solution[j,k]

load_ass = q_ass[i]

Exp = LinExpr([(1,model._vars[i,j,k])])

reference = (truck_size+1.5)-load_2-load_ass

if reference <= 1:

Q -= 1

next_node = arc_order.select(j,'*',k) # here I select the node that would normally follow the node after which the assignment is inserted

if len(next_node)>=2:

next_node = arc_order.select(j,'*',k)[1][1]

else:

next_node = arc_order.select(j,'*',k)[0][1]

new_time= time_solution[next_node,k]+extra_time(routes,i,j,k)

index = 1+sum(L_copy[f] for f in range(k))+j

if new_time > Time_windows[index][1]:

Q -= 1

if k == 0:

dist = math.sqrt((route1[j][0]-assignments[2*i][0])*(route1[j][0]-assignments[2*i][0]) + (route1[j][1]-assignments[2*i][1])*(route1[j][1]-assignments[2*i][1]))

if time_solution[j,k]+(dist/speed)+s1[j] > Time_windows_ass[2*i][1]:

Q -= 1

for i in range(L_copy[k]-3-j): #this determines how many times it must be checked whether the truck arrives before each next time window

new_time = new_time + traveltime(points1,j+1+i,j+2+i)+s1[j+1+i]

if new_time > Time_windows1[j+1+i][1]:

Q -= 1

if k == 1:

dist = math.sqrt((route2[j][0]-assignments[2*i][0])*(route2[j][0]-assignments[2*i][0]) + (route2[j][1]-assignments[2*i][1])*(route2[j][1]-assignments[2*i][1]))

if time_solution[j,k]+(dist/speed)+s2[j] > Time_windows_ass[2*i][1]:

Q -= 1

for i in range(L_copy[k]-3-j): #this determines how many times it must be checked whether the truck arrives before each next time window

new_time = new_time + traveltime(points2,j+1+i,j+2+i)+s2[j+1+i]

if new_time > Time_windows2[j+1+i][1]:

Q -= 1

if k == 2:

dist = math.sqrt((route3[j][0]-assignments[2*i][0])*(route3[j][0]-assignments[2*i][0]) + (route3[j][1]-assignments[2*i][1])*(route3[j][1]-assignments[2*i][1]))

if time_solution[j,k]+(dist/speed)+s3[j] > Time_windows_ass[2*i][1]:

Q -= 1

for i in range(L_copy[k]-3-j): #this determines how many times it must be checked whether the truck arrives before each next time window

new_time = new_time + traveltime(points3,j+1+i,j+2+i)+s3[j+1+i]

if new_time > Time_windows3[j+1+i][1]:

Q -= 1

model.cbLazy(Exp <= Q)

Silke Horn

unread,

Mar 22, 2019, 5:00:49 AM3/22/19

to 'Tobias Achterberg' via Gurobi Optimization

Hi,

The MIPSOL callback is called for every feasible solution that is encountered along the way not only for the optimal one in the end. In your case it seems that y[0,1,1]=1 is part of a feasible solution that is found before the optimal one.

As for the second question, since you are iterating over i, j, and k, I would assume that they different values. Could you show us the definitions of A, K, L, and _vars?

- Silke

> --
>
> ---
> You received this message because you are subscribed to the Google Groups "Gurobi Optimization" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to gurobi+un...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

alex st

unread,

Mar 24, 2019, 11:32:21 AM3/24/19

to Gurobi Optimization

Hi Silke,

The definitions:

A is the number of extra assignments, which equals 1

K is the number of routes in which the extra assignment could be inserted, I have 3.

L is a list with the number of points in each route, i have set it to [6,6,6]. An extra assignment must be inserted in between 2 points of the already existing route, so that gives L[k]-1 possibilities.

I have set m._vars = y . Here y is my gurobi variable.

y is:

{(0, 0, 0): <gurobi.Var arc0_0_0>,

(0, 1, 0): <gurobi.Var arc0_1_0>,

(0, 2, 0): <gurobi.Var arc0_2_0>,

(0, 3, 0): <gurobi.Var arc0_3_0>,

(0, 4, 0): <gurobi.Var arc0_4_0>,

(0, 0, 1): <gurobi.Var arc0_0_1>,

(0, 1, 1): <gurobi.Var arc0_1_1>,

(0, 2, 1): <gurobi.Var arc0_2_1>,

(0, 3, 1): <gurobi.Var arc0_3_1>,

(0, 4, 1): <gurobi.Var arc0_4_1>,

(0, 0, 2): <gurobi.Var arc0_0_2>,

(0, 1, 2): <gurobi.Var arc0_1_2>,

(0, 2, 2): <gurobi.Var arc0_2_2>,

(0, 3, 2): <gurobi.Var arc0_3_2>,

(0, 4, 2): <gurobi.Var arc0_4_2>}

So yes i am really wondering where the following error comes from:

Traceback (most recent call last):

File "callback.pxi", line 183, in gurobipy.CallbackClass.callback

File "C:/Users/alexs/Desktop/Universiteit/MSc/Research Assignment/three_routes_each_one_truck_combined_with_time_windows_22_3_2019.py", line 555, in capacity_constraint

sol = model.cbGetSolution(model._vars[ii,jj,kk])

KeyError: (2, 1, 0)

Op vrijdag 22 maart 2019 10:00:49 UTC+1 schreef horn:

Silke Horn

unread,

Mar 25, 2019, 5:28:13 AM3/25/19

to gur...@googlegroups.com

Hi,

This does not make sense… If A=1, then i should only take the value 0 in your for-loop.
However, I am slightly confused since you have now posted three different versions of the error message:

> sol = model.cbGetSolution(model._vars[ii,jj,kk])
>
> KeyError: (2, 1, 0)

> > sol = model.cbGetSolution(model._vars[i,j,k])
> > KeyError: (1, 2, 1)

> > sol = model.cbGetSolution(model._vars[i,j,k])
> > KeyError: ((1, 2, 1),)

Moreover, you said that you were getting the error for some solutions but not for all. Are A, K and L really constants?

I will take a closer look if you can share a minimal working code example to reproduce the error.

- Silke

alex st

unread,

Mar 25, 2019, 8:19:36 AM3/25/19

to Gurobi Optimization

Hi Silke,

I completely agree, i should only take the value 0 in my loop. That is why I am so baffled about this error message.

Concerning the different error messages:

The first one:

> sol = model.cbGetSolution(model._vars[ii,jj,kk])
>
> KeyError: (2, 1, 0)

Here I tried replacing i,j,k wit ii,jj,kk to see if anything would change. I realize now that of course it doesnt.

The KeyErrors (2,1,0) and (1,2,1) are different because I tried running the code after I altered one of the initial routes to see if the error would still show up. It does, however since the initial route was a bit different the error is as well I assume.

A,K and L are really constants yes.

I attached the code. The top part of the code contains the initial truck route solutions.

Op maandag 25 maart 2019 10:28:13 UTC+1 schreef horn:

shortened version of code.py

Silke Horn

unread,

Mar 25, 2019, 8:54:08 AM3/25/19

to 'Silke Horn' via Gurobi Optimization

Hi,

You use the same variable i again as a loop variable later in your callback. That is how the value of i becomes 2. When I change the name of those loop variables (there’s three of them, for k = 0, 1, 2) to something else, the error goes away.

- Silke

> <shortened version of code.py>

alex st

unread,

Mar 25, 2019, 10:51:31 AM3/25/19

to Gurobi Optimization

Hi,

Yes i see it now, thank you very much!

Do you know why it only checks four solutions in the callback function?

I ask this since the assignment could be inserted in 13 different places ( the number of variables y).

Alex

Op maandag 25 maart 2019 13:54:08 UTC+1 schreef horn:

Reply all

Reply to author

Forward