Maximizing the difference in the order of binary variables

Problems with modeling
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,

but I do nor understand your 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)));
I have several questions and comments:
1) xpos(tp,t) and ypos(tp,t) are not declared in your model description. They are only unsed in the equations. Is it not necessary to define them?
2) Basically I have to admit that I do not understand much of your code and I am confused (I spend many hours trying to understand). What are eq1, eq2 and eq3 ensuring? On the left side of eq1 and eq2 your are counting the number of times x(t)=1 until t. But on the right side you are using tp which I don't understand. When xpos(tp,t) =0, eq1 and eq2 ensure that the sum equals ord(tp). Let's say tp=1000 and t is any number (lets say t=1010) and xpos(tp,t)=1, then eq1 and eq2 - according to my understandig - force the sum of x(t)=1 for t in [0,..., 1005] to be 1000. That means that x(t) is almost always 1. But when I have constraints that forbid something like this there will not be a feasible solution.
3) I guess I have to insert equations for every timeslot and every binary variable, meaning that I have to insert - taking your suggestion - at least 4*1440 = 5760 equations manually. This is also not really doable for me. It would take a fairly long time and there will surely be mistakes in several of those equations which I'll not be able to find.

I know that this question is a fairly difficult one. But I at least want to try to solve it. This is why I really appreciate your input (and the inputs of others)
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 Peter,
I forgot to define the variables because I wrote them fast in the browser without checking them in GAMS.
xpos(tp,t) and ypos(tp,t) are binary variable

For example,
if xpos('1','4')=1 this mean thats the first time of x it happen in the fouth order (tp=1 and t=4)
if xpos('2','10')=1 this mean thats the second time of x it happen in the tenth order (tp=2 and t=10)
.
.
.
if xpos('50','1000')=1 this mean thats the fiftieth time of x it happen in the thousandth order (tp=50 and t=1000)

But, if for the rest of restriction x it happen only 50 time, the rest of the variables xpos take a values of 0
( xpos('51',t)=xpos('52',t)=xpos('53',t)=...=xpos('1440',t)=0 )

For the previusly example, xpos('1','4')=1 (tp=1 and t=4)
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;
replacing and expanding
eq1('4','1').. x('1') + x('2') + x('3') + x('4') =l= 1 + (1-1)*1440;
eq2('4','1').. x('1') + x('2') + x('3') + x('4') =g= 1 - (1-1)*1440;
and
x('1') + x('2') + x('3') + x('4') = 1

if xpos('1','4')=1 the rest of xpos('1',t) (t ne 4) take a value of 0, so
eq1(t,'1').. sum(tpp$(ord(tpp) le ord(t)),x(tpp)) =l= 1 + (1-0)*1440;
eq2(t,'1').. sum(tpp$(ord(tpp) le ord(t)),x(tpp)) =g= 1 - (1-0)*1440;
finally
eq1(t,'1').. sum(tpp$(ord(tpp) le ord(t)),x(tpp)) =l= 1441;
eq2(t,'1').. sum(tpp$(ord(tpp) le ord(t)),x(tpp)) =g= 1441;
eq1 and eq2 always be satisfied in this case

Analyzing your questions, I noted that you must to aggregate the eq7 and eq8
I think that this equations can represent all your problem. This focus is so-called "BigM relaxation"

Anyway, only you know all the problem and you must to vericated all equations.

I hope this can help you
bye!

Code: Select all

set
t /1*1440/
;
alias(t,tp,tpp);
binary variable
x(t)
y(t)
xpos(tp,t)
ypos(tp,t)

;
variable
z
;
equation
eq1,eq2,eq3,eq4,eq5,eq6,eq7,eq8,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;

eq7(tp,t)..  1-xpos(tp,t) + x(t) =g= 1;
eq8(tp,t)..  1-ypos(tp,t) + y(t) =g= 1;

eqobj.. z =e=  sum(tp, sum(t,xpos(tp,t)*ord(tp)) - sum(t,ypos(tp,t)*ord(tp)));
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 think that the first formulation of the problem is better than the BigM.
In the first approximation you must to type more equation but the final size is lower.
Maybe, if you could found a compact way to express the first formulation the model will result small an easy to implement.

