• Gurobi Staff

Hi Assia,

Here are some ideas:

• You mention an IIS, but also said that the problem is that x (I'm assuming xd here?) is not being forced to 0 when q2<d. What exactly is the issue - are you getting a status "infeasible" from Gurobi, or an incorrect solution that Gurobi considers feasible?
• Wouldn't constraints 7 and 10 enforce that the total load of a vehicle doesn't exceed its capacity, which would automatically imply all served locations have demand no more than that capacity?
• If constraints 8 and 9 are needed, should you not also consider the option that a particular customer with large demand is visited in the middle of the trip, instead of only looking at arcs (0, i) and (i, 0) ?
• Finally, you can simplify your code a lot by using xt.sum('*', j) instead of grb.quicksum(xt[i, j] for i in nodes if i != j) ; note that you've excluded the cases where i=j already when you generated arcs_k

Hope this helps!

Kind regards,
Ronald

Hi Ronald,

Thank you so much for your help. I got the following status:

Model is infeasible
Best objective -, best bound -, gap -
Set parameter TimeLimit to value 3600
No optimal solution found
run time average TDVRP:  0.007054805755615234
Travel time  0
Warning: linear constraint 4 and linear constraint 5 have the same name "C3"

IIS computed: 1 constraints, 0 bounds
IIS runtime: 0.00 seconds (0.00 work units)

The following constraints and variables are in the IIS:
C9: 15.0 xd[0,6] + 15.0 xd[6,0] < -1.0

I tried to put the sum (xt(j,i)) rather than the arcs(0,i) and (i,0) but I got the same result. For the constraint, it should handle the capacity but it is not the case. I don't figure out what I miss in my model.

If I understand, I can rewrite the constraint 4 as follows:

for j in customers:
mdl.addConstr(xt.sum('*', j) - xt.sum('*',i), name = 'C4') 
• Gurobi Staff

Ah... one problem is that if the difference between demand and the smallest vehicle is large enough, that constraint can never be satisfied. For example, with demand=31 and capacity=15, you have:

(xt[0,i] + xt[i,0] - 1)*15 <= 15 - 31

which translates to the impossible constraint

15*xt[0,i] + 15*xt[i,0] <= -1

Instead, you will want to involve variable y here. If the first vehicle traverses (0, i) then you want to ensure y[i] <= q1 - demand[i]. Can you formulate that? You're right that there's no need to consider other arcs to node i.

for j in customers:
mdl.addConstr(xt.sum('*', j) - xt.sum(j,'*') == 0, name = 'C4') 

Thank you for clarifying the formulation. I will add your suggestion. Meanwhile, I try to formulate it as follows:
arc_k = {(i, j) for i in nodes for j in nodes if i != j}
for i in customers:
mdl.addConstr(df.demand[i] <= q2*w + 10000 * (1-w), name ='C12')
mdl.addConstr(q2 * (1-w) <= df.demand[i], name = 'C13')
mdl.addConstr(grb.sum(xd[j,i] for j in nodes) <= w, name = 'C14')
mdl.addConstr(10000 * (1-w) <= grb.sum(xd[j,i] for j in nodes), name = 'C15')
But I get this error regarding the constraint 12:
gurobipy.TempConstr.__bool__()

GurobiError: Constraint has no bool value (are you trying "lb <= expr <= ub"?

• Gurobi Staff

I cannot reproduce the error; there might be a problem with the type/values of some of your variables. What is the type of df.demand[i] - is it a single float, or a list/vector/dataseries? If that doesn't help, could you update your message to include a minimal reproducible example? Also note that grb.sum() will give an error too - you should either use grb.quicksum or xt.sum() on your variable.

Here's what I tried without getting the error. Note that demand[i] here is a normal Python float.

import gurobipy as gpcustomers = range(3)demand = [5]*len(customers)mdl = gp.Model()q2 = 15w = mdl.addVar()for i in customers:    mdl.addConstr(demand[i] <= q2*w + 10000 * (1-w), name ='C12')