sci.op-research

On Mar 21, 8:53=A0pm, Paul Rubin wrote:
> xgenera...@gmail.com wrote:
> >>> x(i)'s ae actually bounded above and below: =A0LB(i) <=3D x(i) <=3D UB=
(i).
> >>> But the problem is that x(i)'s can be either positive or negative.
> >> Represent each x(i) with a sum of two auxiliary variables that
> >> cannot be greater than zero at the same time.
>
> > if x(i)=3Dxp(i)-xn(i) where xp(i) and xn(i) are two nonnegative slack
> > variables, then to enforce exactly one of them to be zero =A0I would
> > need to maximize
> > |x(i)|=3Dz=3Dxp(i)+xn(i).
> > But this is not the case for me.
>
> You still need binary variables, and I think you will also need to bound
> x away from zero when it is not zero. =A0For instance, introduce binary
> variables y(i) and z(i) and a small positive constant e, then use the
> following constraints:
>
> x(i) =3D xp(i) - xn(i)
> e*y(i) <=3D xp(i) <=3D U(i)*y(i)
> e*z(i) <=3D xn(i) <=3D |L(i)|*z(i)
> y(i) + z(i) <=3D 1.
>
> This gives you three cases:
>
> y(i) =3D 0 =3D z(i), x(i) =3D 0;
> y(i) =3D 1, z(i) =3D 0, e <=3D x(i) <=3D U(i);
> y(i) =3D 0, z(i) =3D 1, L(i) <=3D x(i) <=3D -e.
>
> So if you sum up 1 - y(i) - z(i) for all i, you get the number of zeros.
> =A0 Note, though, that 0 < |x(i)| < e cannot occur, so you are eliminating=

> some potential solutions from the feasible region.
>
> A different approach is to say
>
> e*y(i) <=3D xp(i) <=3D e + (U(i) - e)*y(i)
> e*z(i) <=3D xn(i) <=3D e + (|L(i)| - e)*z(i)
> y(i) + z(i) <=3D 1.
>
> Now y(i) =3D 0 =3D z(i) means 0 <=3D xp(i) <=3D e and 0 <=3D xn(i) <=3D e,=
so -e <=3D
> x(i) <=3D e, while y(i) =3D 1 means x(i) >=3D e and z(i) =3D 1 means x(i) =
<=3D -e.
> =A0 The first case (both binaries zero) opens the door to both xp(i) and
> xn(i) being positive, but that's harmless here. =A0Now summing 1 - y(i) -
> z(i) for all i counts the number of x(i) that are nearly zero (within e
> of zero).
>
> Last comment: =A0you can count the number of exact zeros if x is
> integer-valued. =A0I don't think you can count the number of exact zeros
> if x is divisible; I think you're limited to counting near-zeros.
>
> /Paul

So using
xpb(i) + xnb(i) <=3D 1
with
xp(i) <=3D xpb(i)*UB
xn(i) <=3D xnb(i)*UB

as Wit suggests, one can determine if the continuous variable x(i) is
EXACTLY zero or not.