Skip to main content

How to implement a linear approximation?

Answered

Comments

11 comments

  • Gurobot (AI-generated response)
    Gurobi Staff Gurobi Staff

    Given the specific function c[i] == math.exp(-0.5 * d[i]), you're dealing with an exponential decay function, which is inherently non-linear. To approximate this function linearly in a Gurobi model, there are a few steps you can follow:

    1. Piecewise Linear Approximation: The most common method to linearize a non-linear function like yours is to use a piecewise linear approximation. This involves breaking the range of your variable d[i] into segments and approximating the exponential function with a series of linear segments within each range.

    2. Defining Segments: Determine the range of your d[i] variable and divide it into segments. The more segments you use, the more accurate your approximation will be, but this will also increase the complexity of the model.

    3. Calculating Segment Slopes and Intercepts: For each segment, calculate the slope and intercept that best approximates the exponential function over that segment.

    4. Implementing in Gurobi: Use Gurobi's addGenConstrPWL method to add a piecewise linear constraint to your model. This method allows you to specify the breakpoints of your segments and the corresponding function values.

    Here is an example of how you could implement this in your Gurobi model:

    import gurobipy as gp
    from gurobipy import GRB

    # Assuming you have already defined your model 'm' and your variables 'c' and 'd'
    breakpoints = [0, 1, 2, 3, ...] # Define your breakpoints here
    function_values = [math.exp(-0.5 * d) for d in breakpoints] # Calculate the function values at the breakpoints
    for i in range(n):
    m.addGenConstrPWL(d[i], c[i], breakpoints, function_values)

    This is a simplified example. You'll need to adjust the breakpoints and function values based on the specific range and accuracy needs of your model.

    Remember that this is an approximation, and the accuracy will depend on the number and placement of your breakpoints. It's often a good practice to analyze the trade-off between the model's complexity and the accuracy of the approximation.

    0
  • Robert Fourer
    Collaborator
    Gurobi-versary

    Hey bot! Couldn't you use Model.addGenConstrExp()?

    0
  • Ed Rothberg
    Gurobi Staff Gurobi Staff

    Yes, it seems that some of our recent non-linear features came after the AI's cut off date.

    You can use Model.addGenConstrExp() to do an automatic piecewise-linear approximation or a dynamic outer approximation (by setting the FuncNonLinear parameter to 1).  The latter will give you a more accurate solution, and is often faster.

    0
  • Nico T
    Conversationalist
    First Question

    Ed Rothberg  Thanks for your answer. How exactly would the code for the latter approach look like in my case?

    0
  • Matthias Miltenberger
    Gurobi Staff Gurobi Staff

    Hi Nico,

    Here's one way to do it:

    t = {}
    for
    i in range(n):
    t[i] = m.addVar()
    m.addConstr(t[i] == -0.5 * d[i]) m.addGenConstrExp(t[i], c[i], options="FuncNonlinear=1"
    )

    You may want to pass additional arguments to the addVar() method to define the new auxiliary variable t better.

    0
  • Nico T
    Conversationalist
    First Question

    Matthias Miltenberger Thank you for your answer. That helped me a lot. I am also trying to implement this function, but am currently failing. Could you possibly help me here again?

    \(c_i = 1 - 1/(1+e^{-(d_i-5)})\)

    Thank you very much

    0
  • Matthias Miltenberger
    Gurobi Staff Gurobi Staff

    This guide should help you out regarding the division: How do I divide by a variable in Gurobi? – Gurobi Help Center

    In general, you often need to split up your mathematical constraint into smaller terms and introduce auxiliary variables to represent them.

    0
  • Nico T
    Conversationalist
    First Question

    Matthias Miltenberger Would this be the correct way? I am not able to test it right now?

    for i in I:
    breakpoints = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    slopes = [0] + [-math.exp(-(5-x)) for x in breakpoints[1:]]
    m.addGenConstrPWL(g[i], n[i], breakpoints, slopes, name="pwl")
    m.addConstr(p[i] * (1 + g[i]) == 1 , name="link")
    0
  • Matthias Miltenberger
    Gurobi Staff Gurobi Staff

    Seems OK to me, except that the exponent should be exp(5-x) to match your mathematical equation. Please note that you should also specify tight bounds to all your variables to improve the solver's performance.

    0
  • Nico T
    Conversationalist
    First Question

    Matthias Miltenberger Thanks for clarification. What exactly do you mean by tightening the bounds? How would i accomplish that?

    0
  • Matthias Miltenberger
    Gurobi Staff Gurobi Staff

    When modeling nonlinear problems, you should always make sure that the variables that taking part in nonlinear constraints have predefined bounds that are as tight as possible. This reduces the domains of the variables and therefore also the range of the constraints.

    You can set bounds via the variables' attributes LB and UB.

    0

Please sign in to leave a comment.