Modeling the absolute value

PeterBe · April 10, 2017, 9:58am

Hi guys,

I just started to use GAMS (so I have no experience whatsoever). I wanted to know whether and how it is possible to model the absolute values of binary variables. So I want to maximize the difference:

max: SUM(t=0 to T) {abs(x_t - c_t)}

where x_t is a binary decision variable and c_t is also a binary variable (but not decision variable; the values are fixed). Of course there are contraints such that just flipping the value of c_t for every time slot is not feasible.

Does anyone have an idea whether something like this is possible or not.

Manassaldi · April 10, 2017, 7:21pm

Hi, maybe you can try with this restriction:

eq1(t).. 1 - x(t)  +    c(t) +    absvalue(t)   =g= 1;
eq2(t).. 1 - x(t)  + 1-c(t) + 1-absvalue(t)  =g= 1;
eq3(t)..      x(t)  + 1-c(t) +     absvalue(t)  =g= 1;
eq4(t)..      x(t)  +    c(t) +  1- absvalue(t) =g= 1;
eq5..        z =e= sum(t,absvalue(t) )

absvalue(t) correspond to the absolute value of (x(t) - c(t))

Good luck

PeterBe · July 21, 2017, 1:27pm

Sorry it has been a while since I posted this question. Nonetheless I unforunately have not solved this problem. Basically my problem has slightly changend. Now I want to solve the following prolbem:

max: SUM(t=0 to T) {abs(x_t - y_t)}

where x_t is a binary decision variable and y_t is also a binary decision variable.

Is there a way how this can automatically be done by GAMS meaning that GAMS for example linearizes the abs function?

PeterBe · July 24, 2017, 1:20pm

Hi, Sorry that I have not written anything since a fairly long time. But I do not really understand the approach form Manassaldi and my objective has slightly changed. So I want to maximize the difference:
max: SUM(t=0 to T) {abs(x_t - y_t)}

where x_t is a binary decision variable and y_t is also a binary decision variable.

I heard that something like this is solable with the Gurobi Solver by introducing an auxiliary variable z(t) = x(t) - y(t) for each t. However adding the following equations to GAMS:

eq_z(t).. z(t) =e= x(t) - y(t);

eq_z_abs(t).. z_abs(t)=e= abs(z(t));

led to the error message: “Endogenous function argument(s) not allowed in linear models”

Does anyone have an idea whether and how something like this is possible or not by using GAMS?

Manassaldi · July 26, 2017, 1:13pm

Hi!
These constraints are obtained using logical propositions and the so-called “basic steps”.
You can not use the abs() function in linear programming

eq1(t).. 1 - x(t)  +    c(t) +    absvalue(t)   =g= 1;
eq2(t).. 1 - x(t)  + 1-c(t) + 1-absvalue(t)  =g= 1;
eq3(t)..      x(t)  + 1-c(t) +     absvalue(t)  =g= 1;
eq4(t)..      x(t)  +    c(t) +  1- absvalue(t) =g= 1;
eq5..        z =e= sum(t,absvalue(t) )

If you observe the restrictions you can note that:

If x = 1 and c = 0 then for eq1 absvalue = 1 (equal to abs(x-c)) (the remaining restrictions are also satisfied)
If x = 1 and c = 1 then for eq2 absvalue = 0 (equal to abs(x-c)) (the remaining restrictions are also satisfied)
If x = 0 and c = 1 then for eq3 absvalue = 1 (equal to abs(x-c)) (the remaining restrictions are also satisfied)
If x = 0 and c = 0 then for eq4 absvalue = 0 (equal to abs(x-c)) (the remaining restrictions are also satisfied)

As the variables are binary, there are no other possibilities

Best regard

PeterBe · July 27, 2017, 12:54pm

Hi,

I inserted following equations:

eq_z_firstCondition(t).. z(t) =l= 2 - x(t) - y(t);
eq_z_secondCondition(t).. z(t) =l= x (t) + y(t);

...

u
=e=
sum((t),  z(t));

