# Linear programming: objective function with “buckets”

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?

• Is $A_{i}$ an integer variable? If not, how do you compute your objective if $100 < A_{i} < 101$? – mtanneau Dec 22 '20 at 18:52

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.

• 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

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

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