11
$\begingroup$

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.

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$
1
  • $\begingroup$ Is $A_{i}$ an integer variable? If not, how do you compute your objective if $100 < A_{i} < 101$? $\endgroup$
    – mtanneau
    Dec 22 '20 at 18:52
10
$\begingroup$

1. Your suggested approach : quadratic program

Here are the details of your suggested approach. It results in a quadratic objective.

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:

\begin{align} \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} \end{align}

The resulting model then has a quadratic function $\sum_i A_i c_i$ in the objective.

2. Alternative : linear program

You can instead get a linear objective by introducing a variable $z_i$ to represent $A_i c_i$, with constraints:

\begin{align} \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})\\ \end{align}

The resulting model then has only a linear function $\sum_i z_i$ in the objective.

$\endgroup$
6
  • $\begingroup$ Should the objective function now also not include $y_i$ in some capacity? $\endgroup$
    – BarkingCat
    Feb 13 '20 at 11:57
  • $\begingroup$ Also, another question: why is $\sum_{i} A_i c_i$ going to be quadratic? $\endgroup$
    – BarkingCat
    Feb 13 '20 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$
    – RobPratt
    Feb 13 '20 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 '20 at 10:57
  • $\begingroup$ No, it is not needed because $c_i$ does not appear anywhere in that model. $\endgroup$
    – RobPratt
    Feb 14 '20 at 13:04
7
$\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$
7
  • $\begingroup$ This model yields $c_i$ instead of $A_i c_i$ in the objective. $\endgroup$
    – RobPratt
    Feb 12 '20 at 18:39
  • $\begingroup$ yes indeed ! thanks for pointing it out. $\endgroup$
    – Kuifje
    Feb 12 '20 at 18:44
  • $\begingroup$ I think you are missing one constraint: $A_i \ge 201 y_{i3}$. $\endgroup$
    – prubin
    Feb 12 '20 at 20:39
  • $\begingroup$ yes indeed ! thanks $\endgroup$
    – Kuifje
    Feb 12 '20 at 20:50
  • $\begingroup$ What is $M$ in this context? $\endgroup$
    – BarkingCat
    Feb 13 '20 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.