...

Solve model using mip maximizing u;

z(t) is an auxilliary variable

I think that this might be same as in your example, doesn’t it?

Manassaldi · July 27, 2017, 2:02pm

Hi, your equations are good too.
If I am not mistaken, these restrictions are only valid for a maximization problem.

if x=1 y=1
eq_z_firstCondition(t)… z(t) =l= 0;
eq_z_secondCondition(t)… z(t) =l= 2;
so: z=0

if x=1 y=0
eq_z_firstCondition(t)… z(t) =l= 1;
eq_z_secondCondition(t)… z(t) =l= 1;
so: z=1 or z=0 (but for a maximization problem z=1)

if x=0 y=0
eq_z_firstCondition(t)… z(t) =l= 2;
eq_z_secondCondition(t)… z(t) =l= 0;
so: z=0

if x=0 y=1
eq_z_firstCondition(t)… z(t) =l= 1;
eq_z_secondCondition(t)… z(t) =l= 1;
so: z=1 or z=0 (but for a maximization problem z=1)

I think that the so-called “Basic Steps” allow to obtain logical restrictions in a systematic way in a short time.
Best regard!

PeterBe · July 28, 2017, 8:05am

Thanks Manassaldi for your answers and comments.

Would you mind telling me a little bit more about the “basic step”. Is that a generall principle for modelling absolut values or what exactly does this method aim for?

Manassaldi · July 28, 2017, 12:53pm

Hi, the “basic-steps” are steps to transform logical propositions into algebraic equations.
In your problem, i used 4 logical proposition and three booelan variable:

X: boolean variable equivalent to x
Y: boolean variable equivalent to y
Z: boolean variable equivalent to z (abs(x-y))

logical proposition #1: X ^ Y → ¬Z (in logic languaje: X true and Y true implies Z not true)

Now, using the basic steps you can transform the logical proposition #1 into an algebraic equation.
BASIC STEPS
Goal is to Convert Logical Expression into Conjunctive Normal Form (CNF)

REPLACE IMPLICATION BY DISJUNCTION
¬(X ^ Y)˅¬Z
MOVE NEGATION INWARD APPLYING DE MORGAN’S THEOREM
¬X ˅ ¬Y ˅¬Z
RECURSIVELY DISTRIBUTE OR OVER AND
(not necessary in this case)

Finally,
¬X ˅ ¬Y ˅¬Z (CNF)
So, you can replace any CNF for a summatory of each term.
Because at least one of a term has to be true, the sumatory has to be greater than 1
¬X equivalent to 1-x
¬Y equivalent to 1-y
¬Z equivalent to 1-z
So, this CNF generate equation “eq2” of my example
1 - x + 1 - y + 1 - z =g= 1;

logical proposition #2: X ^ ¬Y → Z (generate eq1)
logical proposition #2: ¬X ^ ¬Y → ¬Z (generate eq4)
logical proposition #2: ¬X ^ Y → Z (generate eq3)

This is a quick explanation, I hope it will be useful

Best regard!

PeterBe · July 28, 2017, 1:23pm

Thanks again for the answers. Where can I read more about those basic steps? I typed it into google but somehow I could not find useful information about them.

Manassaldi · July 28, 2017, 1:32pm

You can find some here (page 14): http://www.minlp.org/pdf/GBDEWOGrossmann.pdf
Th Basic Steps are simple, the difficult is the manipulation of the propositions.
Best regard!

PeterBe · August 30, 2017, 3:58pm

Hi guys, I have a further question:

I still have not fully understood how to modell the absolute value of a difference in GAMS. I have used the following equations for binary variables for modelling: abs(x(t) - y(t)):
eq_z_firstCondition(t)… z(t) =l= 2 - x(t) - y(t);
eq_z_secondCondition(t)… z(t) =l= x (t) + y(t);

