Skip to main content

Quadratic function to linear function in gurobi.

Answered
Eleonora Pribadi
Edited
  • Gurobi-versary
  • First Comment
  • First Question

hii, I have this constraint to my model

 

for client in cl: 
     for warehouse in wl: 
           for types in sl:  
                 m.addConstr(select[warehouse,types]<= assign[warehouse,client,types])

but when I optimize with gurobi, the result is infeasible. then, I changed to this one 

for client in cl: 
     for warehouse in wl: 
           for types in sl:                                       
                  m.addConstr(select[warehouse,types]*flow[warehouse,client] <= flow[warehouse,client]*assign[warehouse,client,types])

and the result come,, is there any possible way to delete flow[warehouse,client], because it's redundant. I think it won't come without it, because if the flow value is 0, then the other stuff will follow.

 

0

Comments

5 comments

Date Votes
  • Official comment
    Simranjit Kaur
    • Gurobi Staff
    Edited
    This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
  • Jaromił Najman
    • Gurobi Staff

    Hi Eleonora,

    It is only valid to remove \(\texttt{flow[warehouse,client]}\) if it is guaranteed to be \(\neq 0\). Note that if \(\texttt{flow[warehouse,client]}\) is negative, you have to flip the constraint sense. If you have additional information about the \(\texttt{flow}\) variable for specific \(\texttt{(warehouse,client)}\) combinations, you may simplify these quadratic constraints to linear constraints.

    Best regards,
    Jaromił

    1
  • Eleonora Pribadi
    • Gurobi-versary
    • First Comment
    • First Question

    Thank you Jaromil, 

     

    the flow[warehouse,client]  it's a continuous number. I put this one in my code. 

    for warehouse in wl:
         for client in cl:
               flow[warehouse,client] = m.addVar(vtype=GRB.CONTINUOUS, name = f'flow({warehouse},{client})')

               z[warehouse,client] = m.addVar(vtype= GRB.BINARY, name = f'z({warehouse},{client})')

    for warehouse in wl: 
         for client in cl:                                      
              flow[warehouse,client] = m.addVar(vtype=GRB.CONTINUOUS, name = f'flow({warehouse},{client})')
              z[warehouse,client] = m.addVar(vtype= GRB.BINARY, name = f'z({warehouse},{client})')


    while the select[warehouse,types] is a binary variable, and assign [warehouse,client] is data. 

    I wonder, if I can remove the flow[warehouse,types] with the z[warehouse,client] above, with condition z[warehouse,client]=0 when flow = 0, and z[warehouse,types]=1 when flow>=0 

    and keeping this constraint 

    for client in cl: 
         for warehouse in wl: 
               for types in sl:  
                     m.addConstr(select[warehouse,types]<= assign[warehouse,client,types])

     

    Regards,

    Eleonora

    0
  • Jaromił Najman
    • Gurobi Staff
    Edited

    Hi Eleonora,

    I don't fully understand the usage of the \(z\) variable. Do you mean that you would replace \(\texttt{flow}\) by \(z\) with the two conditions you describe? Please note that the multiplication of a binary variable with a continuous variable can be modeled with the use of linear inequalities only. The stackexchange post How to linearize the product of a binary and a non-negative continuous variable? might catch your interest.

    Is it possible that some of the \(\texttt{assign}\) data is negative causing the infeasibility? This would at least explain why you have to multiply the inequality constraint by the continuous positive variable \(\texttt{flow}\) in order to obtain feasibility.

    In order to better track the source of infeasibility, you could compute an IIS using the ComputeIIS() function and then analyze the set of infeasible constraints. The Knowledge Base article How do I determine why my model is infeasible? might come in handy.

    Best regards,
    Jaromił

    0
  • Eleonora Pribadi
    • Gurobi-versary
    • First Comment
    • First Question

    Thank you Jaromil,

    Yes, I think that the z could replace the flow. but I tried, and it doesn't work. 

    assign is binary 1,0. so it won't make the value become 0. 

    I think if the flow ==0, it will make the objective become 0. 

    Decision Variable: 

    #Define decision variables
    for warehouse in wl:
        for types in sl:
            select[warehouse,types]= m.addVar(vtype= GRB.BINARY, name = f'select({warehouse},{types})')

    for warehouse in wl: 
        for client in cl:
            flow[warehouse,client] = m.addVar(vtype=GRB.CONTINUOUS, name = f'flow({warehouse},{client})') 
            z[warehouse,client] = m.addVar(vtype= GRB.BINARY, name = f'z({warehouse},{client})') 

    for types in sl: 
        for warehouse in wl: 
            obj1.addTerms(d_warehouse_type['Fixed Investment Cost'][types],
                         select[warehouse,types])
    for warehouse in wl:
        for client in cl: 
            obj2.addTerms(d_distances[warehouse][client]*cost, flow[warehouse,client])
       
    obj= obj1+obj2
    m.setObjective(obj.GRB.MINIMIZE)

    Here is my constraint

    #total warehouse facility equal to 1
    for warehouse in wl:
        m.addConstr(quicksum(select[warehouse,types] for types in sl) <= 1 )


    for client in cl: 
        m.addConstr(quicksum(flow[warehouse,client] for warehouse in wl) == d_market_demand['Demand'][client])


    for warehouse in wl:
        m.addConstr(quicksum(flow[warehouse,client] for client in cl) <= quicksum(select[warehouse,types]*d_warehouse_type['Capacity'][types] for types in sl) )

    The redundant Constrain

    for client in cl: 
         for warehouse in wl: 
               for types in sl:                                       
                      m.addConstr(select[warehouse,types]*flow[warehouse,client] <= flow[warehouse,client]*assign[warehouse,client,types])

    Well, I'm not sure which part will make it become infeasible. 

     

    Thank you so much for your help.

    Sincerely,

    Eleonora

     

    0

Post is closed for comments.

Didn't find what you were looking for?

New post