Enforce binary variable to zero when the sum is negative
Awaiting user input
Hi,
I'm trying to model the CVRP problem with flow formulation. I'm working with two fleets where the capacity of one can be less than the demand of the customer in some cases (fleet with capacity q2). For this, I have the constraint 'C8' that enforce to not serve this customer. So, it will be served by the other fleet with capacity q1. However the solver doesn't enforce x to 0 if q2<d. Here is what I get for the IIS set (the case for customer 2 with 30 demand and customer 3 with 16:
C9: 15 xd[0,2] + 15 xd[2,0] >= 15
C9: 15 xd[3,0] + 15 xd[0,3] >= 15
arc_k = {(i, j) for i in nodes for j in nodes if i != j}
var = {(i) for i in customers}
xt = mdl.addVars(arc_k, vtype=GRB.BINARY, name='xt')
xd = mdl.addVars(arc_k, vtype=GRB.BINARY, name='xd')
y = mdl.addVars(var, vtype=GRB.CONTINUOUS, lb=0, name='y')
n = len(customers)
UB = [max(q1-df.demand[i],q2-df.demand[i]) for i in range(1,n+1)]
mdl.modelSense = GRB.MINIMIZE
mdl.setObjective(grb.quicksum(time1[i][j] * xt[i, j] if i!=j else 0 for i in nodes
for j in nodes) + grb.quicksum(time2[i][j] * xd[i, j] if i!=j else 0
for i in nodes for j in nodes))
mdl.addConstr(grb.quicksum(xt[0, j] for j in customers) <= n1, name='C11')
mdl.addConstr(grb.quicksum(xt[0, j] for j in customers) <= n2, name='C12')
for j in customers:
mdl.addConstr(grb.quicksum(xt[i, j] for i in nodes if i != j)
+ grb.quicksum(xd[i, j] for i in nodes if i != j) == 1, name='C3')
for j in customers:
mdl.addConstr(grb.quicksum(xt[i, j] if i != j else 0 for i in nodes)
- (grb.quicksum(xt[j, i] if i != j else 0 for i in nodes)) == 0, name = 'C4')
for j in customers:
mdl.addConstr(grb.quicksum(xd[i, j] if i != j else 0 for i in nodes)
- (grb.quicksum(xd[j, i] if i != j else 0 for i in nodes)) == 0, name = 'C5')
for i in customers:
for j in customers:
if i != j:
mdl.addConstr(y[j] <= y[i] - df.demand[j]* (xt[i,j] + xd[i,j]) + 100000 * (1- (xt[i, j]+xd[i,j])) , name= 'C7')
for i in customers:
mdl.addConstr((xt[0,i] + xt[i,0] - 1)*q1 <= q1 - df.demand[i], name= 'C8')
for i in customers:
mdl.addConstr(((xd[0,i] + xd[i,0] - 1)*q2 <= q2 - df.demand[i], name= 'C9')
for i in customers:
mdl.addConstr(y[i] <= UB[i-1], name = 'C10')
return mdl, xt, xd
-
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,
Ronald0 -
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')
0 -
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.
Finally, constraint 4 would read:
for j in customers: mdl.addConstr(xt.sum('*', j) - xt.sum(j,'*') == 0, name = 'C4')
1 -
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}
xx= mdl.addVars(arc_k, vtype=GRB.BINARY, name='xd’)
w = mdl.addVar(0,1,vtype=GRB.BINARY, name='w')
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"?
0 -
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 gp
customers = range(3)
demand = [5]*len(customers)
mdl = gp.Model()
q2 = 15
w = mdl.addVar()
for i in customers:
mdl.addConstr(demand[i] <= q2*w + 10000 * (1-w), name ='C12')0
Please sign in to leave a comment.
Comments
5 comments