Modeling the absolute value

Problems with modeling
PeterBe
User
User
Posts: 64
Joined: 1 year ago

Modeling the absolute value

Post by PeterBe » 1 year ago

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.

Online
Manassaldi
User
User
Posts: 71
Joined: 1 year ago
Location: Rosario - Argentina

Re: Modeling the absolute value

Post by Manassaldi » 1 year ago

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

PeterBe
User
User
Posts: 64
Joined: 1 year ago

Re: Modeling the absolute value

Post by PeterBe » 1 year ago

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
User
User
Posts: 64
Joined: 1 year ago

Re: Modeling the absolute value

Post by PeterBe » 1 year ago

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?

Online
Manassaldi
User
User
Posts: 71
Joined: 1 year ago
Location: Rosario - Argentina

Re: Modeling the absolute value

Post by Manassaldi » 1 year ago

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

PeterBe
User
User
Posts: 64
Joined: 1 year ago

Re: Modeling the absolute value

Post by PeterBe » 1 year ago

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?

Online
Manassaldi
User
User
Posts: 71
Joined: 1 year ago
Location: Rosario - Argentina

Re: Modeling the absolute value

Post by Manassaldi » 1 year ago

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
User
User
Posts: 64
Joined: 1 year ago

Re: Modeling the absolute value

Post by PeterBe » 1 year ago

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?

Online
Manassaldi
User
User
Posts: 71
Joined: 1 year ago
Location: Rosario - Argentina

Re: Modeling the absolute value

Post by Manassaldi » 1 year ago

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!

PeterBe
User
User
Posts: 64
Joined: 1 year ago

Re: Modeling the absolute value

Post by PeterBe » 1 year ago

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.

Post Reply