PWL constraints efficiency

Answered

Andre Pistoletov

• January 29, 2022 20:57
• Edited

So, I'm trying to optimize MILP, which has PWL constraints. Without those constraints, gurobi solves model in a matter of seconds. The problem is when I try to add them, performance drops significantly. When I added only 419 out 4072 PWL constraints, gurobi took several minutes two solve the model, and when I added all of them, it couldn't find feasible solution (which must always exist) in several hours. PWL function I use has 11 breakpoints and has no jumps. I can't post all code (there's too much) so here super general outline.

s1 = m.addVars(indices, vtype=GRB.CONTINUOUS, name='s1')
s2 = m.addVars(indices, vtype=GRB.CONTINUOUS, name='s2')

# Some constraints with s1 and s2

c1 = m.addVars(indices, vtype=GRB.CONTINUOUS, name='c1')
c2 = m.addVars(indices, vtype=GRB.CONTINUOUS, name='c2')

for i in range(M):
    for j in range(N):
        m.addGenConstrPWL(s1[i, j], c1[i, j], X, Y)
        m.addGenConstrPWL(s1[i, j], c1[i, j], X, Y)

# also need to add constraints with c1 and c2 in the future

I also need too add constraints with `c1`, `c2` variables to the model.

So my question is it expected that PWL constraints would cause such a drop in performance, and can I do something to improve it?

 

 

0

• 

  Jaromił Najman

  Gurobi Staff

  • January 31, 2022 13:11

  It highly depends on the complexity of the PWL functions you use. In general, one can say that using PWL formulations to approximate nonlinear makes the final MIP problem harder. Thus, it is expected that when you add multiple hundreds of PWL constraints, that the model gets harder and harder to solve. Note that each breakpoint adds at least one binary variable to the model.

  Are you approximating some specific functions? Do these functions have a common structure which you might exploit?

  Best regards, 
  Jaromił

  0
• 

  Andre Pistoletov

  • January 31, 2022 19:47

  

  

  

  Hi Jaromił Najman. Thank you for the reply!

  In general all PWL constraints are divided between 1-5 functions. These functions look like so:

  

  

   

  0
• 

  Jaromił Najman

  Gurobi Staff

  • February 01, 2022 08:36
  • Edited

  Hi Andre,

  The upper functions are nonconvex functions explaining the increase in complexity. From a modeling point of view, you could try using less breakpoints on the right side of the functions where they tend to be flat. Reducing the number of breakpoints might results in a performance boost.

  The lower functions look like they could be modeled via concave quadratic functions. You could use quadratic terms instead of a PWL approximation which might again improve performance.

  In general, you could pick a smaller version of your model which takes ~5 - 10 minutes to solve and use Gurobi's automatic tuning tool to find parameters which might improve performance. I would run the tuner for 1 - 2 days and see whether it was able to find some parameters to improve your model's performance.

  Best regards, 
  Jaromił

  0

Please sign in to leave a comment.