Page 1 of 3
Maximizing the difference in the order of binary variables
Posted: Wed Aug 02, 2017 11:22 am
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.
Re: Maximizing the difference in the order of binary variables
Posted: Wed Aug 02, 2017 5:43 pm
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
Re: Maximizing the difference in the order of binary variables
Posted: Wed Aug 02, 2017 5:51 pm
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!
Re: Maximizing the difference in the order of binary variables
Posted: Thu Aug 03, 2017 6:10 pm
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.
Re: Maximizing the difference in the order of binary variables
Posted: Thu Aug 03, 2017 9:24 pm
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
Re: Maximizing the difference in the order of binary variables
Posted: Fri Aug 04, 2017 2:34 pm
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?
Re: Maximizing the difference in the order of binary variables
Posted: Fri Aug 04, 2017 7:10 pm
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
Re: Maximizing the difference in the order of binary variables
Posted: Mon Aug 07, 2017 10:08 am
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?
Re: Maximizing the difference in the order of binary variables
Posted: Mon Aug 07, 2017 1:14 pm
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;
Re: Maximizing the difference in the order of binary variables
Posted: Mon Aug 07, 2017 3:50 pm
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