use KKT or bilevel to solve MAXMIN

[Jingle Li]

Dear Prof. Löfberg,

 

If I want to solve a problem like P2:

P2 : Q(y) = {max _u∈U min _x   b^T x : Gx ≥ h - Ey - Mu, Lu<=g, x ∈ Sx}.

Where u are binary variables, x are continuous variables, including x1,x2,x3

Consider P2. which is identical to:

Q(y)= max _u,x(z)

s.t. z<= min { b^T x : Gx ≥ h - Ey – Mu, x ∈ Sx }% The right-hand sides are (LP)

       Lu<=g

       Let π be the vector of dual variables to the second-stage decision problem. Using KKT conditions, P2 is equivalent to the following:

max b^T x                            (1)
s.t. Gx ≥ h - Ey - Mu                 (2)
GT π ≤ b                                       (3)
(Gx - h + Ey + Mu)iπi = 0, ∀i      (4)
(b - G^T π)jxj = 0, ∀j                        (5)
x ∈ Sx, π ≥ 0.                              (6)

u ∈ U, Lu<=g                            (7)

 

1)     If I try to solve P2 using Yalmip in this way:

f= b^T x;

F=[constraints(1), constraints(2),……, constraints(7)];

[k,details]=kkt(F,f,u);

optimize([details.dual>=0,details.dualeq>=0,k,F],-f)

 

2)     Or I want to using bi-level to solve the problem:

OO= b^T x;

CO=[ constraints(7)];

 

OI= b^T x;

CI=[constraints(1), constraints(2),……, constraints(6)];

solvebilevel(CO, -OO, CI, OI, [x1,x2,x3]); However, x1, x2, x3 have different dimensions, so I cannot put them together like [x1,x2,x3].

I know there are many mistakes in my approach .But what are the main mistakes, and how can I correct them?

 

[Johan Löfberg]

1. Dual variables for inequalities are already constrained to be non-negative, what you have to add is upper bounds on these. Dual variables for equalities should not be constrained

2. Hence create [x1(:);x2(:);x3(:)]

[Jingle Li]

Thank you very much for your reply.

As I mentioned earlier, I tried to solve the MaxMin problem by using KKT or bi-level，but I met some problems.

1)As for KKT, the MATLAB show:

Removed 2272 duplicated or redundant inequalities

Transfered 24 inequalities to equalities

Starting derivation of dual bounds (can be turned off using option kkt.dualbounds)

*Computing 224 primal bounds (required for dual bounds)

*Computing 112 bounds on parameterized RHS (required for dual bounds)

*Computing 112 dual bounds

*Warning: Some of the dual upper bounds are infinite

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

|   ID|                     Constraint|                                             Tag|

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

|   #1|     Complementarity constraint|   Compl. slackness and primal-dual inequalities|

|   #2|      Equality constraint 182x1|                                 Primal feasible|

|   #3|   Element-wise inequality 42x1|                            Upper bound on duals|

|   #4|      Equality constraint 224x1|                                    Stationarity|

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

details = 

            info: 'min c'x s.t. Ax<b, Ex=f'

               c: [224x1 double]

               Q: [224x224 double]

               A: [112x224 double]

               b: [112x1 sdpvar]

               E: [182x224 double]

               f: [182x1 double]

            dual: [112x1 sdpvar]

          dualeq: [182x1 sdpvar]

          primal: [224x1 sdpvar]

    inequalities: [1x1 constraint]

      equalities: [1x1 constraint]

      dualbounds: [112x1 double]

CPXPARAM_MIP_Display                             1

Dual infeasible due to empty column 'x421'.

Presolve time = 0.00 sec. (0.12 ticks)

2) As for bi-level,it has so many iterations, and it can't get the optimal solution.

My model looks like this:

where the inner  is LP, and the outer  is the 0-1 programming problem. And I think my model is not very difficult. It can be  solved with kkt, bi-level or strong duality. What's the main problem with my code? How do I handle it?

Or my thoughts are wrong, and I should write Benders decomposition algorithm(or CC&G) to deal with such problems.

Thank you very much again

[Johan Löfberg]

you mean  CO=[z<=sum(ls_n)] 

[Jingle Li]

Yeah, and I made the following corrections:

   OO=z;

  

   CO=[];

   %Attack cost constraint  

   CO=[CO,sum(sum(X_e))<=attack_budget,z<=sum(ls_n);];

   %If the line is not connected, it cannot be attacked,namely  X_e(C==L)=0

   CO=[CO,X_e(C==L)==0];

   ops = sdpsettings('verbose',2);

   solvesdp([k,CO,boundingbox([CI,CO]),details.dual<=1e4],-OO)

 

 

But there are still problems. Both kkt and bi-level took a lot of time, and they didn't work out.

[Johan Löfberg]

the manual kkt version terminates already in the root-node, i.e. trivial

Found heuristic solution: objective -259.0000000

Explored 0 nodes (0 simplex iterations) in 0.07 seconds

Thread count was 4 (of 4 available processors)

Solution count 1: -259 

Optimal solution found (tolerance 1.00e-04)

Best objective -2.590000000000e+02, best bound -2.590000000000e+02, gap 0.0000%

ans = 

  struct with fields:

    yalmiptime: 2.2871

    solvertime: 0.1369

          info: 'Successfully solved (GUROBI-GUROBI)'

       problem: 0

The solvebilevel version runs forever (to be expected...). The lower bound is -259, so that is consistent with the solution found above which is good to see

[Jingle Li]

Thank you, professor. 

There should be another mistake in the second document I sent before.

I think this code should be-----solvesdp([k,CO,boundingbox([CI,CO]),details.dual<=1e4],-OO);

          rather than solvesdp([k,CI,boundingbox([CI,CO]),details.dual<=1e4],-OO);

And if I follow this code "solvesdp([k,CO,boundingbox([CI,CO]),details.dual<=1e4],-OO)",

the kkt version runs forever too.

[Johan Löfberg]

Yes.

Well, it is simply a very hard problem. Bilevel problems are generically intractable

[Jingle Li]

how about KKT or strong dual? Do you think it's feasible to convert max-min to max-max by duality? Or another way to deal with this problem -- the inner  is LP, the outer is 0-1 integer programming? Intuitively, I think this problem is not too hard to handle，although there are a little bit more of  0 -1 variables。

Thank you very much, professor

[Johan Löfberg]

Already the fact that you have 14^2 binary variables in Xe means it is intractable

an outer lp with inner lp is also intractable, regardless of binary variables