# Linear programming: extending problems yields non linearity

I had a linear programming problem with the following objective function

$$f(x) = \sum_{j}x_jq_jp_j - \sum_{i}\left(\sum_{j}x_jq_jC_{ij} \right) c_i$$

Where $$q, p, C, c$$ are known. Let the term within parentheses be called $$A_i$$

I then had three buckets to represent

$$c_i = \begin{cases} 10 & \text{for } 0\leq A_i\leq 100\\ 8 & \text{for } 101\leq A_i\leq 200\\ 6 & \text{for } A_i \geq 201 \end{cases}$$

The solution (provided by RobPratt) was given as follows:

Here are the details of your suggested approach. Let binary variable $$y_{i,b}$$ indicate whether $$A_i$$ is in bucket $$b$$, where $$b\in\{1,2,3\}$$. Let $$M_i$$ be a (small) upper bound on $$A_i$$. The constraints are: $$\sum_{b=1}^3 y_{i,b} = 1\\ 10 y_{i,1} + 8 y_{i,2} + 6 y_{i,3} = c_i\\ 0 y_{i,1} + 101 y_{i,2} + 201 y_{i,3} \le A_i \le 100 y_{i,1} + 200 y_{i,2} + M_i y_{i,3}$$ The resulting model then has a quadratic function $$\sum_i A_i c_i$$ in the objective.

You can instead get a linear objective by introducing a variable $$z_i$$ to represent $$A_i c_i$$, with constraints: $$\sum_{b=1}^3 y_{i,b} = 1\\ 0 y_{i,1} + 101 y_{i,2} + 201 y_{i,3} \le A_i \le 100 y_{i,1} + 200 y_{i,2} + M_i y_{i,3}\\ -M_{i,1}(1-y_{i,1}) \le z_i - 10 A_i \le M_{i,1}(1-y_{i,1})\\ -M_{i,2}(1-y_{i,2}) \le z_i - 8 A_i \le M_{i,2}(1-y_{i,2})\\ -M_{i,3}(1-y_{i,3}) \le z_i - 6 A_i \le M_{i,3}(1-y_{i,3})\\$$ The resulting model then has a linear function $$\sum_i z_i$$ in the objective.

This worked perfectly. I now want to further extend the problem to the case where $$A_i$$ not only depends on the summation but is multiplied by some correction factor $$V_i$$, subject to the following constraint:

$$\sum_{i}\left(\sum_{j}x_jC_{ij} \right) V_i = (1-WR)\cdot \sum_{i}\left(\sum_{j}C_{ij} \right) + WR \sum_{i}\left(\sum_{j}x_jC_{ij}\right)$$

Where WR (and C) are constant.

The problem here seems to be that this constraint is non-linear (because we are multiplying $$x$$ by $$V_i$$ on the left hand side) and that the multiplication $$A_iV_i$$ is also non linear. Is there a way to somehow linearize this problem?

• So that's a product of continuous variables? if so, it might be time to bite the bullet and use a non-convex nonlinear solver. – Mark L. Stone May 19 '20 at 20:15