cfm = quicksum( max(quicksum(cf[i][t] * q[i] - L[t] for i in range(I)), 0) for t in range(T) / quicksum(L[t] for t in range(T)) <= 0.015
There are two non-linearities: a division and a \max() function. Note that I am not sure which symbols are variables or parameters. I'll try to explain some possible cases below.
Division
Exogenous divisions of the form \frac{\color{darkred}x}{\color{darkblue}a} where \color{darkblue}a is a constant, are not an issue. This is just really a linear coefficient 1/\color{darkblue}a. If you have \frac{\color{darkred}x}{\sum_i \color{darkblue}a_i} in the constraints, I would advice to calculate \color{darkblue}\alpha :=\sum_i \color{darkblue}a_i in advance, so we can simplify things to \frac{\color{darkred}x}{\color{darkblue}\alpha} It is a good habit to keep constraints as simple as possible, as they are more difficult to debug than parameter assignments.
If we have something like \frac{\color{darkred}x}{\color{darkred}y} (endogenous division) we need to be careful and worry about division by zero (or, more generally, that the expression can assume very large values if \color{darkred}y \approx 0). If \color{darkred}y is a positive variable, we can protect things a bit by using a lower bound, say \color{darkred}y\ge 0.0001. This is difficult to do if \color{darkred}y is a free variable (we want a hole in the middle). If we have \frac{\color{darkred}x}{\sum_i\color{darkred}y_i} it may be better to write this as: \begin{align}&\frac{\color{darkred}x}{\color{darkred}z}\\ & \color{darkred}z= \sum_i \color{darkred}y_i \\ &\color{darkred}z\ge 0.0001 \end{align} at the expense of an extra variable and constraint. It has the additional advantage of making the model less non-linear (fewer non-linear variables, smaller non-linear part of the Jacobian). Note that we assumed here that \sum_i\color{darkred}y_i \ge 0. If this expression can assume both negative and positive values, this will not not work.
If the division is not embedded in other non-linear expressions, we often can multiply things out. E.g. if we have the constraint: \frac{\color{darkred}x}{\sum_i\color{darkred}y_i} \le 0.015 then we can write: \color{darkred}x \le 0.015 \cdot \sum_i\color{darkred}y_i This is now linear. This is what can apply to our original constraint:\sum_t \max\left\{\sum_i CF_{i,t}\cdot q_i -L_t, 0 \right\} \le 0.015\cdot \sum_t L_t
Max function
We can feed \max\{\color{darkred}x,0\} to a general-purpose NLP solver. However, this is dangerous. Although this function is continuous, it is non-differentiable at \color{darkred}=0.
In the special case \max\{\color{darkred}x,0\} \le \color{darkred}y we can write: \begin{align} \color{darkred}x &\le \color{darkred}y \\ 0 & \le \color{darkred}y\end{align} If \color{darkred}y represents an expression, you may want to use an extra variable to prevent duplication.
If we have \sum_i \max\{\color{darkred}x_i,0\} \le \color{darkred}y we can do: \begin{align} & \color{darkred}z_i \ge 0 \\ & \color{darkred}z_i \ge \color{darkred}x_i \\ &\sum_i \color{darkred}z_i \le \color{darkred}y \end{align} Note that the variables \color{darkred}z_i are a bit difficult to interpret. They can be larger than \max\{\color{darkred}x_i,0\} if the inequality is not tight. The reason I use \color{darkred}z_i \ge \max\{\color{darkred}x_i,0\} is that it is sufficient for our purpose and that \color{darkred}z_i = \max\{\color{darkred}x_i,0\} is just way more difficult to represent.
This is the reformulation we can apply to our original problem: \begin{align}&z_t \ge \sum_i CF_{i,t}\cdot q_i -L_t \\ & z_t \ge 0 \\ & \sum_t z_t \le 0.015\cdot \sum_t L_t \end{align} This is now completely linear: we have removed the division and the \max(.,0) function.
References
- Piecewise Linear Function as Constraint, https://stackoverflow.com/questions/72026948/piecewise-linear-function-as-constraint
No comments:
Post a Comment