Skip to main content

Enforce binary variable to zero when the sum is negative

Awaiting user input



  • Ronald van der Velden
    Gurobi Staff 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,

  • Assia Kamal-idrissi
    First Question

    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'
  • Ronald van der Velden
    Gurobi Staff 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.

    Finally, constraint 4 would read:

    for j in customers:
      mdl.addConstr(xt.sum('*', j) - xt.sum(j,'*') == 0, name = 'C4'
  • Assia Kamal-idrissi
    First Question

    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:

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

  • Ronald van der Velden
    Gurobi Staff 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 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')

Please sign in to leave a comment.