How to write a conditional summation?
Answered
I am modeling the following constraints using Python and Gurobi:
I tried to model it as the line bellow, where Nd[k] is equivalent to Nk ∪ {d(k)}
m.addConstrs(quicksum(x[i, j, k] for k in K for j in Nd[k]) == 1 for i in P)
Is it possible to model the conditional sum with the given indexes and tupledict structure?
Thank you for the help
-
Is it possible to model the conditional sum with the given indexes and tupledict structure?
Could you please explain what a conditional sum is? The code snippet you showed correctly implements the constraint you showed. Do you get an error when modeling this constraint? If so, could you please provide a minimal reproducible example to reproduce the issue?
1 -
Thank you for the quick response!
I am not sure if conditional sum is the correct term but I was referring to the summation where the range is dependent on another index, in this case k.
Yes!, I get a 'KeyError: (0,1,0)' message.
The problem is a VRP with pickup and delivery:
from math import *
import numpy as np
from gurobipy import Model, GRB, quicksum
def distance(loc1, loc2):
E = 6371
φ1 = np.radians(loc1[0])
λ1 = np.radians(loc1[1])
φ2 = np.radians(loc2[0])
λ2 = np.radians(loc2[1])
return 2 * E * np.arcsin(np.sqrt(np.sin((φ2 - φ1)/2)**2 + np.cos(φ1)*np.cos(φ2)*(np.sin((λ2 - λ1)/2)**2)))The model is fed the pickup locations (lP), the delivery locations (lD), and the driver locations (lK) as well as the type of vehicle of the driver (ωK), and for each request the type of vehicle that can serve that request (ωR). The nodes have a number from 0 to 19 where from 0 to 3 are pickup points, 4 to 7 delivery points, 8 to 13 are the driver locations and 14 to 19 are the end locations of drivers (equal to the initial). An array to hold all locations is created (l) as well as an array where an entry is equal to one if that driver can serve that request and 0 otherwise.
lP = np.array([[0.85, 0.54], [0.37, 0.80], [0.42, 0.16], [0.18, 0.23]])
lD = np.array([[0.54, 0.11], [0.29, 0.11], [0.13, 0.50], [0.45, 0.19]])
lK = np.array([[0.11, 0.23], [0.65, 1.00], [0.67, 0.07], [0.77, 0.23], [0.14, 0.80], [0.10, 0.33]])
ωK = np.array([[1, 0, 0], [0, 1, 0], [0, 0, 1], [0, 0, 1], [0, 1, 0], [0, 0, 1]])
ωR = np.array([[0, 1, 1], [1, 1, 1], [1, 1, 0], [1, 1, 1]])
l = np.concatenate((lP, lD, lK, lK), axis=0)
Ω = np.inner(ωK, ωR)There are 6 drivers and 4 requests in the example.
m = 6
n = 4
K = range(m)
R = range(n)Next, the origin and destination node for each drivers is created.
o = np.array(range(2*n, 2*n+m))
d = np.array(range(2*n+m, 2*(n+m)))Based on the mentioned restrictions, the pickup (P) and delivery (D) points for each courier are created. Two additional groups of points are also created for each driver: one with both pickup and delivery points (N), one with all locations for that driver (V) and the arcs possible for that driver (A). Afterwards, the travel distance (t) is computed.
P = {}
for k in K:
P[k] = [r for r in R if Ω[k][r] == 1]
D = {}
for k in K:
D[k] = [r+n for r in R if Ω[k][r] == 1]
N = {}
for k in K:
N[k] = P[k]+D[k]
V = {}
for k in K:
V[k] = N[k] + [o[k]] + [d[k]]
A = {}
for k in K:
A[k] = [(i, j) for i in V[k] for j in V[k] if i != j]
t = {}
for k in K:
for i in V[k]:
for j in V[k]:
if i != j:
t[i, j, k] = distance(l[i], l[j])/25*60Gurobi is used to solve the model, that for brevity is limited to the constraints causing trouble.
M = Model('Routing')
x = {}
for k in K:
for (i, j) in A[k]:
x[i, j, k] = M.addVar(vtype=GRB.BINARY, name='x')
x = M.addVars(x, vtype=GRB.BINARY, name='x')
M.setObjective(x.prod(t), GRB.MINIMIZE)
Nd = {}
for k in K:
Nd[k] = N[k] + [d[k]]
M.addConstrs(quicksum(x[i, j, k] for k in K for j in Nd[k]) == 1 for i in P)
M.optimize()If the constraints were working I would expect the following result (where '?' could be any courier from 0 to 5):
x[2,7,?] = 1
x[3,14,?] = 1
x[0,17,?] = 1
x[1,18,?] = 1One more, thank you for the help!
1 -
Printing your variables x shows that you indeed don't have a key (0,1,0)
x = {}
for k in K:
for (i, j) in A[k]:
x[i, j, k] = M.addVar(vtype=GRB.BINARY, name='x')
print(x)
>{(1, 2, 0): <gurobi.Var *Awaiting Model Update*>,
(1, 3, 0): <gurobi.Var *Awaiting Model Update*>,
(1, 5, 0): <gurobi.Var *Awaiting Model Update*>, ... }However, you try to access it because you loop over i in P and j in Nd[k]
print(P)
print(Nd[0])
>{0: [1, 2, 3], 1: [0, 1, 2, 3], 2: [0, 1, 3], 3: [0, 1, 3], 4: [0, 1, 2, 3], 5: [0, 1, 3]}
>[1, 2, 3, 5, 6, 7, 14]This means that i goes over the keys of P which are 0,1,2,3,4,5. I don't know whether you want to indeed loop over the keys of P or over the actual key entries P[k]. Anyway, to avoid such key errors, you could implement a safe guard
M.addConstrs(quicksum(x[i, j, k] for k in K for j in Nd[k] if (i,j) in A[k] ) == 1 for i in P)
Note that depending on how you want to handle P, the above fix is not making your model correct. You should definitely check your model for correctness or whether it needs some fixing.
Best regards,
Jaromił1 -
Your solution is correct and solved the problem, thank you very much!
Best regards,
Tomás
0
Please sign in to leave a comment.
Comments
4 comments