How to implement a linear approximation?
AnsweredHello, I have the following question. I would like to implement a non-linear relationship in my model as a linear approximation. I want to approximate this function linearly.
\(c_{i} = \exp^{-0.5\times d_{i}}\)
How would I implement this linear Approximation. It looks like this in my model:
for i in range(n):
m.addConstr(c[i] == math.exp(-0.5 * d[i]))
-
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:-
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. -
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. -
Calculating Segment Slopes and Intercepts: For each segment, calculate the slope and intercept that best approximates the exponential function over that segment.
-
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 -
-
Hey bot! Couldn't you use Model.addGenConstrExp()?
0 -
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 -
Ed Rothberg Thanks for your answer. How exactly would the code for the latter approach look like in my case?
0 -
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 -
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 -
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 -
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 -
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 -
Matthias Miltenberger Thanks for clarification. What exactly do you mean by tightening the bounds? How would i accomplish that?
0 -
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.
0
Please sign in to leave a comment.
Comments
11 comments