[Math] Convert non-linear into linear

linear algebralinear programmingnonlinear optimizationoperations researchoptimization

enter image description here


What I tried:

Let

$$u_1 = x_1^3$$

$$u_2 = x_2 x_3$$

$$u_3 = x_3^3$$

Then we have $z = u_1 + u_2 + u _3$

s.t.

  1. $1 \le u_3 \le 343$

  2. $u_3^{1/3}$ should be integer

  3. $u_1 \in \{0, 1\}$

  4. $u_2 \in \{0, u_3^{1/3}\}$

Is that right?

If so, it seems like we split up the original non-LP into 4 LPs based on constraints #3 and #4. In each of the 4 LP's, z becomes an increasing function of $u_3$ only. Therefore, we pick $u_3 = 343$ in the case that $u_2 = u_3^{1/3}$ and $u_1 = 1$.

Is that right?


From one of these files

Best Answer

Since $x_1$ is binary, $u_1=x_1^3$ is also binary: $$ u_1\in \{0,1\} $$

Since $x_2$ is binary, $x_3$ is integer and $1\le x_3\le 7$, $u_2=x_2x_3$ can take values among the set $\{0,2,3,4,5,6,7\}$. So you need to define new binary variables $y_i$ that equal $1$ if and only if $u_2$ takes value $i\in \{0,1,2,3,4,5,6,7\}$: $$ u_2=0y_0+y_1+2y_2+3y_3+4y_4+5y_5+6y_6+7y_7, $$ and you need to force $u_2$ to take exactly one of this values: $$ y_0+y_1+y_2+y_3+y_4+y_5+y_6+y_7=1\\ y_i\in \{0,1\}\quad \forall i=0,\cdots,7 $$

Since $x_3$ is integer and $1\le x_3\le 7$, $u_3=x_3^3$ can take values among the set $\{1^3,\cdots,7^3\}$. With the same logic: $$ u_3=z_1+\cdots+7^3z_7\\ z_1+\cdots+z_7=1\\ z_i\in \{0,1\}\quad \forall i=1,\cdots,7 $$

Related Question