Maximizing the difference in the order of binary variables

Problems with modeling
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 that the first approximation generate a smaller model that require lower memory. But i don't know how much memory will consume.
I don't know if there are any way to estimate how much memory the model needs

Best regard
PeterBe
User
User
Posts: 66
Joined: 7 years ago

Re: Maximizing the difference in the order of binary variables

Post by PeterBe »

Hi I'm back again :-)

and I have a question regarding the BigM formulation:
The objective function looks like this :

Code: Select all

 sum(tp, sum (t,xpos(tp,t)*ord(tp)) - sum(t,ypos(tp,t)*ord(tp)));
How can I model the absolute value of the inner sum? Meaning:

Code: Select all

 sum(tp, ABS{sum (t,xpos(tp,t)*ord(tp)) - sum(t,ypos(tp,t)*ord(tp))});
I had a look at my other topic: Modeling the absolute value (viewtopic.php?f=9&t=9923&start=10)
There one answer was:

Re: Modeling the absolute value

Report this post
Quote
Accept this answer

Unread postby Manassaldi » 3 weeks ago
Hi again PeterBe, I think this can works

x(t) and c(t) are continuous variables
p(t) are binary variables
M is a sufficiently large number (BigM parameter)

if "p=1", by "eq3" (x-c) is greater than 0 so by "eq1" and "eq2" absvalue = x-c (the rest of equation are also satisfied)
if "p=0", by "eq6" (x-c) is lower than 0 so by "eq4" and "eq5" absvalue = c-x (the rest of equation are also satisfied)

eq1(t).. absvalue(t) =l= x(t) - c(t) + (1-p(t))*M;
eq2(t).. absvalue(t) =g= x(t) - c(t) - (1-p(t))*M;
eq3(t).. x(t) - c(t) =g= -(1-p(t))*M
eq4(t).. absvalue(t) =l= c(t) - x(t) + p(t)*M;
eq5(t).. absvalue(t) =g= c(t) - x(t) - p(t)*M;
eq6(t).. x(t) - c(t) =l= p(t)*M
eq7.. z =e= sum(t,absvalue(t))

All this restrictions are for "z = sum(t,abs(x(t)-c(t)))" with x and c continuous variables

Bye!
How can I transfer this to this problem?

Thanky in advance for your suggestion. I really appreciate it.
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 can try with this...

eq01(tp).. x(tp) =e= sum(t,xpos(tp,t)*ord(tp))
eq02(tp).. c(tp) =e= sum(t,ypos(tp,t)*ord(tp))});
eq1(tp).. absvalue(tp) =l= x(tp) - c(tp) + (1-p(tp))*M;
eq2(tp).. absvalue(tp) =g= x(tp) - c(tp) - (1-p(tp))*M;
eq3(tp).. x(tp) - c(tp) =g= -(1-p(tp))*M
eq4(tp).. absvalue(tp) =l= c(tp) - x(tp) + p(tp)*M;
eq5(tp).. vabsvalue(tp) =g= c(tp) - x(tp) - p(tp)*M;
eq6(tp).. x(tp) - c(tp) =l= p(tp)*M
eq7.. z =e= sum(tp,absvalue(tp))
PeterBe
User
User
Posts: 66
Joined: 7 years ago

Re: Maximizing the difference in the order of binary variables

Post by PeterBe »

Thanks for your answer Manassaldi

eq01(tp).. x(tp) =e= sum(t,xpos(tp,t)*ord(tp))
eq02(tp).. c(tp) =e= sum(t,ypos(tp,t)*ord(tp))});
eq1(tp).. absvalue(tp) =l= x(tp) - c(tp) + (1-p(tp))*M;
eq2(tp).. absvalue(tp) =g= x(tp) - c(tp) - (1-p(tp))*M;
eq3(tp).. x(tp) - c(tp) =g= -(1-p(tp))*M
eq4(tp).. absvalue(tp) =l= c(tp) - x(tp) + p(tp)*M;
eq5(tp).. vabsvalue(tp) =g= c(tp) - x(tp) - p(tp)*M;
eq6(tp).. x(tp) - c(tp) =l= p(tp)*M
eq7.. z =e= sum(tp,absvalue(tp))
Is x(tp) a binary variable. Because as far as I understood x(tp) is a continious variable whereas in the previous models (BigM) x(tp) is a binary variable. I am talking about the model that you posted some weeks ago:

