Range limits on terms in the objective function of an LP

Question

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.

Answer 1

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.$$