Maximizing the difference in the order of binary variables

Problems with modeling
PeterBe
User
User
Posts: 66
Joined: 7 years ago

Maximizing the difference in the order of binary variables

Post by PeterBe »

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: 118
Joined: 7 years ago
Location: Rosario - Argentina

Re: Maximizing the difference in the order of binary variables

Post by Manassaldi »

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: 118
Joined: 7 years ago
Location: Rosario - Argentina

Re: Maximizing the difference in the order of binary variables

Post by Manassaldi »

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: 66
Joined: 7 years ago

Re: Maximizing the difference in the order of binary variables

Post by PeterBe »

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: 118
Joined: 7 years ago
Location: Rosario - Argentina

Re: Maximizing the difference in the order of binary variables

Post by Manassaldi »

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: 66
Joined: 7 years ago

Re: Maximizing the difference in the order of binary variables

Post by PeterBe »

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: 118
Joined: 7 years ago
Location: Rosario - Argentina

Re: Maximizing the difference in the order of binary variables

Post by Manassaldi »

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: 66
Joined: 7 years ago

Re: Maximizing the difference in the order of binary variables

Post by PeterBe »

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: 118
Joined: 7 years ago
Location: Rosario - Argentina

Re: Maximizing the difference in the order of binary variables

Post by Manassaldi »

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: 118
Joined: 7 years ago
Location: Rosario - Argentina

Re: Maximizing the difference in the order of binary variables

Post by Manassaldi »

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
Post Reply