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$ – Mark L. Stone May 19 '20 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.