How can I solve this bi-level like problem?

GAMS
1

Hi, I’m chemical engineer in Korea.

I want to solve some kind of bi-level optimization.



Problem statement.

The problem is that there is 10 m by 10 m square area and there are three sensor. Their location vectors are (x(k),y(k)) where k is number of sensor thus in this model it is 3.
A explosion is occurred on the point (xz, yz) and the probability(P) that sensor can detect this explosion is (1-exp(-3/d^2)) where d is Euclidean distance between sensor and explosion.

I want to find the optimal sensor location which maximize the product series of detection probability(P1P2P3).

Thus, I have to make model like

Max { min (product series of detection probability(P1P2P3))}
x,y xz,yz

è This means that maximizing the (minimum probability at the fixed sensor location)



Questions

  1. I think this is bilevel programming, but obj of leader and follower is same. And I don’t know how to formulate this. I want to know the code bilevel optimization for solving this problem. Alternatively, I make the grid and find all minimum probability under all three sensor location combination varying the explosion vector. Then find the maximum value of probability among this minimum solutions. However, it take too long time. I attach the Matlab-GAMS file for this.

  2. I saw the EMP solver and doing for example of bilevel programming. Actually, bilevel programming solution usually like pareto curve. But they give just point. How can I search the set of solution.




    My GAMS CODE

set k/1*3/;

variables

xz

yz

minimum;


parameters

x(k)

y(k)


$gdxin tstdat

$load x y

$gdxin


equations

maxi ;


maxi… minimum =e= 1*(1-exp(-3/((power(xz-x(‘1’),2)+power(yz-y(‘1’),2))+0.00000000000000000001)))*(1-exp(-3/((power(xz-x(‘2’),2)+power(yz-y(‘2’),2))+0.00000000000000000001)))1(1-exp(-3/((power(xz-x(‘3’),2)+power(yz-y(‘3’),2))+0.00000000000000000001)));


xz.up=10;

xz.lo=0;

yz.up=10;

yz.lo=0;


Model super/all/;

OPTION nlp=LINDOGLOBAL;


solve super using nlp minimizing minimum;

display x,y, xz.l, yz.l, minimum.l

execute_unload ‘tstsol’, xz,yz,minimum;


My MATLAB CODE


clc;

clear all;


m=0

for xi=4:8

for xj=4:8

for xk=4:8

for yi=4:8

for yj=4:8

for yk=4:8



Xe = [1*(xi-1) 1*(xj-1) 1*(xk-1)]

Ye = [1*(yi-1) 1*(yj-1) 1*(yk-1)]


xe.name = ‘x’;

xe.type = ‘parameter’;

xe.val = Xe’;

xe.form = ‘full’;

xe.dim = 1;


ye.name = ‘y’;

ye.type = ‘parameter’;

ye.val = Ye’;

ye.form = ‘full’;

ye.dim = 1;


wgdx (‘tstdat’, xe,ye);

gams(‘zone’)


rs1.name = ‘xz’;

rs1.form = ‘full’;

r1 = rgdx (‘tstsol’, rs1);

xz = r1.val;


rs2.name = ‘yz’;

rs2.form = ‘full’;

r2 = rgdx (‘tstsol’, rs2);

yz = r2.val;


rs3.name = ‘minimum’;

rs3.form = ‘full’;

r3 = rgdx (‘tstsol’, rs3);

minimum = r3.val;


m=m+1

Rx(m)=xz

Ry(m)=yz

RRx1(m)=Xe(1);

RRx2(m)=Xe(2);

RRx3(m)=Xe(3);

RRy1(m)=Ye(1);

RRy2(m)=Ye(2);

RRy3(m)=Ye(3);

min(m)=minimum

end

end

end

end

end

end



\

To unsubscribe from this group and stop receiving emails from it, send an email to gamsworld+unsubscribe@googlegroups.com.
To post to this group, send email to gamsworld@googlegroups.com.
Visit this group at http://groups.google.com/group/gamsworld.
For more options, visit https://groups.google.com/d/optout.

2

Hi

I would probably not try it in a bi-level approach.
My guess: try to discretise the set of possible explosion locations (xz, yz) like (xz(i), yz(i) | i=1, …, I).
Let x(k) and y(k) remain variables.
You may then compute P1(z(i)), P2(z(i)) and P3(z(i)) for each possible discrete location z(i).
Now simply state that your objective F must be <= P1(z(i))*P2(z(i))*P3(z(i)) for each possible i,
and maximise F.

You have to ensure that the “granularity” of your discretisation is fine enough… but it should do the job.
Hope this helps

cheers
dax