Code: Select all

et
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)));
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, x(tp) is the sum of the product between a binary variable and its position, so I suppose that is an integer variable (not binary). Anyway, I think it's better to define it as a continuous variable.
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 effort :-)
Hi, x(tp) is the sum of the product between a binary variable and its position, so I suppose that is an integer variable (not binary). Anyway, I think it's better to define it as a continuous variable.
I think I am getting confused. Let's have a look at the BigM fomulation:

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)));
x(t) has to be a binary variable . Basically I do not want to change anything except "insert" the absolute value in the last equation:

Code: Select all

eqobj.. z =e=  sum(tp, ABS{sum(t,xpos(tp,t)*ord(tp)) - sum(t,ypos(tp,t)*ord(tp))});
So the question is: how can I "insert" this absolute function without changing the model itself. So there was this idea by Mansassaldi:

Code: Select all

eq01(tp).. x(tp) =e= sum(t,xpos(tp,t)*ord(tp))
eq02(tp).. c(tp) =e= sum(t,ypos(tp,t)*ord(tp))});
eq1(tp).. absvalue(tp) =l= x(tp) - c(tp) + (1-p(tp))*M;
eq2(tp).. absvalue(tp) =g= x(tp) - c(tp) - (1-p(tp))*M;
eq3(tp).. x(tp) - c(tp) =g= -(1-p(tp))*M
eq4(tp).. absvalue(tp) =l= c(tp) - x(tp) + p(tp)*M;
eq5(tp).. vabsvalue(tp) =g= c(tp) - x(tp) - p(tp)*M;
eq6(tp).. x(tp) - c(tp) =l= p(tp)*M
eq7.. z =e= sum(tp,absvalue(tp))
How can I combine those two formulation (if that is possible)? You simply cannot define x(t) to be a continious variable because then the first fomulation (BIgM) will not make sense
PeterBe
User
User
Posts: 66
Joined: 7 years ago

Re: Maximizing the difference in the order of binary variables

Post by PeterBe »

So you canot thinkg about a way how to combine the inital BigM formulation with the "absoulte value" in the objective function? It ried to combine the two formulations but did not really know how to do 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, I do not completely remember your model. I think this can work.


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;
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).. sumx(tp) =e= sum(t,xpos(tp,t)*ord(tp))
eq8(tp).. sumy(tp) =e= sum(t,ypos(tp,t)*ord(tp));
eq9(tp).. absvalue(tp) =l= sumx(tp) - sumy(tp) + (1-p(tp))*M;
eq10(tp).. absvalue(tp) =g= sumx(tp) - sumy(tp) - (1-p(tp))*M;
eq11(tp).. sumx(tp) - sumy(tp) =g= -(1-p(tp))*M
eq12(tp).. absvalue(tp) =l= sumy(tp) - sumx(tp) + p(tp)*M;
eq13(tp).. absvalue(tp) =g= sumy(tp) - sumx(tp) - p(tp)*M;
eq14(tp).. sumx(tp) - sumy(tp) =l= p(tp)*M;
eq15.. z =e= sum(tp,absvalue(tp));

Bye
PeterBe
User
User
Posts: 66
Joined: 7 years ago

Re: Maximizing the difference in the order of binary variables

Post by PeterBe »

Thanks a lot Manassaldi for your effort once again :-)

My model is on the first page of the thread. Here you can see it again:

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 will try your suggestion.
Post Reply