## Maximizing the difference in the order of binary variables

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

### 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 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
Posts: 60
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 :

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
Posts: 60
Joined: 1 year ago
Location: Rosario - Argentina

### Re: Maximizing the difference in the order of binary variables

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

### 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):

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
Posts: 60
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.

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

### Re: Maximizing the difference in the order of binary variables

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
Posts: 60
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

PeterBe
User
Posts: 62
Joined: 1 year ago

### Re: Maximizing the difference in the order of binary variables

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
Posts: 60
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;

Manassaldi
User
Posts: 60
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
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