# What is the class of this Integer programming prob.

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

• 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$). – Erwin Kalvelagen Apr 25 '16 at 8:40
• yes, it was actually $\leq$. Anyway, $r_i$ is a kind of cost, and $R$ is the total constant budget. – Farzad Apr 25 '16 at 8:48

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.