Re: Question on a bilevel problem and transfer it to an MILP problem using Yalmip

[Johan Löfberg]

What does the L stand for in MILP?

[Johan Löfberg]

Is your model linear...?

[Stephanie]

just now I checked my problem and found that I added the objective function,which is nonlinear =_=And I remove it to make the objective function blank and the result turned out to be all the variables are zeros (It is ok that objective function is removed because constraints are enough I think)and it obviouly not the optimal solution I want. and I think maybe it is just a local optimal point? How can I find the global optimal solution?

[Johan Löfberg]

Precisely, you have a nasty nonconvex mixed-integer problem. The solution you get by simply solving the feasibility problem is most likely completely uninteresting.

There is no simple way to solve these, if even possible at all. Is it easier than your original nonlinear form of the bilevel problem? Not clear

The way I have solved mixed-integer nonconvex quadratics is by posing the KKT conditions of the indefinite QP with the binaries relaxed, and treated them as outer variables in a bivel program, and handle the KKT conditions using binary models (precisely as you do now, just in two steps, i.e. KKt conditions of the indefinite QP hich arise when you apply the kkt conditions of the original problem) Once you have the kkt conditions of the indefinite QP, you think of fixing the binaries as an outer problem. Doing this manully as you currently do sounds horrible (as your code already now looks pretty messy), that's why I use the kkt operator etc when doing that. However, with the size of your problem, I would have very little hope that this would be a tractable approach.

[Johan Löfberg]

YALMIP can automatically derive kkt conditions, and formulate as MILPs, and thus automatically create basic bilevel solvers etc

https://yalmip.github.io/command/kkt/

[Johan Löfberg]

BTW, most likely you don't want betarmin to be symmetric (you've defined it as such now as k=n)

https://yalmip.github.io/tutorial/basics/

[Johan Löfberg]

and clearly your model is flawed, as already this model leads to PG=0 being the only feasible solution, which is unreasonable according to your claims on the gurobi group

FF=(sita(1)==0);

pinj=sdpvar(n,1);%ûÓÐÓõ½Õâ¸ö±äÁ¿

PGn=zeros(n,2);%ÅжÏÿ¸ö½ÚµãÊÇ·ñÓлú×é,µÚÒ»ÁÐΪ1±íʾÓУ¬µÚ¶þÁбíʾÔÚ¶ÔÓ¦µÄ½ÚµãλÖÃ

PDn=zeros(n,2);%ÅжÏÿ¸ö½ÚµãÊÇ·ñÓиººÉ

lambdaG=sdpvar(Ng,1);%ÿ¸ö»ú×é¶ÔÓ¦ËùÔÚ½ÚµãµÄLMP

lambdaD=sdpvar(Nd,1);

for i=1:k

    if i<=Ng

        FF=[FF,pinj(array(i,2))==pinj(array(i,2))+PG(i)];%ÒýÈëPinjÓ¦¸ÃÊDz»»á¶àÒýÈë±äÁ¿µÄ£¬Ã¿¸ö½Úµã±ØÓлú×é»ò¸ººÉ

        FF=[FF,lambdaG(i)==lambda(array(i,2))];%lambdaGÖеÄÿһ¸ö±äÁ¿¶¼ÊÇÒÑÓеģ¬Ó¦¸ÃÒ²ÊÇûÎÊÌâµÄ

        PGn(array(i,2),1)=1;

        PGn(array(i,2),2)=i;%ij¸ö½ÚµãÉÏÓлú×éi

    else

        FF=[FF,pinj(array(i,2))==pinj(array(i,2))-PD(i-Ng)];

        FF=[FF,lambdaD(i-Ng)==lambda(array(i,2))];

        PDn(array(i,2),1)=1;

        PDn(array(i,2),2)=i-Ng;%ij¸ö½ÚµãÉÏÓиººÉi

    end

end
optimize(FF,-PG(1))

[Johan Löfberg]

This

FF=[FF,pinj(array(i,2))==pinj(array(i,2))+PG(i)]

effectively says 0 == PG(i)

[Johan Löfberg]

Remove stuff until it starts behaving as expected, then add stuff until it doesn't

https://yalmip.github.io/debugginginfeasible/

[Johan Löfberg]

I presume you mean double-sided inequalities

if such a small change makes a big difference, it simply tells you that the problem perhaps is ill-posed. Not much to do except trying to come up with a better model