Maximizing the difference in the order of binary variables

Problems with modeling
PeterBe
User
User
Posts: 29
Joined: 8 months ago

Maximizing the difference in the order of binary variables

Postby PeterBe » 4 months ago

Hi guys,

the problem I am facing is going to be difficult to explain and I strongly question whether something like this is solvable with GAMS. But I'll try:

Lets say we have two binary decision variables x(t) and y(t) and lets assume they have the following values:
t: 0 1 2 3 4
x: 0 0 1 0 1
y: 1 0 0 1 0

So now I want to calculate the difference in the order of the value 1 between x(t) and y(t), meaning: the first time y(t)=1 is for t=0 and the first time x(t)=1 is for t=2. So the difference in time is 2-0= 2. The second time y(t)=1 is for t=3 and the second time x(t) = 1 is for t=4. So the difference in time is 4-3=1. The sum of differences is 3.

Now my question is, if it is possible to maximize this difference in time by using GAMS with a solver. This problem also has some constraints that have to be taken into account.

Manassaldi
User
User
Posts: 44
Joined: 10 months ago
Location: Rosario - Argentina

Re: Maximizing the difference in the order of binary variables

Postby Manassaldi » 4 months ago

Hi, I think you should use an auxiliary variable to define the first time of X and Y (same to the second time and third time and so on)

I think this can work :

Code: Select all

eqfirstx(t).. 1 - x(t) + sum(tp$(ord(tp) lt ord(t)),x(tp)) + xfirst(t) =g= 1;
eqfirsty(t).. 1 - y(t) + sum(tp$(ord(tp) lt ord(t)),y(tp)) + yfirst(t) =g= 1;
eqdiffirst..                                   firstdif =e= sum(t,xfirst(t)*(ord(t)-1)) - sum(t,yfirst(t)*(ord(t)-1));
*Similarly for the second time of x:
eqsecondx(t,tp)$(ord(tp) lt ord(t)).. 1 - x(t) + 1 - x(tp) + sum(tpp$(ord(tpp) lt ord(t) and ord(tpp) ne ord(tp)),x(tpp)) + xsecond(t) =g= 1;
eqsecondy(t,tp)$(ord(tp) lt ord(t)).. 1 - y(t) + 1 - y(tp) + sum(tpp$(ord(tpp) lt ord(t) and ord(tpp) ne ord(tp)),y(tpp)) + ysecond(t) =g= 1;
eqdifsecond..                                   seconddif =e= sum(t,xsecond(t)*(ord(t)-1)) - sum(t,ysecond(t)*(ord(t)-1));
eqobj.. z =e=  firstdif + seconddif;
In "sum(t,xfirst(t)*(ord(t)-1)" I use "ord(t)-1" because "ord(t)" indicates the position of the set not its value

Manassaldi
User
User
Posts: 44
Joined: 10 months ago
Location: Rosario - Argentina

Re: Maximizing the difference in the order of binary variables

Postby Manassaldi » 4 months ago

I forgot this equations

Code: Select all

uniquefirstx..     sum(t,xfirst(t)) =e= 1;
uniquefirsty..     sum(t,yfirst(t)) =e= 1;
uniquesecondx.. sum(t,xsecond(t)) =e= 1;
uniquesecondy.. sum(t,ysecond(t)) =e= 1;
Bye!

PeterBe
User
User
Posts: 29
Joined: 8 months ago

Re: Maximizing the difference in the order of binary variables

Postby PeterBe » 4 months ago

Hi Manassaldi,

thank you for your answer. Unfortunately I'm having a hard time understading what you posted. Even the first equation is not understandable for me (I have not tried to understand the other equations yet, because I am struggeling even with the first one):

Code: Select all

eqfirstx(t).. 1 - x(t) + sum(tp$(ord(tp) lt ord(t)),x(tp)) + xfirst(t) =g= 1;
Let's have a look a the exampe:
t: 0 1 2 3 4
x: 0 0 1 0 1
y: 1 0 0 1 0

For t=2
1- 1 + 0 + xfirst(2) =1 --> xfirst(2) = 1

So xfirst(2) should be one. But this cannot be true, since xfirst has to have the value 2, according to my understandings.

Manassaldi
User
User
Posts: 44
Joined: 10 months ago
Location: Rosario - Argentina

Re: Maximizing the difference in the order of binary variables

Postby Manassaldi » 4 months ago

Hi, "xfirst" identifies the position of the first time of x and the term "sum(t,xfirst(t)*(ord(t)-1))" corresponds to its order.

For your example:
t: 0 1 2 3 4
x: 0 0 1 0 1
y: 1 0 0 1 0

For t=2 (correspond to position 3 of the set)
eqfirstx(t=2) --> 1- 1 + 0 + xfirst(2) >=1 --> xfirst(2) = 1
For t=0 (correspond to position 1 of the set)
eqfirsty(t=0) --> 1 - 1 + 0 + yfirst(0) >=1 --> yfirst(0) = 1
If you expand "sum(t,xfirst(t)*(ord(t)-1))" --> xfirst(0)*(1-1) + xfirst(1)*(2-1) + xfirst(2)*(3-1) + xfirst(3)*(4-1) + xfirst(4)*(5-1)
but only xfirst(2) take a value of 1, so: sum(t,xfirst(t)*(ord(t)-1)) = xfirst(2)*(3-1) = 1*(3-1) = 2
Similarly for y: sum(t,yfirst(t)*(ord(t)-1)) = xfirst(0)*(1-1) = = 1*(1-1) = 0
finally
eqdiffirst --> firstdif = 2 - 0 = 2;

firstdif is the difference in the order of the value 1 between x(t) and y(t) for the first time

