'Misbehaving' follower in bi-level optimization model Topic is solved

[O'Jhene]

Hello Everyone,

I'm currently working on a bi-level optimization model that seems to behave strangely. Please find my equations below. I have set Bgt=30 and Cf=30. Therefore, per constraint 1 (con1), both et(i,j)=0 and ek(i,j)=0 for all eligible (i,j) pairs. This is what the solver selects. Then, per con8, con9 and con10, y(i,j) is free to be 0 or 1, which is what I expect. But for some strange reason, the solver refuses to select y(i,j)=1, it always sets y(i,j)=0. In fact, when I change the '=L=' to '=E=' in con9, which is a valid constraint, it claims the model is infeasible. I just cannot tell what is going on and would appreciate your help on this. I tried some of the methods here (https://www.gams.com/blog/2017/07/misbe ... nfeasible/), but nothing has worked so far. Please note that et(i,j), ek(i,j) and z(Ds) are binary variables that belong to the leader problem, whereas y(i,j) and all other variables belong to the follower. Also, con1 belongs to the leader, and because of its variables, con8 as well.

Code: Select all

P.up(D,ph)$(Dph(D,ph)) = LoadData(D,ph,'Pmax');
P.lo(D,ph)$(Dph(D,ph)) = 0;

Pline.up(i,j,ph)$(Eph(i,j,ph)$(not Esph(i,j,ph))) = Vbase*F(i,j,ph,'Ampacity');
Pline.lo(i,j,ph)$(Eph(i,j,ph)$(not Esph(i,j,ph))) = -Vbase*F(i,j,ph,'Ampacity');

Pg.lo(src,ph) = 0;

con1..                              Cf + sum(Ds, Cd(Ds)*(1-z(Ds))) + sum((i,j)$(Es(i,j)), Ce(i,j)*(et(i,j) + ek(i,j))) =L= Bgt;
con2(src,ph)..                      Pg(src,ph) =E= sum(j$(E(src,j) ), Pline(src,j,ph));
con3(D,ph)$(Dph(D,ph))..            P(D,ph) =E= sum(i$(Eph(i,D,ph)), Pline(i,D,ph)) - sum(j$(Eph(D,j,ph)), Pline(D,j,ph));
con4(i,j,ph)$(Esph(i,j,ph))..       Pline(i,j,ph) =L= s(i,j)*Vbase*F(i,j,ph,'Ampacity');
con5(i,j,ph)$(Esph(i,j,ph))..       Pline(i,j,ph) =G= -s(i,j)*Vbase*F(i,j,ph,'Ampacity');
con6(Ds,ph)$(Dsph(Ds,ph))..         P(Ds,ph) =L= z(Ds)*LoadData(Ds,ph,'Pmax');
con7(i,j,ph)$(Eph(i,j,ph))..        Pline(i,j,ph) =L= sum(src,Pg(src,ph));
con8(i,j)$(Es(i,j))..               ek(i,j) =L= 1 - et(i,j);
con9(i,j)$(Es(i,j))..               y(i,j) =L= 1 - et(i,j) - ek(i,j);
con10(i,j)$(Es(i,j))..              y(i,j)*(1-y(i,j)) =E= 0;
con11(i,j)$(Es(i,j))..              s(i,j) =E= et(i,j)*(1 - sc(i,j)) + ek(i,j)*sc(i,j) + y(i,j);
objIn..                             OFin =E= sum((D,ph)$(Dph(D,ph)),P(D,ph));
objOut..                            OFout =E= R * sum((D,ph)$(Dph(D,ph)), LoadData(D,ph,'Criticality')*(LoadData(D,ph,'Pmax') - P(D,ph)))
                                    - (Cf + sum(Ds, Cd(Ds)*(1-z(Ds))) + sum((i,j)$(Es(i,j)), Ce(i,j)*(et(i,j) + ek(i,j))));                               


Model AttackerProblem /all/;

* For running on NEOS while in GAMS Studio
FILE info / ' ' /;
put_utility info 'ren' / gams.scrDir 'empinfo.' gams.ScrExt
PUTCLOSE info "bilevel et ek z max OFin * objin con2 con3 con4 con5 con6 con7 con9 con10 con11" /;

Solve AttackerProblem using EMP maximizing OFout; 

[O'Jhene]

I've worked on it some more and come across a rather strange problem. The problem is with s(i,j); for some reason, it doesn't want to be anything but 0.
Two experiments:
1. Set s(i,j) in con11 to a fixed value such as 0.5 (instead of the rhs function) while keeping s(i,j) in con4 and con5. This won't work.
2. Comment out con 11 and remove it from the follower variables, and replace s(i,j) in con4 and con5 with 0.5. This works. But this is technically the same as experiment 1.

You can change 0.5 to any number you want, and you would get the same outcome. But if you set it to 0, it works for some strange reason. I have searched my model and I can confirm that the variable s is unique and only appears as s(i,j). At this point, I'm not sure what is going on . Please help.

[dirkse]

Hi,

I believe forum users would be more able and willing to help you if you followed the forum rules:

app.php/rules

A few observations on your model spring to mind:
1. If you have issues with infeasibility, first try to relax all the integrality constraints and see if that makes things feasible.
2. Your constraints require y to be binary, i.e. to take on 0/1 values, without making it a binary variable. But there is no free lunch here. This constraint is nonconvex and will cause some solvers difficulty. It is possible that a solution exists but the solver you choose cannot find it.
3. If you want to fix y at 1 to test your conjecture that y=1 is a feasible point, then do this directly: set y.fx(i,j) = 1;

HTH,

-Steve

[O'Jhene]

Thanks for your response Steve. As indicated in my follow-up post, the problem is with s(i,j). And it behaves in a manner I believe is strange. For instance, if I replace con11 with

Code: Select all

s(i,j) =E= 1

it does not run at all and claims it is infeasible. Nevertheless, if I remove con11 and use .fx for all my (i,j) pairs (as I've done for one pair below), it works fine.

Code: Select all

s.fx('450','451') = 1

Unfortunately, I can't see how to attach my code so you can help with it.

[O'Jhene]

Hi Steve,

I have attached my code here.

Thanks.

[O'Jhene]

Hi Steve\Everyone,

Were you able to find the problem? I have added a dummy variable, dummy(i,j) and a dummy constraint, con12, and placed dummy(i,j) in con4 and con5, and it says it's infeasible. But if you take out dummy(i,j) from con4 and con5, and comment out con12, it works fine, and both are supposed to be technically the same thing. Please help.

[O'Jhene]

Thanks Steve, I found the issue. Doing

Code: Select all

s(i,j) =E= some_number_apart_from_0

wasn't good. I'm going with your initial suggestion to relax y.