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$.

  • $\begingroup$ Yes. Probably can be linearized. We don't know much about $r_i$ (and $R$). Further < is usually not an appropriate type of equation (both in practice and from a theoretical point of view we much more prefer $\le$). $\endgroup$ – Erwin Kalvelagen Apr 25 '16 at 8:40
  • $\begingroup$ yes, it was actually $\leq$. Anyway, $r_i$ is a kind of cost, and $R$ is the total constant budget. $\endgroup$ – Farzad Apr 25 '16 at 8:48

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.