Skip to main content

Problem with gurobi default setting for piecewise linear function

Answered
Thanh Phong Pham
Conversationalist
First Question

Hello,

I'm using this piecewise linear function in gurobi.

for i in range(N+1):
        for k in range(M):
            m.addGenConstrPWL(q[i,k],u[i,k],u_axis_x,u_axis_y)
        for k in range(M):
            m.addGenConstrPWL(q[i,k],v[i,k],v_axis_x,v_axis_y)
 
And I encounter a problem that is when the points in the piecewise linear function are too close to each other, the terminal flags out this error.
 
gurobipy.GurobiError: more than three points for PWL constraint have (almost) the same x values
 
What I understand is that the default setting does not allow points that are too near to each other. Can I ask is there anyway to change this default setting as allowing very small distance between points are very important for my model performance?

Related to

0

Comments

12 comments

Date Votes
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Thanh,

    What I understand is that the default setting does not allow points that are too near to each other. Can I ask is there anyway to change this default setting as allowing very small distance between points are very important for my model performance?

    The reason for not allowing points that are too close to each other on the x-axis is that this often leafs to wrong numerical behavior. Especially, when the difference in x-axis values are close or even less than the feasibility tolerance. There is currently no way to avoid this except for spreading out the x-axis points more.

    What kind of function are you approximation such that you need the x values to be so close to each other?

    Best regards, 
    Jaromił

    0
  • Thanh Phong Pham
    Conversationalist
    First Question

    Hello Jaromil, 

    Thank you for replying to my request!

    The piecewise linear approximation I need to put in Gurobi model is of function ln(x). Since x cannot take 0 as a starting point, I need to set the starting point to be a very small number (around 1e-10). But since ln(x) is very steep in initial part, the approximation needs x-coordinates that are very close to each other. 

    If I cannot set very small starting point, my model performance will be really bad. 

    It would be great if you can think of any ways to deal with this problem, maybe somehow change the default feasibility tolerance.

    Best regards,

    Phong

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Phong,

    The piecewise linear approximation I need to put in Gurobi model is of function ln(x). Since x cannot take 0 as a starting point, I need to set the starting point to be a very small number (around 1e-10). But since ln(x) is very steep in initial part, the approximation needs x-coordinates that are very close to each other. 

    If I cannot set very small starting point, my model performance will be really bad. 

    It would be great if you can think of any ways to deal with this problem, maybe somehow change the default feasibility tolerance.

    In this case, I recommend to upgrade to Gurobi v11 and use the new MINLP feature, where you don't have to use a static PWL approximation of nonlinear functions, see the Section Function Constraints With Dynamic Piecewise-Linear Approximation of General Constraints documentation. The API remains exactly the same as for general constraint via PWL approximation, i.e., you can use the addGenConstrLog method to implement the natural logarithm. You only have to set the FuncNonlinear parameter to 1.

    I would recommend to have a look at our What's New in Gurobi 11.0? webinar.

    Best regards, 
    Jaromił

    0
  • Thanh Phong Pham
    Conversationalist
    First Question

    Hi Jaromil,

    Thank you for the suggestion, I used the new feature and it was very efficient. If I use the static piecewise-linear approximation, is there any way I can access the details about how many pieces was use and the list of pieces? And what algorithm Gurobi used to find the piecewise-linear approximation?

    Best regards,

    Phong

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Phong,

    And what algorithm Gurobi used to find the piecewise-linear approximation?

    There are two different approaches for a PWL approximation. A static one, where a PWL approximation is computed once and is not altered during the optimization process and a dynamic one, where a PWL approximation is computed and altered in every B&B node.

    If I use the static piecewise-linear approximation, is there any way I can access the details about how many pieces was use and the list of pieces?

    The static piecewise-linear approximation is controlled by the parameters FuncPieces, FuncPieceRatio, FuncPieceError, and FuncPieceLength. There is currently no way to get the information on how many pieces were actually used or to get the list of pieces. The algorithm used to compute the static piecewise-linear approximation tries to keep the maximum error between the given function and the PWL approximation below the threshold given by FuncPieceError. If you want achieve better accuracy, you might need to either reduce the FuncPieceError value or increase the FuncPieces value. This often comes with a performance cost. In that case, I would recommend to stick with the dynamic PWL approximation.

    Note that the above parameters do not have any effect on the dynamic PWL approximation activated by FuncNonlinear=1. The dynamic PWL approximation uses the spatial B&B algorithm and computes a linear outer approximation of each nonlinear function in every B&B node. The outer approximation gets tighter with shrinking variable domain.

    Best regards, 
    Jaromił

    0
  • Thanh Phong Pham
    Conversationalist
    First Question

    Hi Jaromil,

    Thank you for the explanation.

    I just have one last question. For the dynamic PWL, I don't have any control over the FuncPieceError right? Is there any default settings of dynamic PWL about how tight is the approximation or how tight is the approximation when the variable domain becomes smaller?

    Best regards,

    Phong

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Phong,

    I just have one last question. For the dynamic PWL, I don't have any control over the FuncPieceError right?

    Correct.

    Is there any default settings of dynamic PWL about how tight is the approximation or how tight is the approximation when the variable domain becomes smaller?

    This is not needed. The approximation is guaranteed to get tight enough with shrinking node domains to fulfill constraint tolerances. Thus, there is no need to statically set some error tolerance.

    Best regards, 
    Jaromił

    0
  • Thanh Phong Pham
    Conversationalist
    First Question

    I see.

    So for example, if the function ln(x) I want to approximate starts from 1e-20, does Gurobi actually takes 1e-20 as a starting point, or it will take some thing like 1e-5?

    Best regards,

    Phong

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff
    • Edited

    So for example, if the function ln(x) I want to approximate starts from 1e-20, does Gurobi actually takes 1e-20 as a starting point, or it will take some thing like 1e-5?

    The minimum value used for x when computing a PWL approximation for ln(x) is 1e-10. This holds for both, static and dynamic approximation. The reason is numerical, the derivative of ln(x) at 1e-10 is already 10^10, which can lead to all sorts of numerical trouble.

    If you want values < 1e-10 to be considered for x, you could try working with exp instead, y = ln(x) <=> exp(y) = x. Note that if a change in x from 1e-10 to 1e-20 is important for your application, which can easily be the case, because the value of ln(x) changes by a lot, then you should try to re-scale the input x. Otherwise, there is no guarantee that a numerical algorithm can provide you a solution that is close to an exact solution.

    Best regards, 
    Jaromił

    0
  • Thanh Phong Pham
    Conversationalist
    First Question

    Thank you! 

    Does re-scaling input x means doing some manipulation on x (for example times x with a very big number)?

    Best regards,

    Phong

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Does re-scaling input x means doing some manipulation on x (for example times x with a very big number)?

    The problem here is, in order to move your x from 1e-20, you would have to multiply it by 1e10 which leads to different numerical issues. So just multiplying x by a very big number is not a good idea.

    To re-scale an input x, it is best to change its units. For example using grams instead of kilograms leads to a scaling factor of 1000, so a 0.001 kilogram would be 1 gram.

    Another way would be a reformulation. As proposed in my previous comment, you could formulate exp(y) = x instead of y = log(x).

    For more details on numerics, I recommend having a look at our Guidelines for Numerical Issues.

    Best regards, 
    Jaromił

    0
  • Thanh Phong Pham
    Conversationalist
    First Question

    Hello Jaromil,

    It is a good suggestion. Thank you for supporting me!

    Best regards,

    Phong

    0

Please sign in to leave a comment.

Didn't find what you were looking for?

New post