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?

  • 1
    $\begingroup$ 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. $\endgroup$ Commented May 19, 2020 at 20:15


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.