Le mercredi 25 juin 2014 09:16:35 UTC+2, Jonggeol Na a écrit :

Hi, I’m chemical engineer in Korea.

I want to solve some kind of bi-level optimization.



Problem statement.

The problem is that there is 10 m by 10 m square area and there are three sensor. Their location vectors are (x(k),y(k)) where k is number of sensor thus in this model it is 3.
A explosion is occurred on the point (xz, yz) and the probability(P) that sensor can detect this explosion is (1-exp(-3/d^2)) where d is Euclidean distance between sensor and explosion.

I want to find the optimal sensor location which maximize the product series of detection probability(P1P2P3).

Thus, I have to make model like

Max { min (product series of detection probability(P1P2P3))}
x,y xz,yz

è This means that maximizing the (minimum probability at the fixed sensor location)



Questions

  1. I think this is bilevel programming, but obj of leader and follower is same. And I don’t know how to formulate this. I want to know the code bilevel optimization for solving this problem. Alternatively, I make the grid and find all minimum probability under all three sensor location combination varying the explosion vector. Then find the maximum value of probability among this minimum solutions. However, it take too long time. I attach the Matlab-GAMS file for this.

  2. I saw the EMP solver and doing for example of bilevel programming. Actually, bilevel programming solution usually like pareto curve. But they give just point. How can I search the set of solution.




    My GAMS CODE

set k/1*3/;

variables

xz

yz

minimum;


parameters

x(k)

y(k)


$gdxin tstdat

$load x y

$gdxin


equations

maxi ;


maxi… minimum =e= 1*(1-exp(-3/((power(xz-x(‘1’),2)+power(yz-y(‘1’),2))+0.00000000000000000001)))*(1-exp(-3/((power(xz-x(‘2’),2)+power(yz-y(‘2’),2))+0.00000000000000000001)))1(1-exp(-3/((power(xz-x(‘3’),2)+power(yz-y(‘3’),2))+0.00000000000000000001)));


xz.up=10;

xz.lo=0;

yz.up=10;

yz.lo=0;


Model super/all/;

OPTION nlp=LINDOGLOBAL;


solve super using nlp minimizing minimum;

display x,y, xz.l, yz.l, minimum.l

execute_unload ‘tstsol’, xz,yz,minimum;


My MATLAB CODE


clc;

clear all;


m=0

for xi=4:8

for xj=4:8

for xk=4:8

for yi=4:8

for yj=4:8

for yk=4:8



Xe = [1*(xi-1) 1*(xj-1) 1*(xk-1)]

Ye = [1*(yi-1) 1*(yj-1) 1*(yk-1)]


xe.name = ‘x’;

xe.type = ‘parameter’;

xe.val = Xe’;

xe.form = ‘full’;

xe.dim = 1;


ye.name = ‘y’;

ye.type = ‘parameter’;

ye.val = Ye’;

ye.form = ‘full’;

ye.dim = 1;


wgdx (‘tstdat’, xe,ye);

gams(‘zone’)


rs1.name = ‘xz’;

rs1.form = ‘full’;

r1 = rgdx (‘tstsol’, rs1);

xz = r1.val;


rs2.name = ‘yz’;

rs2.form = ‘full’;

r2 = rgdx (‘tstsol’, rs2);

yz = r2.val;


rs3.name = ‘minimum’;

rs3.form = ‘full’;

r3 = rgdx (‘tstsol’, rs3);

minimum = r3.val;


m=m+1

Rx(m)=xz

Ry(m)=yz

RRx1(m)=Xe(1);

RRx2(m)=Xe(2);

RRx3(m)=Xe(3);

RRy1(m)=Ye(1);

RRy2(m)=Ye(2);

RRy3(m)=Ye(3);

min(m)=minimum

end

end

end

end

end

end



\

To unsubscribe from this group and stop receiving emails from it, send an email to gamsworld+unsubscribe@googlegroups.com.
To post to this group, send email to gamsworld@googlegroups.com.
Visit this group at http://groups.google.com/group/gamsworld.
For more options, visit https://groups.google.com/d/optout.

3

try discrete optimization, and it is easier if you use Matlab and call Cplex via matlab to solve MIP.

Good Luck


On Thu, Jun 26, 2014 at 2:47 AM, dax wrote:

Hi

I would probably not try it in a bi-level approach.
My guess: try to discretise the set of possible explosion locations (xz, yz) like (xz(i), yz(i) | i=1, …, I).
Let x(k) and y(k) remain variables.
You may then compute P1(z(i)), P2(z(i)) and P3(z(i)) for each possible discrete location z(i).
Now simply state that your objective F must be <= P1(z(i))*P2(z(i))*P3(z(i)) for each possible i,
and maximise F.

