# how to penalize a shortfall of a sum of absolute values

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.

• Our preference on OR.SE is to use MathJax (LaTeX) for mathematical programming formulations, rather than code blocks. I have edited your code accordingly. Please make sure I haven't introduced any errors. For future posts, you can refer to or.meta.stackexchange.com/q/5/38. Mar 26 '20 at 0:06
• Also, since $y_i = |x_i|$, I think the sum in the penalty term can just be over $y_i$, correct? And if so, what's wrong with the model as you have already formulated it? Mar 26 '20 at 0:09
• @LarrySnyder610, the constraints enforce only that $y_i\ge |x_i|$, not equality. Nothing prevents $y_i>|x_i|$. Mar 26 '20 at 0:25
• @RobPratt that's true. Henry: Is your question about how to formulate the absolute value? Or about how to formulate the penalty? Or something else...? Mar 26 '20 at 1:48
• thanks Larry. my question is how to make the penalty work. will use mathjax next time Mar 27 '20 at 2:43

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.

• thank you Dr. Prubin, this helps me with the problem. Mar 27 '20 at 2:15

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.

• thanks Renan, this is a different approach to consider Mar 27 '20 at 2:44