Skip to main content

max and min constraints

Ongoing
Roos Vahrmeijer
Gurobi-versary
First Comment
First Question

Hello!

I'm trying to formulate the following constraint in python: 

max{0,qi}<= Qik <= min{Ck, Ck + qi}

I tried to do this with the following formulation: 

m.addConstrs(Q[(i,k)] >= 0 for i in V for k in K if i!=L)
m.addConstrs(Q[(i,k)] >= qi[i] for i in V for k in K if i!=L)
m.addConstrs(Q[(i,k)] <= Ck[k] for i in V for k in K if i!=L)
m.addConstrs(Q[(i,k)] <= (Ck[k] + qi[i]) for i in V for k in K if i!=L)

Unfortunately this does not work has anyone a recommendation to scribe this in an other way? 

 

Kind Regards

Roos 

0

Comments

6 comments

Date Votes
  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    Hi Roos,

    Your linearization of the max and min terms looks ok. I guess "qi" can get negative, otherwise the max and min terms would not make sense.

    What exactly does not work? Could you show the relevant Gurobi log output or error messages?

    Best regards,
    Mario

    0
  • Roos Vahrmeijer
    Gurobi-versary
    First Comment
    First Question

    Yes qi can be negative because by delivery the demand is negative and for pick up it is positive

     

    0
  • Roos Vahrmeijer
    Gurobi-versary
    First Comment
    First Question

    Can share my full code with you 

     

    0
  • Roos Vahrmeijer
    Gurobi-versary
    First Comment
    First Question

    n= 3
    n2 = 3

    P = [i for i in range (1, n+1)]
    D = [i for i in range (n+1,n+n2+1)]
    Ck = {1:6, 2:6}
    K = [i for i in range (1, len(Ck)+1)]
    N = P + D
    qi = {0:0, 1:6, 2:3, 3:6, 4:-6, 5:-3, 6:-6, 7:0}
    di = {0:0, 1:6, 2:3, 3:6, 4:6, 5:3, 6:6, 7:0}

    req ={1:(1,4), 2:(2,5), 3:(3,6)}


    L= 1+n + n2

     

    cijk = {(0,0,1):0, (0,1,1):2.236, (0,2,1):4.123, (0,3,1):2.236, (0,4,1):5.830, (0,5,1):2.236, (0,6,1):3.605, (0,7,1):0,
    (1,0,1):2.236, (1,1,1):0, (1,2,1):5.099, (1,3,1):3.162, (1,4,1):7.280, (1,5,1):3.162, (1,6,1):4, (1,7,1):2.236,
    (2,0,1):4.123, (2,1,1):5.099, (2,2,1):0, (2,3,1):6.325, (2,4,1):9.219, (2,5,1):2,(2,6,1):1.414, (2,7,1):4.123,
    (3,0,1):2.236, (3,1,1):3.162, (3,2,1):6.325, (3,3,1):0, (3,4,1):4.123, (3,5,1):4.472,(3,6,1):5.830, (3,7,1):2.236,
    (4,0,1):5.830, (4,1,1):7.280, (4,2,1):9.219, (4,3,1):4.123, (4,4,1):0, (4,5,1):7.810,(4,6,1):9.219, (4,7,1):5.830,
    (5,0,1):2.236, (5,1,1):3.162, (5,2,1):2, (5,3,1):4.472, (5,4,1):7.810, (5,5,1):0, (5,6,1):1.414, (5,7,1):2.236,
    (6,0,1):3.605, (6,1,1):4, (6,2,1):1.414, (6,3,1):5.830, (6,4,1):9.219, (6,5,1):1.414,(6,6,1):0, (6,7,1):3.605,
    (7,0,1):0, (7,1,1):2.236, (7,2,1):4.123, (7,3,1):2.236, (7,4,1):5.830, (7,5,1):2.236, (7,6,1):3.605, (7,7,1):0,
    (0,0,2):0, (0,1,2):2.236, (0,2,2):4.123, (0,3,2):2.236, (0,4,2):5.830, (0,5,2):2.236, (0,6,2):3.605, (0,7,2):0,
    (1,0,2):2.236, (1,1,2):0, (1,2,2):5.099, (1,3,2):3.162, (1,4,2):7.280, (1,5,2):3.162, (1,6,2):4, (1,7,2):2.236,
    (2,0,2):4.123, (2,1,2):5.099, (2,2,2):0, (2,3,2):6.325, (2,4,2):9.219, (2,5,2):2,(2,6,2):1.414, (2,7,2):4.123,
    (3,0,2):2.236, (3,1,2):3.162, (3,2,2):6.325, (3,3,2):0, (3,4,2):4.123, (3,5,2):4.472,(3,6,2):5.830, (3,7,2):2.236,
    (4,0,2):5.830, (4,1,2):7.280, (4,2,2):9.219, (4,3,2):4.123, (4,4,2):0, (4,5,2):7.810,(4,6,2):9.219, (4,7,2):5.830,
    (5,0,2):2.236, (5,1,2):3.162, (5,2,2):2, (5,3,2):4.472, (5,4,2):7.810, (5,5,2):0, (5,6,2):1.414, (5,7,2):2.236,
    (6,0,2):3.605, (6,1,2):4, (6,2,2):1.414, (6,3,2):5.830, (6,4,2):9.219, (6,5,2):1.414,(6,6,2):0, (6,7,2):3.605,
    (7,0,2):0, (7,1,2):2.236, (7,2,2):4.123, (7,3,2):2.236, (7,4,2):5.830, (7,5,2):2.236, (7,6,2):3.605, (7,7,2):0}

    tijk ={(0,0,1):0, (0,1,1):2.236, (0,2,1):4.123, (0,3,1):2.236, (0,4,1):5.830, (0,5,1):2.236, (0,6,1):3.605, (0,7,1):0,
    (1,0,1):2.236, (1,1,1):0, (1,2,1):5.099, (1,3,1):3.162, (1,4,1):7.280, (1,5,1):3.162, (1,6,1):4, (1,7,1):2.236,
    (2,0,1):4.123, (2,1,1):5.099, (2,2,1):0, (2,3,1):6.325, (2,4,1):9.219, (2,5,1):2,(2,6,1):1.414, (2,7,1):4.123,
    (3,0,1):2.236, (3,1,1):3.162, (3,2,1):6.325, (3,3,1):0, (3,4,1):4.123, (3,5,1):4.472,(3,6,1):5.830, (3,7,1):2.236,
    (4,0,1):5.830, (4,1,1):7.280, (4,2,1):9.219, (4,3,1):4.123, (4,4,1):0, (4,5,1):7.810,(4,6,1):9.219, (4,7,1):5.830,
    (5,0,1):2.236, (5,1,1):3.162, (5,2,1):2, (5,3,1):4.472, (5,4,1):7.810, (5,5,1):0, (5,6,1):1.414, (5,7,1):2.236,
    (6,0,1):3.605, (6,1,1):4, (6,2,1):1.414, (6,3,1):5.830, (6,4,1):9.219, (6,5,1):1.414,(6,6,1):0, (6,7,1):3.605,
    (7,0,1):0, (7,1,1):2.236, (7,2,1):4.123, (7,3,1):2.236, (7,4,1):5.830, (7,5,1):2.236, (7,6,1):3.605, (7,7,1):0,
    (0,0,2):0, (0,1,2):2.236, (0,2,2):4.123, (0,3,2):2.236, (0,4,2):5.830, (0,5,2):2.236, (0,6,2):3.605, (0,7,2):0,
    (1,0,2):2.236, (1,1,2):0, (1,2,2):5.099, (1,3,2):3.162, (1,4,2):7.280, (1,5,2):3.162, (1,6,2):4, (1,7,2):2.236,
    (2,0,2):4.123, (2,1,2):5.099, (2,2,2):0, (2,3,2):6.325, (2,4,2):9.219, (2,5,2):2,(2,6,2):1.414, (2,7,2):4.123,
    (3,0,2):2.236, (3,1,2):3.162, (3,2,2):6.325, (3,3,2):0, (3,4,2):4.123, (3,5,2):4.472,(3,6,2):5.830, (3,7,2):2.236,
    (4,0,2):5.830, (4,1,2):7.280, (4,2,2):9.219, (4,3,2):4.123, (4,4,2):0, (4,5,2):7.810,(4,6,2):9.219, (4,7,2):5.830,
    (5,0,2):2.236, (5,1,2):3.162, (5,2,2):2, (5,3,2):4.472, (5,4,2):7.810, (5,5,2):0, (5,6,2):1.414, (5,7,2):2.236,
    (6,0,2):3.605, (6,1,2):4, (6,2,2):1.414, (6,3,2):5.830, (6,4,2):9.219, (6,5,2):1.414,(6,6,2):0, (6,7,2):3.605,
    (7,0,2):0, (7,1,2):2.236, (7,2,2):4.123, (7,3,2):2.236, (7,4,2):5.830, (7,5,2):2.236, (7,6,2):3.605, (7,7,2):0}


    V = [0] + P + D +[n+n2+1]
    A = [(i,j) for i in V for j in V]

    m = grb.Model("PDPTW")

    x = m.addVars(A,K, vtype=grb.GRB.BINARY, name="xijk") #BINARY variable, shows if Arc is used =1 or not =0
    Q = m.addVars(V,K, vtype=grb.GRB.CONTINUOUS, name="Qik") #Continous variable, cumulative demand, with upper bound Q
    B = m.addVars(V,K, vtype=grb.GRB.CONTINUOUS, name="Bik")

    m.setObjective(grb.quicksum(grb.quicksum(cijk[(i,j,k)] * x[(i,j,k)] for i,j in A if i!=j if i!=L if j!=0) for k in K), sense=grb.GRB.MINIMIZE) #Objective function, minimizing the distance

    #Every vertex need to be served exactly once
    m.addConstrs(grb.quicksum(grb.quicksum(x[(i,j,k)] for j in V if j!=i if i!=L if j!=0) for k in K)== 1 for i in N)

    #Every vehicle starts and end at the depot
    m.addConstrs(grb.quicksum(x[(i,j,k)] for i,j in A if i==0 and i!=j)==1 for k in K)
    m.addConstrs(grb.quicksum(x[(i,j,k)] for i,j in A if j==L and i!=j)==1 for k in K)

    #Flow conservation Every node has a incoming and outcoming arc
    m.addConstrs((grb.quicksum(x[(i,j,k)] for i in V if i!=j if i!=L) - grb.quicksum(x[(j,i,k)] for i in V if i!=j if i!=0))==0 for j in N for k in K)

    #Subtour elimination
    m.addConstrs(B[(j,k)] + 1000 * (1- x[(i,j,k)]) >= B[(i,k)] + di[i]+ tijk[(i,j,k)] for i,j in A for k in K if j!=i if j!=0 if i!=L)

    #Capacity constraints
    m.addConstrs(Q[(j,k)] + 1000 *(1-x[(i,j,k)]) >= (Q[(i,k)] + qi[j]) for i,j in A for k in K if i!=j if i!=L if j!=0)
    m.addConstrs(Q[(i,k)] >= 0 for i in V for k in K if i!=L)
    m.addConstrs(Q[(i,k)] >= qi[i] for i in V for k in K if i!=L)
    m.addConstrs(Q[(i,k)] <= Ck[k] for i in V for k in K if i!=L)
    m.addConstrs(Q[(i,k)] <= (Ck[k] + qi[i]) for i in V for k in K if i!=L)


    #Every pick up and delivery point are associated
    m.addConstrs((grb.quicksum(x[(i,j,k)] for j in V if i!=j if j!=0) - grb.quicksum(x[(i,j,k)] for j in V if i!=j if j!=0))==0 for i in P for k in K)

    #Delivery can only occur after pickup
    m.addConstrs(B[(i,k)]<= B[(n+i, k)] for i in P for k in K)

    0
  • Roos Vahrmeijer
    Gurobi-versary
    First Comment
    First Question

    Output is as follows:

    Solved in 0.028 secs.

    OPTIMAL
    Objective value: 24.075000000000003
    Used edges:
    0 1 1
    0 4 2
    1 6 1
    2 5 1
    3 7 2
    4 3 2
    5 7 1
    6 2 1

     

    Now delivery takes place before picking up

    0
  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    Hi Roos,

    Ok, so you want to solve a pickup-and-delivery problem with 3 commodities, each with a dedicated source and target node. You have two vehicles, each with capacity 6. The model is called PDPTW but I could not detect any time windows here. Anyway, if you have time windows, you just need to bound the B(i,k) variables.

    Your solution shows that pickup and delivery, e.g., of the first commodity from 1 to 4, is done by different vehicles. If you output the values for the visiting time variables B(i,k), you will see that your last set of constraints is satisfied but still not enough to ensure that one commodity is completely handled by one vehicle. Usually, one uses binary assignment variables y(i,k) to assign the visit of node i to vehicle k. Then, you can state that \( y_{i,k} = y_{i+n,k} \). You also need to use variables y(i,k) in the flow conservation constraints, and you could use them to better bound capacity variables Q and visiting time variables B.

    Note that you should always use the smallest possible BigM value instead of 1000. Here, you could use vehicle capacities and time window bounds (if available).

    Best regards,
    Mario

    0

Please sign in to leave a comment.

Didn't find what you were looking for?

New post