You have to ensure that the “granularity” of your discretisation is fine enough… but it should do the job.
Hope this helps

cheers
dax



Le mercredi 25 juin 2014 09:16:35 UTC+2, Jonggeol Na a écrit :

Hi, I’m chemical engineer in Korea.

I want to solve some kind of bi-level optimization.



Problem statement.

The problem is that there is 10 m by 10 m square area and there are three sensor. Their location vectors are (x(k),y(k)) where k is number of sensor thus in this model it is 3.
A explosion is occurred on the point (xz, yz) and the probability(P) that sensor can detect this explosion is (1-exp(-3/d^2)) where d is Euclidean distance between sensor and explosion.

I want to find the optimal sensor location which maximize the product series of detection probability(P1P2P3).

Thus, I have to make model like

Max { min (product series of detection probability(P1P2P3))}
x,y xz,yz

è This means that maximizing the (minimum probability at the fixed sensor location)



Questions

  1. I think this is bilevel programming, but obj of leader and follower is same. And I don’t know how to formulate this. I want to know the code bilevel optimization for solving this problem. Alternatively, I make the grid and find all minimum probability under all three sensor location combination varying the explosion vector. Then find the maximum value of probability among this minimum solutions. However, it take too long time. I attach the Matlab-GAMS file for this.

  2. I saw the EMP solver and doing for example of bilevel programming. Actually, bilevel programming solution usually like pareto curve. But they give just point. How can I search the set of solution.




    My GAMS CODE

set k/1*3/;

variables

xz

yz

minimum;


parameters

x(k)

y(k)


$gdxin tstdat

$load x y

$gdxin


equations

maxi ;


maxi… minimum =e= 1*(1-exp(-3/((power(xz-x(‘1’),2)+power(yz-y(‘1’),2))+0.00000000000000000001)))*(1-exp(-3/((power(xz-x(‘2’),2)+power(yz-y(‘2’),2))+0.00000000000000000001)))1(1-exp(-3/((power(xz-x(‘3’),2)+power(yz-y(‘3’),2))+0.00000000000000000001)));


xz.up=10;

xz.lo=0;

yz.up=10;

yz.lo=0;


Model super/all/;

OPTION nlp=LINDOGLOBAL;


solve super using nlp minimizing minimum;

display x,y, xz.l, yz.l, minimum.l

execute_unload ‘tstsol’, xz,yz,minimum;


My MATLAB CODE


clc;

clear all;


m=0

for xi=4:8

for xj=4:8

for xk=4:8

for yi=4:8

for yj=4:8

for yk=4:8



Xe = [1*(xi-1) 1*(xj-1) 1*(xk-1)]

Ye = [1*(yi-1) 1*(yj-1) 1*(yk-1)]


xe.name = ‘x’;

xe.type = ‘parameter’;

xe.val = Xe’;

xe.form = ‘full’;

xe.dim = 1;


ye.name = ‘y’;

ye.type = ‘parameter’;

ye.val = Ye’;

ye.form = ‘full’;

ye.dim = 1;


wgdx (‘tstdat’, xe,ye);

gams(‘zone’)


rs1.name = ‘xz’;

rs1.form = ‘full’;

r1 = rgdx (‘tstsol’, rs1);

xz = r1.val;


rs2.name = ‘yz’;

rs2.form = ‘full’;

r2 = rgdx (‘tstsol’, rs2);

yz = r2.val;


rs3.name = ‘minimum’;

rs3.form = ‘full’;

r3 = rgdx (‘tstsol’, rs3);

minimum = r3.val;


m=m+1

Rx(m)=xz

Ry(m)=yz

RRx1(m)=Xe(1);

RRx2(m)=Xe(2);

RRx3(m)=Xe(3);

RRy1(m)=Ye(1);

RRy2(m)=Ye(2);

RRy3(m)=Ye(3);

min(m)=minimum

end

end

end

end

end

end



\

To unsubscribe from this group and stop receiving emails from it, send an email to gamsworld+unsubscribe@googlegroups.com.
To post to this group, send email to gamsworld@googlegroups.com.
Visit this group at http://groups.google.com/group/gamsworld.
For more options, visit https://groups.google.com/d/optout.



\


\

To unsubscribe from this group and stop receiving emails from it, send an email to gamsworld+unsubscribe@googlegroups.com.
To post to this group, send email to gamsworld@googlegroups.com.
Visit this group at http://groups.google.com/group/gamsworld.
For more options, visit https://groups.google.com/d/optout.