Wednesday, August 25, 2010

Absolute Value Inequalities

The following question arose today: given divisible variables $x,y\in(-\infty,+\infty)$, how does one implement in a mathematical program the constraint $|x|\le|y|$?

To start, I do not think it can be done with unbounded variables. Then again, I'm not a big believer in unbounded variables in practice. (Physicists seem to believe the number of atoms in the universe is finite, which gives us a starting point at bounding all physical variables. They also believe the universe will eventually suffer heat death, which gives us a start at bounding time variables.)

Let us assume instead that $L_{x}\le x\le U_{x}$ and $L_{y}\le y\le U_{y}$, with no restrictions on which bounds are positive or negative. Now add a binary variable $z$, which will take value 0 if $y$ is positive and 1 if $y$ is negative.  We enforce that with the constraints\begin{eqnarray*}y & \le & U_{y}\times(1-z)\\y & \ge & L_{y}\times z.\end{eqnarray*} [LaTeXMathML does not support equation numbering, so please number the inequalities above (1) and (2) mentally, and the inequalities below (3)--(6). Sorry about that!] Note that the value of $z$ is undetermined if $y=0$, which will not be a problem. Now add the constraints\begin{eqnarray*} x & \le & y+\left(U_{x}-L_{y}\right)\times z\\ -x & \le & y-\left(L_{x}+L_{y}\right)\times z\\ x & \le & -y+\left(U_{y}+U_{x}\right)\times\left(1-z\right)\\ -x & \le & -y+\left(U_{y}-L_{x}\right)\times\left(1-z\right).\end{eqnarray*} If $y>0$, then (1) forces $z=0$, in which case (5) and (6) become vacuous (since $x\le U_{x}\le U_{x}+(U_{y}-y)$ and $-x\le-L_{x}\le-L_{x}+(U_{y}-y)$ respectively). Meanwhile, (3) and (4) become $x\le y$ and $-x\le y$, which enforces $|x|\le y=|y|$. Similarly, if $y<0$, then (2) forces $z=1$, which makes (3) and (4) vacuous and turns (5) and (6) into $x\le-y$ and $-x\le-y$, so that $|x|\le-y=|y|$. Finally, if $y=0$, then it does not matter whether $z=0$ or $z=1$, since either (3) and (4) (if $z=0$) or (5) and (6) (if $z=1$) will force $x=0$.

4 comments:

  1. Would this work? (no binaries or bounds)

    min yabs
    s.t.
    y = s0 - s1;
    yabs = s0 + s1;
    s0 >=0; s1 >= 0;
    -yabs <= x <= xabs;

    This is a pretty standard non-discrete formulation, but I'm always a little wary of popping stuff up in the objective. I always wonder if this formulation for abs() will work if my problem is nonconvex. I appreciate your advice on this.

    ReplyDelete
  2. Sorry that last constraint should read:
    -yabs <= x <= yabs;

    ReplyDelete
  3. Sadly, while much simpler, that may not work. Suppose, for instance, that in the absence of the constraint |x| <= |y| the optimal solution would be x = 5, y = -3 (which violates the absolute value constraint). Set x = 5, y = -3, s0 = k, s1 = 3 + k for any k >= 1, and you get yabs = 3 + 2k >= 5 ... so the solution is feasible in your formulation, but not in the original model.

    The problem with your approach actually has nothing to do with discreteness. In problems where absolute values are handled by adding the positive and negative components of a variable (as you did), you rely on the absolute value of the variable being penalized in the objective. If there is a sufficiently high cost to inflating yabs (as I just did), the solver will not do it. Adding such a penalty without modifying the problem to the point of changing the optimal solution is somewhere between tricky and generally not feasible.

    ReplyDelete
  4. Your post was so very interested full of sense and I can relate to your side.Thank you so much for all this thoughts!!God Bless

    ReplyDelete

If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on OR-Exchange.