Originally posted by: DavidGravot

Hi

I wonder how to model efficiently constraints implying absolute value of some expression , say y, included in constraints such as 

beta.abs(y) >= x => alpha.abs(y)

I currently model this with directly cplex construct of abs, eg I let cplex linearize it for me (actually, I use only one variable absy , and a constraint absy==abs(y) , in order to minimize the number of re-formulation by cplex and then reuse absy whenever it is requested in the model)

The performances are pretty slow due to the size of my model. 

Note that my problem has no objective function, so I naively was originally thinking that the following model was equivalent : 

Minimize sum(y1 + y2)
y = y1 - y2
y1 >=0
y2 >=0

In the above model, we have of course to consider any expression y (there are a numerous of variable y included in abs expression)

Although it is correct stating that for any feasible y in the original model, there exist an optimal solution with y1 or y2 equal to 0, the opposite is not always true : I may find solutions y1 and y2 that are non zero . I'm not sure this means the original problem is infeasible ? My fear is that it opens more the search space allowing some solutions infeasible for the first model

Thanks for your comments...

David

Your second model is incorrect. Perhaps what you mean is y = y1 - y2, absy = y1 + y2, and minimize absy in the objective.

With that model (plus the remaining elements of the original model), and assuming y is the only variable whose absolute value is being used, I believe that a solution with both y1 and y2 strictly positive would mean that the original problem was infeasible. If there is more than one y variable, though, that might not be true. With multiple y variables, even though the objective function minimizes the sum of the absolute values, you might need to introduce binary variables and model the absolute values more carefully. I suspect that the use of the CPLEX absolute value function results in discrete variables being introduced internally.

Originally posted by: DavidGravot

Thanks Paul, my mistake indeed in the original model (I re-edited my first post to fix the typo)

originally, I wanted to end up with some linearization where for any feasible solution of the original problem, the objective function of the second is zero, but this would lead to actually minimize min(y1,y2), which ends up again in a non linear expression. I can give a try to see whether Cplex handles this better than my model with directly abs(y) in the constraints.

Originally posted by: BoJensen

It's unclear to me, what you are trying to model in :

beta.abs(y) >= x => alpha.abs(y)

What is beta and alpha and why y on both sides ?

I am guessing something like :

abs(y) >= x >= abs(z)

There's at least two ways to handle an absolute expression like abs(y) :

1) Split y up in a negative and positive part (same as Paul's suggestion) :

u >= y >= l => y = y1 + y2 => u >= y1 >= 0, 0 >= y2 >= l 

then replace :

abs(y) = y1 - y2

2) Add constraints and an abs variable t :

y <= t
-y <= t

abs(y) = t

It depends on the specific model, which one is fastest, but for an LP 1) is usually faster.

So I think you were already on the right path.

Originally posted by: DavidGravot

beta and alpha are simply constant values

I did not understand your first model. I can see u variables and kind of implication constraints...

I tried the second formulation where t >= y and t >= -y and tries to minimize t

In my model I end up indeed with a few variables where t is actually strictly greater than the absolute value of y. Again, does it mean the original model is infeasible, which is what I'm trying to figure out

Thanks

Just to be clear: there is only a single scalar variable y whose absolute value is being used in the model?

Originally posted by: DavidGravot

No, there are a large number of variables for which we need to use the absolute value

With multiple absolute values floating around, in general you cannot assume that a solution with y1 and y2 both positive implies an infeasible original problem. Consider the following trivial example. (I'm not saying your model looks like this, I'm just illustrating the concept.)

min (y1 + y2) + (z1 + z2)

s.t.

y = y1 - y2

z = z1 - z2

y <= 2

x = 12

x <= |y| + 0.1 |z|

y1, y2, z1, z2 >= 0

If the objective were to minimize |y| + |z|, the optimal solution would be y = 2, z = 100 with objective value 102. Using the linearization, though, a solver can set y1 = 7, y2 = 5 (so y is again 2), z = 0 and have an objective value of 12. Fundamentally, this is due to |y| and |z| interacting in the constraints.

Originally posted by: BoJensen

Paul is right, I was too fast suggesting those reformulations, sorry about that.

The problem arises because your model has a mix of abs(y) and y. If we use the reformulation y = yplus + yminus, then we substitute abs(y) = yplus-yminus and y = yplus + yminus. The columns of yplus and yminus now have different signs of coefficients in the constraints and we loose complementarity. By loosing complementarity we are no longer guaranteed that yplus * yminus = 0.

For the general case of a abs() formulation of a continuous variable a MIP formulation is needed.

Originally posted by: BoJensen

In my model I end up indeed with a few variables where t is actually strictly greater than the absolute value of y. Again, does it mean the original model is infeasible, which is what I'm trying to figure out.

You can see from the CPLEX log if the model was found infeasible. If t has an zero objective coefficient then t could indeed be larger than abs(y) using the 2) formulation, usually the abs formulation has a penalty. Try to add min t to the objective.

By *strictly* greater do you mean t > abs(y) without taking into count numeric ?

Is it possible to share the model ? If yes, please export it to a mps file and send it to bo.jensen (at) dk.ibm.com.

