# Range limits on terms in the objective function of an LP

I have a linear maximization problem with an objective as follows: $$\sum c_i\cdot\text{exp}_i$$ where $$c_i$$ are constants (positive or negative) and $$\text{exp}_i$$ are linear expressions of the free variables, which may be positive or negative.

I want to put a floor and ceiling on the exp[i] in the objective, so that no term may add or subtract more than abs(c[i] * threshold) to/from the objective value.

It's straight-forward to implement the ceiling for c[i] > 0 and the floor for c[i] < 0 as penalties:

if c[i] > 0:
penalty[i] > exp[i] - threshold
penalty[i] > 0
subtract c[i] * penalty[i] from the objective function

if c[i] < 0:
penalty[i] > threshold - exp[i]
penalty[i] > 0
subtract c[i] * penalty[i] from the objective function


However this method does not work for a floor when c[i] > 0 or for a ceiling when c[i] < 0 because penalty[i] is not bounded from above.

So I am asking if there is a different "trick" that can be applied here, or can this even be done as a linear problem, or alternately is there heuristic approach etc.

## 1 Answer

It can be done by adding binary variables (making your model an integer linear program), assuming that you can deduce upper and lower bounds for your linear expressions in advance. Let $$e_i$$ be the $$i$$-th expression, and let $$U_i$$ and $$L_i$$ be upper and lower bounds for it.

Next, let $$\delta_i>0$$ be your "threshold" on the contribution of $$e_i$$. I'm giving it a subscript $$i$$ in case you decided to vary the threshold from expression to expression, but of course you can use the same value for all $$\delta_i$$. We will introduce continuous variables $$z_i\in [-\delta_i, \delta_i]$$ to represent the objective contribution of the $$i$$-th term, so that the objective becomes $$\max \sum_i c_i z_i.$$

Now for each $$i$$ we introduce three binary variables ($$y_{i1}, y_{i2}, y_{i3}$$) together with the constraint $$y_{i1} + y_{i2} + y_{i3}=1,$$ which ensures that exactly one of them will be 1. The next two constraints define the $$y$$ variables in terms of your expressions.

$$e_i \le -\delta_i y_{i1} + \delta_i y_{i2} + U_i y_{i3}$$ $$e_i \ge L_i y_{i1} -\delta_i y_{i2} + \delta_i y_{i3}.$$

So $$y_{i1}=1 \implies L_i \le e_i \le -\delta_i,$$ $$y_{i2}=1 \implies -\delta_i \le e_i \le \delta_i$$ and $$y_{i3} = 1\implies \delta_i \le e_i \le U_i.$$ I'm assuming here that $$L_i \le -\delta_i \le \delta_i \le U_i$$ (i.e., that $$e_i$$ could exceed the threshold on either the negative or positive side). If not, you can simplify things by eliminating impossible cases.

Having effectively split $$e_i$$ into three ranges, we now use the binary variables to define the objective contribution $$z_i$$.

$$z_i \le e_i - L_iy_{i1}$$ $$z_i \ge e_i - U_iy_{i3}$$ $$z_i \le -\delta_i y_{i1} + \delta_i(y_{i2} + y_{i3})$$ $$z_i \ge \delta_i y_{i3} - \delta_i(y_{i1} + y_{i2}).$$

Collectively, these say that $$y_{i1}=1\implies z_i=-\delta_i,$$ $$y_{i2}=1 \implies z_i = e_i$$ and $$y_{i3} = 1 \implies z_i = \delta_i.$$