3
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.