max f(x)=g(x)+b*p+b*q

s.t

other constraints

x-a+p-q=0;

p,q>=0;

Dear Hossein,

Many thanks for your prompt answer.

I analyzed your model and unfortunately I found out there is a contradiction.

Assume a>0 and h(x)=|x-a|.

If x*=2a, it is expected that h(x=2a)=+a while your model indicates that:

h(x)=p+q

2a-a+p=0 -----> p=-a   while we had p>=0  (this is a contradiction!)

2a-a-q=0 -----> q=+a  ( this condition is correct because we had q>=0).

As a result, h(x)=p+q=0 (!) while it has to be +a !

I think we have to change its equality sign to inequality (>= or

You can divide the problem into two sub-problems:

Problem 1: 

Max f(x)=g(x) + b*(x-a)

s.t.

x>a

other constraints

and 

Problem 2: 

Max f(x)=g(x) + b*(a-x)

s.t.

x

Dear Morteza,

You are right. I correct my answer.

Dear Hossein,

It was better to write your corrected answer in another post and not amending your first answer.

Nevertheless, many thanks for your contribution.

My Conclusion:

        Max f(x) = g(x) + b*(p+q)

         s.t.

                  The previous constraints; and

                   p-q=x-a;

                   p>=0

                   q>=0

-------------------

http://mortezash.blogfa.com/

Hi Morteza,

I think I am confused.

since

f(x) =g(x) + b* |x-a|

If let  p-q = x-a

when x>= a

f(x) = g(x) + b*p - b*q

while when x

Dear Wang,

Just one of p or q takes a value. In fact, p*q=0 in each solution.

Dear Morteza,

i agree with Hassan Hijazi about his idea 

i also refer you to the text book " introduction to linear optimization"

in chapter 1, you can find detailed explanation for Problems involving absolute values at page 17 

you can read my paper, it can help you.

best washes  

Dear Ahmed,

What is the author's name of the book you recommended?

Dear MengChang, 

The optimal solutions of both linear programs are the same if at least one of the values p and q is zero. In this case, p=(x-a) when (x-a)>=0 and q=-(x-a) when (x-a)

Dear Dr. Hijazi,

Many thanks for your worthwhile and convincing answer. Now I know how the |x| in the objective function can be linearized.

Regards,

Morteza

2nd Question:

What do we do if the Absolute Value terms are in the constraints as below?

Constraints:

              3 |x1| + 2 |x2| + 4 |x3|

hi,

here it is a small GAMS MILP model that calculates the modulus of x(i)

and saves it in y(i):

set i /1*12/;

binary variable signal(i);

variable x(i), obj, y(i);

parameter x_p(i), max_min;

x_p(i)=card(i)/2-ord(i);

max_min=card(i);

equations

set_x(i)

calc_signal(i)

calc_y(i)

calc_y2(i)

calc_y3(i)

calc_y4(i)

calc_obj

;

set_x(i).. x(i)=e=x_p(i);

calc_signal(i).. x(i)+ max_min*signal(i)=g=0;

calc_y(i).. y(i) + max_min*signal(i)=g=x(i);

calc_y2(i).. y(i) =l=x(i) +max_min*signal(i);

calc_y3(i).. y(i) + max_min*(1-signal(i))=g= -x(i);

calc_y4(i).. y(i) =l= -x(i) + max_min * (1-signal(i));

calc_obj.. obj=e=sum(i, signal(i));

Model ModulusX /all/;

Solve ModulusX using MIP min obj;

display x.l, signal.l, obj.l, y.l;

hope this can help you!

Best Regards,

jose barahona da fonseca.

Be careful with the proposal of Hossein Karimi, i.e.

max f(x)=g(x)+b*p+b*q

s.t

other constraints

x-a+p-q=0;

p,q>=0;

This won't work when b>0, since with every p and q and t the additional constraint holds for the pair (p+t, q+t), too, increasing the objective by 2bt. Thus with the problem will have no solution, since it is unbounded.

If your modulus term is only in the objective and b is negative (leading to minimizing the modulus term), things are simple: just add one auxiliary variable u, substitute u for the modulus term in the objective by u and add the inequalities

u >= x-a

u>= a-x

Then u>= |x-a| and minimizing u leads to equality.

If b is positive (thus the modulus term shall be maximized) you have to add one binary variable v and a pair of disjunctive inequalities in addition, yielding u

The following general remark may (not) help.

|x| = max subject to |u|

no, CPLEX is for linear models 

if you put an absolute operator in the objective function the model turns to be Nonlinear and not soluble with CPLEX.

best regards,

jbf.

|x-a| = max y^T(x-a) subject to [1, -1]^Ty

Hi Elvis,

what do you mean by [1, -1]^Ty

Hello everyone,

I am trying to remove this absolute operator for cplex.

Zi=1/2 | ∑_(j=1)^J▒(-1)^j (x_(i,j) - x_(i+1,j)) |

where Zi has be  {0,1}

but if I remove the mode, the values I am getting is {0,1,-1}.

How can I replace the absolute operator  to make it an equation for Mixed integer Linear programming

PFA  word file to clearly understand the equation.

any suggestions please.

Thank you.

Not really possible in Linear Programming, if not the term absolute value is to be minimized. In that case it suffices to have

min a

a >= (x_(i,j) - x_(i+1,j)),

a >= (x_(i+1,j) - x_(i,j))

Else it would require a MILP with an additional binary variable to express the disjunctive condition

a x= (x_(i,j) - x_(i+1,j)) or a

If it is a maximization problem, the only way to linearize it is if you can enumerate all the cases which the constraint can take

Dea Issam,

p and q are linearly dependent. It means only one of them takes a value. Therefore, there is no need to consider p*q=0 as a constraint in the model.

Dear Issam M

As we know p and q are linearly dependent and therefore there is not possible that they simultaneously take positive values. In other words, it ensures that p*q=0

Dear Issam,

I think the following proof can help you.

It can be proved by contradiction. If both p and q take positive values, and delta=min(q,p), adding delta to -p+q leaves the resulting value unchanged, but adds abs(x) by 2*delta (abs(x)=p+q), which contradicts the optimality assumption.

To sum up, please see the file in the attachment.

"The linear form of |x| function"

Hi all,

How about the resultant linearized objective function. Is it an approximation or can this be still proven as optimal ? How is it justifiable?

Regards,

Hi Asif Ali Khan,

the slide in Morteza Shabanzadeh's answer shows that the optimal values are the same - provided that none the coefficients of the absolute values in the objective is negative.

There is no 1:1 correpondence between x_j and x_j^+,x_j^-, so to every value of x_j there corresponds a ray of values, since for every feasible x_j=x_j^+ - x_j^- the pairs

(x_j^+ +delta, x_j^- +delta) will be feasible, too - and they represent the same difference.

So the applicability of the representation by a difference depends on HOW the absolute values occur in the problem.

Adding the condition x_j^+ * x_j^- = 0 makes the problem nonlinear (a complementarity problem). Instead of adding that condition one could as well solve the original problem with an NLP solver like e.g. Ipopt. It would work in practice, though the absolute value is not differentiable (which is a condition for the convergence proofs).

Another way of modeling the absolute value (only valid for variables with bounded domain) would introduce a binary variable and Big-M-constraints, making the problem a MILP (see the notion: alternative inequalities in MIP modelling):

suppose x is bounded by -M

Alternatively, wlog we can assume x, b and a are all row vectors of size k, we can write Max f(x) = g(x) + b|x-a| = g(x) + sumj=1...k (b_j*|x_j - a_j|),

|x_j - a_j| = max {x_j - a_j, -x_j + a_j} = z_j for j = 1, ... , k. So, we have

Max f(x) = g(x) + sumj=1...k(b_j*z_j)

x_j - a_j

I have a similar question, maybe someone can help me please

https://www.researchgate.net/post/How_to_linearize_the_following_exercises_with_absolute_values