but what if you don’t have binary variables but for example a sum:
abs( (sum(t, x(t))) - (sum(t, y(t))).

How could I model something like that?

PeterBe · September 6, 2017, 2:02pm

Hi guys,

does nobody have a clue? I just want incoorporate the absolute value of:
abs( (sum(t, x(t))) - (sum(t, y(t))) (with x(t) and y(t) being binary variables)

Manassaldi suggest the following for binary variables:

eq1(t).. 1 - x(t)  +    c(t) +    absvalue(t)   =g= 1;
eq2(t).. 1 - x(t)  + 1-c(t) + 1-absvalue(t)  =g= 1;
eq3(t)..      x(t)  + 1-c(t) +     absvalue(t)  =g= 1;
eq4(t)..      x(t)  +    c(t) +  1- absvalue(t) =g= 1;
eq5..        z =e= sum(t,absvalue(t) )

Let’s say x(t) and c(t) are not binary variables. How would you model the absolute value of the difference between them: abs (x(t)-c(t))?

Manassaldi · September 6, 2017, 5:29pm

Hi again PeterBe, I think this can works

x(t) and c(t) are continuous variables
p(t) are binary variables
M is a sufficiently large number (BigM parameter)

if “p=1”, by “eq3” (x-c) is greater than 0 so by “eq1” and “eq2” absvalue = x-c (the rest of equation are also satisfied)
if “p=0”, by “eq6” (x-c) is lower than 0 so by “eq4” and “eq5” absvalue = c-x (the rest of equation are also satisfied)

eq1(t)… absvalue(t) =l= x(t) - c(t) + (1-p(t))*M;
eq2(t)… absvalue(t) =g= x(t) - c(t) - (1-p(t))*M;
eq3(t)… x(t) - c(t) =g= -(1-p(t))*M
eq4(t)… absvalue(t) =l= c(t) - x(t) + p(t)*M;
eq5(t)… absvalue(t) =g= c(t) - x(t) - p(t)*M;
eq6(t)… x(t) - c(t) =l= p(t)*M
eq7… z =e= sum(t,absvalue(t))

All this restrictions are for “z = sum(t,abs(x(t)-c(t)))” with x and c continuous variables

Bye!

gnaeidj · September 12, 2017, 6:56am

Dear Friend
I’ve Written a MIQCP code which has an absolute value in its constraints and I don’t know how exactly I must write it so that the code works.

here is the constraint:

sum((n,m,t),abs(z(n,m,t) - z(n,m,t+1)) =l= 2*j

the summation basically is based on t (time) and I want this absolute value constraint to work within my code

I’ll be so thankful if you guide me

Best Reards
Ghassem

Manassaldi · September 12, 2017, 12:38pm

Hi,
What kind of variables are z and j?

gnaeidj · September 12, 2017, 4:27pm

Hi,
Z is a binary variable and J is a scalar

actually the Z variable represents a line status (being in circuit or out of it) and J represents the maximum number of lines which can get out of service

I want to use the mentioned constraint to express the maximum number of switching in a system, but I don’t know how to insert it into my codes, so that it works properly.

Manassaldi · September 13, 2017, 12:46pm

Hi, this constraints are equivalent to “sum((n,m,t),abs(z(n,m,t) - z(n,m,t+1)) =l= 2*j”
With the command “$” you must decide what happens with the last t

eq1(n,m,t)… 1 - z(n,m,t) + z(n,m,t+1) + absvalue(n,m,t) =g= 1;
eq2(n,m,t)… 1 - z(n,m,t) + 1-z(n,m,t+1) + 1-absvalue(n,m,t) =g= 1;
eq3(n,m,t)… z(n,m,t) + 1-z(n,m,t+1) + absvalue(n,m,t) =g= 1;
eq4(n,m,t)… z(n,m,t) + z(n,m,t+1) + 1-absvalue(n,m,t) =g= 1;
eq5… sum((n,m,t),absvalue(n,m,t)) =l= 2*j;

Bye

gnaeidj · September 13, 2017, 7:07pm

Thank you so much

gnaeidj · September 13, 2017, 7:15pm

Just something I didn’t catch
what did you mean by “$” command?