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