Convert non-linear equation to linear equation

linear programminglinearizationmixed-integer programmingoptimization

I have a problem with X machines, each one with a specific production. All the production needs to be sent to an specific place via different routes which may or may be not cheaper.

I need to minimize the cost of sending all the resulting product, but for each shipment the tons of product sent needs to be greater than 15% of the total production for that machine.

$$0.15 P_i B_{i,j} \le S_{i,j} \le 4000 B_{i,j} $$
where $P_i$ is the total production for the machine $i$. $S_{i,j}$ are the tons shipped by the machine $i$ by route $j$, $B_{i,j} \in \{0,1\}$ which indicates if the machine $i$ uses the route $j$ and $4000$ is the maximum production for each machine.

I need to multiply the binary variable with the production to make the statement correct, because if $S_{i,j} = 0$ because it doesn't use the route $j$
$$0.15P_i \not\le 0$$

Best Answer

You want to enforce $$B_{i,j} = 0 \implies S_{i,j} = 0$$ and $$B_{i,j} = 1 \implies 0.15 P_i \le S_{i,j} \le 4000$$ You can do so via linear big-M constraints, where $U_i$ is a small constant upper bound on $P_i$: \begin{align} 0 \le S_{i,j} &\le 4000 B_{i,j} \\ 0.15 P_i - S_{i,j} &\le 0.15 U_i(1-B_{i,j}) \end{align}

Related Question