8

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.

LarrySnyder610
  • 13,141
  • 3
  • 41
  • 105
Henry
  • 542
  • 2
  • 7
  • 2
    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 https://or.meta.stackexchange.com/q/5/38. – LarrySnyder610 Mar 26 '20 at 00: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? – LarrySnyder610 Mar 26 '20 at 00:09
  • @LarrySnyder610, the constraints enforce only that $y_i\ge |x_i|$, not equality. Nothing prevents $y_i>|x_i|$. – RobPratt Mar 26 '20 at 00: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...? – LarrySnyder610 Mar 26 '20 at 01:48
  • thanks Larry. my question is how to make the penalty work. will use mathjax next time – Henry Mar 27 '20 at 02:43

2 Answers2

10

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.

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
prubin
  • 39,078
  • 3
  • 37
  • 104
4

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.

EhsanK
  • 5,864
  • 3
  • 17
  • 54
renan-eccel
  • 49
  • 5