How do i solve two non linear constraints that depend on one another?

回答済み

Gatta Siddhartha kaushik

2023年04月24日 13:11

• 
• 

I am trying to solve two non linear constraints, although i didn't get the model as infeasible but still it is taking a lot of time to solve the model.

These are the constraints that i was talking about, and here both the numberators are given as input and "q" ,"omega" and "h_time" are variables. i am also attaching their respective code and output.

for s in range(n):
    for t in range(time):
        k=(gp.quicksum((wsgt[s][g][t]*time_c[g,t])for g in range(group)))
        m.addConstr(h_time[s]*qc[s,t]-k==0,name="Constraint5_{}_{}".format(s,t))
for t in range(time):
    p=m.addVars(time,lb=0,vtype=GRB.CONTINUOUS)
    p[t]=gp.quicksum(gt[g,t]for g in range(group))
for s in range(n):
    for t in range(time):
        l=gp.quicksum(wsgt[s][g][t] for g in range(group))
        m.addConstr(qc[s,t]*p[t]==l,name="Constraint6_{}_{}".format(s,t))

This is the code i wrote for the two constraints and here as i mentioned earlier wsgt & time_c are input parameters and 'h_time'& 'gt' are continuous variables and , 'qc' is integer variable. 

 1517957 1045365 infeasible  399      509999.638 483000.000  5.29%   0.9 4310s
 1523734 1049805 486000.000  217    8 509999.638 483000.000  5.29%   0.9 4315s
 1530671 1056023 486000.000  305   29 509999.638 483000.000  5.29%   0.9 4320s
 1536248 1060315 498000.000  459    4 509999.638 483000.000  5.29%   0.9 4325s
 1542657 1063636 486000.000  183    8 509999.638 483000.000  5.29%   0.9 4330s
 1548299 1067576 infeasible  455      509999.638 483000.000  5.29%   0.9 4335s
 1554847 1072829 486000.000  276    8 509999.638 483000.000  5.29%   0.9 4340s
 1560395 1076102 486000.000  348    8 509999.638 483000.000  5.29%   0.9 4345s
 1567160 1081786 486000.000  406    8 509999.638 483000.000  5.29%   0.9 4350s
 1572850 1085397 486000.000  385    8 509999.638 483000.000  5.29%   0.9 4355s
 1579561 1091017 486000.000  257    8 509999.638 483000.000  5.29%   0.9 4361s
 1585252 1096011 486000.000  265   26 509999.638 483000.000  5.29%   0.9 4366s
 1588695 1098390 486000.000  411   26 509999.638 483000.000  5.29%   0.9 4370s
 1594855 1103171 486000.000  392   29 509999.638 483000.000  5.29%   0.9 4375s
 1599505 1105941 infeasible  366      509999.638 483000.000  5.29%   0.9 4380s
 1605830 1110819 501000.000  480    3 509999.638 483000.000  5.29%   0.9 4385s

 

This is the output after m.optimize() as you can see the GAP is not decreasing but still it is taking a lot of time also this particular instance is very small compared to other instances that i need to run. please help me to solve this problem so i can make the code run faster or any other way to write the constraints so it will take less time.

Thanks in advance,

Gatta Siddhartha Kaushik

0

• 

  Jaromił Najman

  • Gurobi Staff

  2023年04月25日 07:26

  Hi Gatta,

  Your implementation is correct and the behavior you see is not unusual. The constraints you modeled are nonconvex and high dimensional. Still, maybe there is something to improve here.

  You set the lower bound of your \(\texttt{p}\) variables to \(0\).

  p=m.addVars(time,lb=0,vtype=GRB.CONTINUOUS)

  Theoretically, you allow for division by \(0\). Your formulation does not allow for it because you use multiplication but you are actually interested in the division. If you are sure that at least one of the \(\texttt{p}\) variables is strictly \(> 0\), then it is usually OK and should not lead to numerical difficulties. However, there are cases where it might be beneficial to actually provide a strictly positive lower bound.

  You definitely should provide tight finite upper bounds for all variables. Relaxing constraints of the type you present without bounds (or very loose bounds) is often not possible and results in a vast B&B tree. It would be best if you can derive some tight valid bounds from the application you are modeling and it would be even better if you can tighten these bounds even further manually by some specific problem knowledge.

  You could try eliminating the constraint

  m.addConstr(qc[s,t]*p[t]==l,name="Constraint6_{}_{}".format(s,t))

  by substituting \(\texttt{qc[s,t]}\) into

  m.addConstr(h_time[s]*qc[s,t]-k==0,name="Constraint5_{}_{}".format(s,t))

  which would give

  m.addConstr(h_time[s]*p[t]-k*l==0,name="Constraint_new_{}_{}".format(s,t))

  Here, there are multiple options to consider. You could drop constraints 5 and 6 and only use the new constraint. You could also drop only one of the constraints and add the new constraint or you could keep both constraints 5 and 6 and add the additional nonconvex new constraint. It is hard to tell which option would perform best here so it is something you could experiment with.

  There is also an alternative where you use constraint 5 to substitute \(\texttt{qc[s,t]}\) into constraint 6 to get

  m.addConstr(k*p[t]==l*h_time[s],name="Constraint_new2_{}_{}".format(s,t))

  There is quite a bit to experiment here but nothing can be said a priori about the performance of each reformulation.

  I hope this helps.

  Best regards, 
  Jaromił

  0

サインインしてコメントを残してください。