Page 1 of 3

Modeling the absolute value

Posted: Mon Apr 10, 2017 9:58 am
by PeterBe
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.

Re: Modeling the absolute value

Posted: Mon Apr 10, 2017 7:21 pm
by Manassaldi
Hi, maybe you can try with this restriction:

Code: Select all

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

Re: Modeling the absolute value

Posted: Fri Jul 21, 2017 1:27 pm
by PeterBe
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?

Re: Modeling the absolute value

Posted: Mon Jul 24, 2017 1:20 pm
by PeterBe
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:

Code: Select all

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?

Re: Modeling the absolute value

Posted: Wed Jul 26, 2017 1:13 pm
by Manassaldi
Hi!
These constraints are obtained using logical propositions and the so-called "basic steps".
You can not use the abs() function in linear programming

Code: Select all

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

Re: Modeling the absolute value

Posted: Thu Jul 27, 2017 12:54 pm
by PeterBe
Hi,

I inserted following equations:

Code: Select all

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?

Re: Modeling the absolute value

Posted: Thu Jul 27, 2017 2:02 pm
by Manassaldi
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!

Re: Modeling the absolute value

Posted: Fri Jul 28, 2017 8:05 am
by PeterBe
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?

Re: Modeling the absolute value

Posted: Fri Jul 28, 2017 12:53 pm
by Manassaldi
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)
1. REPLACE IMPLICATION BY DISJUNCTION
¬(X ^ Y)˅¬Z
2. MOVE NEGATION INWARD APPLYING DE MORGAN’S THEOREM
¬X ˅ ¬Y ˅¬Z
3. 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!

Re: Modeling the absolute value

Posted: Fri Jul 28, 2017 1:23 pm
by PeterBe
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.