Originally posted by: DavidGravot

Actually, even with a tiny example, we end up with gap between the relaxed abs and the actual one

The original model : 

Minimize |y|  
|y| <= x <= 2|y|
x >= 2
x >= 2 + y
y >= -0.5

This one would end up with y=2 and x=4, while the relaxed one : 

Minimize absy 

absy >= y;  
absy >= -y;
absy <= x;
x <= 2*absy;
2 <= x;
y+2 <= x;
-0.5 <= y;

would end up with y=-0.5, absy=1 and x=2

The relaxation actually opens the room to infeasible solution in the original problem

Originally posted by: BoJensen

You are right, my second suggestion is not correct in this particular case. It's a formulation that is sometimes used in norm minimization cases, but does not apply to this case. Sorry about that.

If I split up the free variable in a negative and positive part (as suggested in 1)), I get the expected result  (LP file format):

Minimize
 obj: yplus - yminus
Subject To
 c1: yplus - yminus - x  <= 0
 c2: 2 yplus - 2 yminus - x  >= 0
 c3: x >= 2
 c4: yplus + yminus - x <= -2
 c5: yplus + yminus >= -0.5
Bounds
 x free
 0 <= yplus
 0 >= yminus

Originally posted by: DavidGravot

Hi

Can you tell me what 'expected result' you get ? I ran your model and it returns 

yplus = 0.5;
yminus = -0.5;
x = 2;

If you look back in the original space, this would lead to y=0, x=2, which is not feasible

Originally posted by: BoJensen

<variables>
  <variable name="yplus" index="0" status="BS" value="2" reducedCost="0"/>
  <variable name="yminus" index="1" status="LL" value="0" reducedCost="2"/>
  <variable name="x" index="2" status="BS" value="4" reducedCost="0"/>
 </variables>

Originally posted by: DavidGravot

This is indeed feasible but sub-optimal for the second optimization : your optimal value is 2-0 while I get 0.5-(-0.5) 

Did I miss something in your model ?

Originally posted by: BoJensen

Please post your model that should be similar to mine, but give a different result.

Originally posted by: DavidGravot

The original opl model

 dvar float+ yplus;
 dvar float yminus;
 dvar float x;
 
 minimize yplus - yminus;
 
constraints{

yminus <= 0;

 c1: yplus - yminus - x  <= 0; //x >= |y| 
 c2: 2*yplus - 2*yminus - x  >= 0; //x <= 2|y| 
 c3: x >= 2;
 c4: yplus + yminus - x <= -2;//y+2 <=x
 c5: yplus + yminus >= -0.5;//y>=-0.5
}

the generated lp 

Minimize
 obj: yplus - yminus
Subject To
 c1: yminus <= 0
 c1: yplus - yminus - x <= 0
 c2: 2 yplus - 2 yminus - x >= 0
 c3: x >= 2
 c4: yplus + yminus - x <= -2
 c5: yplus + yminus >= -0.5
Bounds
      yminus Free
      x Free
End

Originally posted by: DavidGravot

Thank you Paul & Bo, 

The general assumption that "abs can be linearized" is indeed wrong in general and true only in particular conditions. This reminds me also some particular conditions where piecewise linear expression are convex for the problem and posting them to Cplex won't require any branching. After all, absolute value is a simple case of piecewise expression

My original concern was to detect conflicts in large "linear" models with absolute value of some variables involved in the constraints. Therefore, I was wondering if a relaxation of my problem would help me finding out the conflict. Currently, using directly abs expression in the model, cplex ends up with :

MIP - Integer infeasible.
Current MIP best bound is infinite.

and when I do 

change problem lp

the problem is feasible

I tried running conflict from the original problem (with abs) but the conflict search gets stuck without finding minimal set of constraints

That's why I wanted to find some hand-made relaxation that could possibly detects the conflict in an other way, but this probably won't help since the conflict comes from the MIP standpoint and not the relaxation

The conflict refiner getting "stuck" is odd. Do you mean that it continues to run for an excessively long period of time, or that it returns with no conflict?

If you can assign a priori bounds to the variables whose absolute values you are taking, you might try reformulating as a MIP (without using the abs() function) and then running the conflict refiner on that. Let y be a variable whose absolute value you need, and assume that you know that |y| <= U for some constant value U. Add a new binary variable z and continuous variables y1 >= 0 and y2 >= 0, along with the constraints

y = y1 - y2

y1 <= Uz

y2 <= U(1-z),

and then use y1 + y2 as the absolute value of |y|. The two constraints involving z will ensure that either y1 or y2 (or both, if y = 0) will be 0.

Originally posted by: DavidGravot

Hi 

The conflict refiner does not terminate after more than 1 day of computation and actually still finds 0 mandatory member in the conflict

I'll give a try to the MIP reformulation to detect the conflict. 

Thanks !

Originally posted by: DavidGravot

It is the same behavior with MIP reformulation : no solution and conflict does not converge 

Originally posted by: BoJensen

If it's possible to share the model, then please send the mps file and the log file to to bo.jensen (at) dk (dot) ibm (dot) com.