PeterBe
User
User
Posts: 29
Joined: 8 months ago

Re: Maximizing the difference in the order of binary variables

Postby PeterBe » 4 months ago

Thanks once again Manassaldi for your good answer,

Now I understood how your concept works. You said that I'll have to do this for every occurence of x(t)=1 and y(t)=1 I have to comments/questions regarding this:

1) The number of timeslots, inwhich x(t) = 1and y(t) =1 is not known in advance and has to be determined by the solver itself. As I said earlier there are some constraints that have to be taken into account.

2) Is there a way how to do this more "conveniently" considering that I'll have to do this for 1440 timeslots. Or do I really have to use thousands of equations for that?

Manassaldi
User
User
Posts: 44
Joined: 10 months ago
Location: Rosario - Argentina

Re: Maximizing the difference in the order of binary variables

Postby Manassaldi » 4 months ago

Hi, analyzing more in detail the problem maybe there is a better way to express it.
Perhaps there is a compact way of expressing the constraints.

I think you must to propose the maximum time in which x(t) = 1 and y(t) =1 before, but you have to modifies some restriction.
To consider the case where a "time slot" does not exist all these restrictions have to change to "=l="
uniquefirstx.. sum(t,xfirst(t)) =e= 1; --> uniquefirstx.. sum(t,xfirst(t)) =l= 1;
uniquefirsty.. sum(t,yfirst(t)) =e= 1; --> uniquefirsty.. sum(t,yfirst(t)) =e= 1;
uniquesecondx.. sum(t,xsecond(t)) =e= 1; --> uniquesecondx.. sum(t,xsecond(t)) =e= 1;
uniquesecondy.. sum(t,ysecond(t)) =e= 1; --> uniquesecondy.. sum(t,ysecond(t)) =e= 1;

best regard

PeterBe
User
User
Posts: 29
Joined: 8 months ago

Re: Maximizing the difference in the order of binary variables

Postby PeterBe » 4 months ago

Thanks Manassaldi for your answer (and your general great effort :) ),

I have to admit that I do not really understand the things you said. What is meant by:
I think you must to propose the maximum time in which x(t) = 1 and y(t) =1 before, but you have to modifies some restriction.
As I said in the earlier post. The number of time in which x(t) = 1 and y(t) =1 is not known in advance. I could specify an upper bound for that, but the basic idea is that this number is not known. Are you assuming that there is no way how to handle that?

And you also said that I should change the constraints like this:
uniquefirstx.. sum(t,xfirst(t)) =e= 1; --> uniquefirstx.. sum(t,xfirst(t)) =l= 1;
uniquefirsty.. sum(t,yfirst(t)) =e= 1; --> uniquefirsty.. sum(t,yfirst(t)) =e= 1;
Why do I only have to change uniquefirstx and not uniquefirsty?

Manassaldi
User
User
Posts: 44
Joined: 10 months ago
Location: Rosario - Argentina

Re: Maximizing the difference in the order of binary variables

Postby Manassaldi » 4 months ago

Hi, sorry, it's a mistake
uniquefirstx.. sum(t,xfirst(t)) =e= 1; --> uniquefirstx.. sum(t,xfirst(t)) =l= 1;
uniquefirsty.. sum(t,yfirst(t)) =e= 1; --> uniquefirsty.. sum(t,yfirst(t)) =l= 1;
uniquesecondx.. sum(t,xsecond(t)) =e= 1; --> uniquesecondx.. sum(t,xsecond(t)) =l= 1;
uniquesecondy.. sum(t,ysecond(t)) =e= 1; --> uniquesecondy.. sum(t,ysecond(t)) =l= 1;

Manassaldi
User
User
Posts: 44
Joined: 10 months ago
Location: Rosario - Argentina

Re: Maximizing the difference in the order of binary variables

Postby Manassaldi » 4 months ago

Hi again, you could try with a BIGM reformulation for simplify the wole formulation of the problem
I think it's better to start with 1 instead of 0
Try the next code:

Code: Select all

set
t /1*1440/
;
alias(t,tp,tpp);
binary variable
x(t)
y(t)
;
variable
z
;
equation
eq1,eq2,eq3,eq4,eq5,eq6,eqobj
;

eq1(t,tp).. sum(tpp$(ord(tpp) le ord(t)),x(tpp)) =l= ord(tp) + (1-xpos(tp,t))*1440;
eq2(t,tp).. sum(tpp$(ord(tpp) le ord(t)),x(tpp)) =g= ord(tp) - (1-xpos(tp,t))*1440;
eq3(tp)..   sum(t,xpos(tp,t)) =l= 1;
*same for y
eq4(t,tp).. sum(tpp$(ord(tpp) le ord(t)),y(tpp)) =l= ord(tp) + (1-ypos(tp,t))*1440;
eq5(t,tp).. sum(tpp$(ord(tpp) le ord(t)),y(tpp)) =g= ord(tp) - (1-ypos(tp,t))*1440;
eq6(tp)..   sum(t,ypos(tp,t)) =l= 1;

eqobj.. z =e=  sum(tp, sum(t,xpos(tp,t)*ord(tp)) - sum(t,ypos(tp,t)*ord(tp)));
For example:
t: 1 2 3 4 5 6 ... ... 1440
x: 0 0 1 0 1 0 ...(all 0) 0
y: 1 0 0 1 0 0 ...(all 0) 0

now, only this variables take a value of 1:
xpos('1','3')=1 and xpos('2','5')=1
ypos('1','1')=1 and ypos('2','4')=1

you must check this but I think this can works

Best regard


Who is online

Users browsing this forum: No registered users and 2 guests