Getting rid of non-linearities

In [1], an attempt was made to implement the following non-linear constraint: $$\frac{\displaystyle\sum_t \max\left\{\sum_i CF_{i,t}\cdot q_i -L_t, 0 \right\}}{\displaystyle\sum_t L_t} \le 0.015$$ Obviously code like:

 

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

is really not what we want to see. It is best, not to directly start up your editor and write Python code like this. Rather, get a piece of paper, and focus on the math.

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

1. Piecewise Linear Function as Constraint, https://stackoverflow.com/questions/72026948/piecewise-linear-function-as-constraint