Linear programming: objective function with "buckets"

Question

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?

Answer 1

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.

Answer 2

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