Maximizing the difference in the order of binary variables
Maximizing the difference in the order of binary variables
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 20= 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 43=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.
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 20= 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 43=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.

 User
 Posts: 45
 Joined: 1 year ago
 Location: Rosario  Argentina
Re: Maximizing the difference in the order of binary variables
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 :
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
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;

 User
 Posts: 45
 Joined: 1 year ago
 Location: Rosario  Argentina
Re: Maximizing the difference in the order of binary variables
I forgot this equations
Bye!
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;
Re: Maximizing the difference in the order of binary variables
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):
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.
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;
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.

 User
 Posts: 45
 Joined: 1 year ago
 Location: Rosario  Argentina
Re: Maximizing the difference in the order of binary variables
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)*(11) + xfirst(1)*(21) + xfirst(2)*(31) + xfirst(3)*(41) + xfirst(4)*(51)
but only xfirst(2) take a value of 1, so: sum(t,xfirst(t)*(ord(t)1)) = xfirst(2)*(31) = 1*(31) = 2
Similarly for y: sum(t,yfirst(t)*(ord(t)1)) = xfirst(0)*(11) = = 1*(11) = 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
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)*(11) + xfirst(1)*(21) + xfirst(2)*(31) + xfirst(3)*(41) + xfirst(4)*(51)
but only xfirst(2) take a value of 1, so: sum(t,xfirst(t)*(ord(t)1)) = xfirst(2)*(31) = 1*(31) = 2
Similarly for y: sum(t,yfirst(t)*(ord(t)1)) = xfirst(0)*(11) = = 1*(11) = 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
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?
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?

 User
 Posts: 45
 Joined: 1 year ago
 Location: Rosario  Argentina
Re: Maximizing the difference in the order of binary variables
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
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
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:
And you also said that I should change the constraints like this:
I have to admit that I do not really understand the things you said. What is meant by:
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?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.
And you also said that I should change the constraints like this:
Why do I only have to change uniquefirstx and not uniquefirsty?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;

 User
 Posts: 45
 Joined: 1 year ago
 Location: Rosario  Argentina
Re: Maximizing the difference in the order of binary variables
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;
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;

 User
 Posts: 45
 Joined: 1 year ago
 Location: Rosario  Argentina
Re: Maximizing the difference in the order of binary variables
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:
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
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) + (1xpos(tp,t))*1440;
eq2(t,tp).. sum(tpp$(ord(tpp) le ord(t)),x(tpp)) =g= ord(tp)  (1xpos(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) + (1ypos(tp,t))*1440;
eq5(t,tp).. sum(tpp$(ord(tpp) le ord(t)),y(tpp)) =g= ord(tp)  (1ypos(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)));
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