I have an optimization problem which seems to be non-linear because of the constraints (right?):
$max (\sum U_i\times x_i)\\ \sum x_i\times y_i\times r_i\leq R\\ \sum y_i=1\\ \sum x_i=1\\ x_i, y_i\in \{0,1\}$
The variables are ($r_i, x_i, y_i$), while $r_i$ is a kind of cost whose overall value must be less than or equal to the constant budget, $R$.
Recipe to linearize this (part of the) model:
Step 1. Linearize $z_i = x_i y_i$: $$ \begin{align} z_i &\le x_i \\ z_i &\le y_i \\ z_i &\ge x_i+y_i-1\\ z_i &\in \{0,1\} \>\text{(binary variable)} \end{align} $$ Step 2. Linearize $q_i = x_i y_i r_i$: We assume $r_i\ge 0$. Furthermore assume $r_i \le u_i$ (i.e. $u_i$ is an upper bound on $r_i$).We can reuse the above linearization and say $q_i = z_i r_i$. This equation can be linearized as: $$ \begin{align} q_i & \le u_iz_i \\ q_i & \le r_i \\ q_i & \ge r_i-u_i(1-z_i) \\ q_i &\in [0,u_i] \> \text{(continuous variable)} \end{align} $$ Step 3: use $q_i$ in the budget equation: $$ \sum_i q_i \le R $$
Now we have a straight MIP model again. Depending on the rest of the model (there must be other stuff otherwise we just can set $r_i=0$) we can simplify this further.