how to penalize a shortfall of a sum of absolute values

Question

I have a model where there is a constraint on the sum of absolute values, and I would like to add a penalty on the shortfall from the constraint. More specifically:

\begin{align*} \text{maximize}\ & \sum a_i x_i \\ \text{subject to}\ & y_i \ge x_i \\ & y_i \ge -x_i \\ &\sum y_i \le \text{ABSLIMIT}, \end{align*} and various linear constraints among subsets of the $x$'s. ($\text{ABSLIMIT}$ is a constant.)

I would like to add a penalty to the objective that would accomplish this:

$$\text{maximize}\ \sum a_ix_i - K\left(\text{ABSLIMIT} - \sum |x_i|\right)$$

In other words, when the $\text{ABSLIMIT}$ constraint is not binding, I would like a penalty which would force the magnitudes of the $x_i$ to be as large as is feasible.

Any suggestions or references would be appreciated. Thanks.

Answer 1

If the $x$ variables are bounded, you can do this by introducing some binary variables (one for each $x$). Assume that $L_i \le x_i \le U_i$ for all $i$, where $L_i$ and $U_i$ are constants such that $L_i \le 0 \le U_i$. Create variables $y_i\ge 0$ and $z_i\in \lbrace 0, 1\rbrace$. For each $i$, add the constraints $$0 \le y_i - x_i \le -2L_i (1-z_i)$$and $$0 \le y_i + x_i \le 2U_iz_i.$$If $z_i=1$, you get $x_i\ge 0$ and $y_i=x_i$. If $z_i=0$, you get $x_i \le 0$ and $y_i = -x_i$. So either way $y_i = |x_i|$. Now just use ${\rm ABSLIMIT} - \sum\limits_i y_i$ as the term to be penalized.

Answer 2

I am not sure I got the whole idea, this answer is just focused on the following part:

In other words, when the $\rm ABSLIMIT$ constraint is not binding, I would like a penalty that would force the magnitudes of the $x_i$ to be as large as is feasible.

To do that I would try to use other constraints, and use some logic statements on those.

Thinking a little bit, I came with this set of constraints: \begin{align}z &= 1 - \left\lfloor\frac{\sum y_i}{\rm ABSLIMIT}\right\rfloor\\\sum x_i &\ge Kz\\z &\in \{0, 1\}\end{align}

Therefore, when the $\rm ABSLIMIT$ constraint is not biding $\left(\sum y_i < \rm ABSLIMIT \right)$ the value of $z$ will be equal to $1$ for any positive value of $\sum y_i$. And then the second constraint will be "active". This constraint will make sure that $ \sum x_i $ have a higher value than $K$.

In the opposite case, when $\rm ABSLIMIT$ constraint is biding $\left(\sum y_i = \rm ABSLIMIT \right)$ the value of $z$ will be $0$. And then the second constraint will be "inactive", making $\sum x_i$ unrestricted.

However, now we have the problem of finding a good value for $K$. It will depend deeply on the nature of your problem and it can also have a variable value if needed.

To implement the ceiling function in a linear problem you can use the method described in this answer.