11

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?

BarkingCat
  • 241
  • 1
  • 4

2 Answers2

11

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.

Konstantin
  • 306
  • 1
  • 8
RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • Should the objective function now also not include $y_i$ in some capacity? – BarkingCat Feb 13 '20 at 11:57
  • Also, another question: why is $\sum_{i} A_i c_i$ going to be quadratic? – BarkingCat Feb 13 '20 at 13:24
  • 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. – RobPratt Feb 13 '20 at 13:34
  • 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$?) – BarkingCat Feb 14 '20 at 10:57
  • No, it is not needed because $c_i$ does not appear anywhere in that model. – RobPratt Feb 14 '20 at 13:04
  • It worked perfectly, thanks! I now have an extension of the problem. Would it be possible for you to take a look at that? https://or.stackexchange.com/questions/4215/linear-programming-extending-problems-yields-non-linearity – BarkingCat May 19 '20 at 15:27
8

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

Kuifje
  • 13,324
  • 1
  • 23
  • 56