If an upper bound is proposed for the number of time in which x=1 (an upper bound not the exact number of time in which x=1) you can reduce the model size significantly.
For example: maximum number of time in which x=1 --> 50

For the first formulation:

Code: Select all

eqfirstx(t).. 1 - x(t) + sum(tp$(ord(tp) lt ord(t)),x(tp)) + xfirst(t) =g= 1;
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;
eqthridx(t,tp,tpp)$(ord(tp) lt ord(t) and ord(tpp) lt ord(t)).. 1 - x(t) + 1 - x(tp) + 1 - x(tpp) + sum(tppp$(ord(tppp) lt ord(t) and ord(tppp) ne ord(tp)  and ord(tppp) ne ord(tpp)),x(tppp)) + xthrid(t) =g= 1;
.
.
.
eqfiftiethx(t,tp)  --> Analogously to the second and thrid but taken from a 50
For the BigM formulation:

Code: Select all

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

eq7(tp,t)$(ord(tp) le Maxim)..  1-xpos(tp,t) + x(t) =g= 1;
eq8(tp,t)$(ord(tp) le Maxim)..  1-ypos(tp,t) + y(t) =g= 1;

eqobj.. z =e=  sum(tp$(ord(tp) le Maxim), sum(t,xpos(tp,t)*ord(tp)) - sum(t,ypos(tp,t)*ord(tp)));
I hope this can help you
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 answers

I still have questions:

1) In your first formulation I think you have to insert equations for all timeslots and the number of time in which x is has to be know in advance. Is that correct?

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;
2) Just a general question: x(t) and y(t) should still be binary decision variables. Ist it possible to addconstraints that only refer to x(t) and y(t) and not to xpos(tp, t) and ypos (tp, t)? For example the one I asked two weeks ago in this forum (https://forum.gamsworld.org/viewtopic.php?f=9&t=10040) and other constraints
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,
1) In your first formulation I think you have to insert equations for all timeslots and the number of time in which x is has to be know in
advance. Is that correct?

You have to propose the maximum number of time in which x=1, this is an upper bound. You don't has to know the number of time in which x=1 in advance, just only an upper bound.
So, if this upper bound is equal to 50 you have to insert 50 equation for x and 50 for y.
Later, if x is equal 1 only forty time, xfortyone(t), xfortytwo(t),... and xfifty(t) will be equal zero.


2) Just a general question: x(t) and y(t) should still be binary decision variables. Ist it possible to addconstraints that only refer to x(t) and y(t) and not to xpos(tp, t) and ypos (tp, t)? For example the one I asked two weeks ago in this forum (viewtopic.php?f=9&t=10040) and other constraints

xpos(tp, t) and ypos(tp,t) are auxiliary variable only to identifies the order
Anyway, i suggest to you that use the first approximation

I hope this can help you
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,
So, if this upper bound is equal to 50 you have to insert 50 equation for x and 50 for y.
I don't really have an upper bound. The only upper bound I have is the number of timeslots,which is 1440. So I have to insert 1440 *2= 2880 equations when using the first approximation? What about the BigM-relaxation? Do I also have to use thousands of equations there?
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 Peter,
no, for bigM reformultation you don't have to use thousands of equations. The model that I showed was complete, but when is expanded is very bigger.
As i say previously, if you could found a compact way to express the first formulation of the problem the model will result more small and easy to implement.

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,

i tried to execute the BigM-Relaxation approach of my model. However my computer was out of memory. The workspace was more than 27.000 Mb and then GAMS stopped with the message "Out of memory".

I think by memory GAMS is referring to RAM and not to harddrive. Because on my harddrive there is more than 100 GB left but my RAM is only 8 GB.
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 »

Yes, this BigM formulation generates a very large model...
PeterBe
User
User
Posts: 66
Joined: 7 years ago

Re: Maximizing the difference in the order of binary variables

Post by PeterBe »

Yes, this BigM formulation generates a very large model...
Two question regarding this:
1) Does the first approximation generate a smaller model which does not need to much memory? Or do you know any other way how to reduce the required memory size?

2) Is there a way to roughly estimate how much memory this BigM formulation of my model needs? Because I could use other computers which have more than 8GB memory. But I should only use them if I know that it will be useful
Post Reply