8
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – LarrySnyder610 Mar 26 '20 at 0:06
  • $\begingroup$ 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? $\endgroup$ – LarrySnyder610 Mar 26 '20 at 0:09
  • $\begingroup$ @LarrySnyder610, the constraints enforce only that $y_i\ge |x_i|$, not equality. Nothing prevents $y_i>|x_i|$. $\endgroup$ – RobPratt Mar 26 '20 at 0:25
  • $\begingroup$ @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...? $\endgroup$ – LarrySnyder610 Mar 26 '20 at 1:48
  • $\begingroup$ thanks Larry. my question is how to make the penalty work. will use mathjax next time $\endgroup$ – Henry Mar 27 '20 at 2:43
10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ thank you Dr. Prubin, this helps me with the problem. $\endgroup$ – Henry Mar 27 '20 at 2:15
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ thanks Renan, this is a different approach to consider $\endgroup$ – Henry Mar 27 '20 at 2:44

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.