9
$\begingroup$

I had a linear programming problem with the following objective function

$$f(x) = \sum_{j}x_jq_jp_j - \sum_{i}\left(\sum_{k}x_kq_kC_{ik} \right) c_i$$

Where $q, p, C, c$ are known.

This problem was easily solvable using linear programming, because it is completely linear.

I now have a modified version of the objective function, where I want the last parameter $c_i$ to vary based on the value of the summation $\sum_{k}x_kq_kC_{ik}$, which we will now call $A_i$, that comes before it.

More specifically, I have three "buckets":

$$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}$$

How can I incorporate this into my objective function? My instinct tells me to somehow create three auxiliary variables which function as "switching" parameters for each of the buckets and are either 1 or 0. Since the value of $A_i$ has to lie in one of the buckets, one of these weights will be 1 and the others will be 0. I then sum over the weighting parameter times the bucket value (10/8/6) and I will get the proper result. Is something like this possible?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Should the objective function now also not include $y_i$ in some capacity? $\endgroup$ – BarkingCat Feb 13 at 11:57
  • $\begingroup$ Also, another question: why is $\sum_{i} A_i c_i$ going to be quadratic? $\endgroup$ – BarkingCat Feb 13 at 13:24
  • $\begingroup$ In both models, $y_i$ does not explicitly appear in the objective but instead influences, via the constraints, the variables that do appear in the objective. In the first model, the objective is quadratic because $A_i c_i$ is a product of two decision variables. $\endgroup$ – Rob Pratt Feb 13 at 13:34
  • $\begingroup$ should the equation $10y_{i,1} + 8y_{i,2} + 6y_{i,3} = c_i$ not also be included in the second model? (Where we have the $z_i$?) $\endgroup$ – BarkingCat Feb 14 at 10:57
  • $\begingroup$ No, it is not needed because $c_i$ does not appear anywhere in that model. $\endgroup$ – Rob Pratt Feb 14 at 13:04
6
$\begingroup$

You can add the following equations to your model :

First, define your variable $A_i$:

$$ A_i = \sum_{k}x_k C_{ik}q_k \quad \forall i $$

Then, define binary variables $y_{ij}$ that take value $1$ iff $A_i$ is in interval $j$ (where interval $1$ is $[0,100]$, interval $2$ is $[101,200]$, and interval $3$ is $[201, \infty[$ : \begin{align} 0 &\le A_i \le 100 + M (1-y_{i1}) \\ 101y_{i2} &\le A_i \le 200 + M (1-y_{i2}) \\ 201y_{i3} &\le A_i \end{align}

Impose that you can only be on one of the intervals : $$ y_{i1} + y_{i2} +y_{i3} = 1\quad \forall i $$

And finally, add the following term to your objective function : $$ \sum_{i}(10A_iy_{i1} +8A_iy_{i2} + 6A_iy_{i3}) $$

Note that this last term is not linear, so you need to linearize it : replace $A_i y_{ij}$ by a variable $z_{ij}$ and add the following constraint : $$ z_{ij} \ge A_i - M(1-y_{ij}) $$

$\endgroup$
  • $\begingroup$ This model yields $c_i$ instead of $A_i c_i$ in the objective. $\endgroup$ – Rob Pratt Feb 12 at 18:39
  • $\begingroup$ yes indeed ! thanks for pointing it out. $\endgroup$ – Kuifje Feb 12 at 18:44
  • $\begingroup$ I think you are missing one constraint: $A_i \ge 201 y_{i3}$. $\endgroup$ – prubin Feb 12 at 20:39
  • $\begingroup$ yes indeed ! thanks $\endgroup$ – Kuifje Feb 12 at 20:50
  • $\begingroup$ What is $M$ in this context? $\endgroup$ – BarkingCat Feb 13 at 12:02

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.