infeasible problem(CPLEX-IBM)

[Qihuang Mei]

I coded the model in Matlab and use yalmip and cplex to solve the problem . It can be solved by the Cplex with deterministic model , when I change it into stochastic model with the same problem, and all the constraints had been linear. but it occurred "Infeasible problem(CPLEX-IBM)", Can someone help me how to solve the problem?  

Thanks in advance.

[Johan Löfberg]

ismember(w,1,2,3) will be expanded to d = binvar(3,1), w == [1 2 3]*d, sum(d)==1. Since w is uncertain, this model will be nonsense (as an uncertainty cannot be part of an equality, there cannot exist a fixed value on d, such that an equality holds for all 1<=w<=3). In short, integer uncertainty models is not supported in this naive form

Your big-M model is absolutely terrible. You big-M constant (the number which should be called as-small-as-possible-but-large-ebough-M) is unnecessarily super huge. M is used in a constraint which turns off delta, and delta is upper bounded by w, which is upper bounded by 3. You use the upper bound 100000!

[Qihuang Mei]

Dear Dr. Löfberg,

Thank you for your patience, I have added 1<=w<=3  and delete ismember(w,[1,2,3]) in the constraints, and set big-M=4, but the problem is still infeasible, and error messages are as below.  the only uncertainty constriant in the model is only one:

N = 8;

C = 3;

R = 8;

W = 19;

M = 4;

Y = binvar(N,C,R,T,'full');

delta = sdpvar(1,1,'full');

w = sdpvar(1,length(s),'full');

constraint = constraint + [uncertain(w),1<=w<=3];

for t = 1:T 

    for c = 1:C

        con6 = 0;

        for r = 1:R

            for i = 1:N

                constraint = constraint + [delta <= w(i)];

                constraint = constraint + [delta <= M * Y(i,c,r,t)];

                constraint = constraint + [M*(1-Y(i,c,r,t)) + delta >= w(i)];

                con6 = con6 + delta;  

            end

        end

        constraint = constraint + [con6<=W];       

    end

end

error message

==============================================

***** Starting YALMIP robustification module. *********************

 - Detected 8 uncertain variables

 - Detected 8 independent group(s) of uncertain variables

 - Eliminating uncertainty using explicit maximization of inf-norm

***** Derivation of robust counterpart done ***********************

Infeasibility row 'c3578':  0  = 1.

Presolve time = 0.00 sec. (0.99 ticks)

Root node processing (before b&c):

  Real time             =    0.00 sec. (1.29 ticks)

Parallel b&c, 4 threads:

  Real time             =    0.00 sec. (0.00 ticks)

  Sync time (average)   =    0.00 sec.

  Wait time (average)   =    0.00 sec.

                          ------------

Total (root+branch&cut) =    0.00 sec. (1.29 ticks)

sol = 

    yalmiptime: 0.5061

    solvertime: 0.0079

          info: 'Infeasible problem (CPLEX-IBM)'

       problem: 1

==============================================

I do not know how to find the error in the model, does this model can be solved by yalmip? 

Thanks a lot.

Qihuang Mei

[Johan Löfberg]

Undefined function or variable 'T'.
 

[Qihuang Mei]

I'm sorry , T = 4 in this model 

[Johan Löfberg]

the code still doesn't run. Supply the complete code (s is not defined)

[Qihuang Mei]

I'm sorry, this is the complete code. the run time is about 90 seconds.

[Johan Löfberg]

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

I can already now say that infeasibility occurs after you add % constraint 8, so you don't have to debug your complete model

Your coment does match the code. Comment says at most 1, code says exactly 1

But the actual bug might be anywhere before that

[Johan Löfberg]

...assuming there is a bug, and that your not simply trying to solve a problem which really is infeasible

[Qihuang Mei]

Dear Dr. Löfberg,

I'm really really thank you for your help, the constraint 8 meants exactly 1, but I didn't write the correct comments.  

I'm really sorry and I'll try to debug the model, maybe the infeasible occurs in other constraints, because when I solve the deterministic model with the same problem, it can go well with no error.

Thanks again.

Qihuang Mei

[Johan Löfberg]

As far as I can tell, the uncertainty only enters

  for i = 1:N

                constraint = constraint + [delta <= w(i)];

                constraint = constraint + [delta <= M * Y(i,c,r,t)];

                constraint = constraint + [M*(1-Y(i,c,r,t)) + delta >= w(i)];

                con6 = con6 + delta;  

%                 con6 = con6 + w(i)*Y(i,c,r,t);

            end

and this is trivial to derive the robst version, which is

  for i = 1:N

                constraint = constraint + [delta <= 1];

                constraint = constraint + [delta <= M * Y(i,c,r,t)];

                constraint = constraint + [M*(1-Y(i,c,r,t)) + delta >= 3];

                con6 = con6 + delta;  

%                 con6 = con6 + w(i)*Y(i,c,r,t);

            end

and you immediately have that delta has to be <=1 (first constraint), thus Y has to be 0 (third constraint) which means delta has to be zero (second constraint). This is probably not your intended model

[Qihuang Mei]

Dear  Dr. Löfberg

Thanks for your reply. 

N = 4;

C = 3;

R = 8;

T = 8;

delta = sdpvar(1,1,'full');

Y = binvar(N,C,R,T,'full');

w = sdpvar(1,N,'full');

constraint = constraint + [uncertain(w),1<=w<=3];

  for i = 1:N

                constraint = constraint + [delta <= w(i)];      

                constraint = constraint + [delta <= M * Y(i,c,r,t)];    

                constraint = constraint + [M*(1-Y(i,c,r,t)) + delta >= w(i)];

                con6 = con6 + delta;  

%                 con6 = con6 + w(i)*Y(i,c,r,t);

            end

Since w is a uncertain variable and Y(i,c,r,t) is a binvar,  the  "con6 = con6 + w(i)*Y(i,c,r,t);" is nonlinear, so I use the other three constraints instead of "con6 = con6 + w(i)*Y(i,c,r,t);" to make the constraint linear . in the constraint I use delta = w(i)*Y(i,c,r,t),  so the value of delta is either 0 or w(i),  according the three constraints(delta <= w(i) , delta <= M*Y(i,c,r,t), M*(1-Y(i,c,r,t))+ delta >= w(i) ), if Y(i,c,r,t) = 1, then the value of delta must be w(i), if Y(i,c,r,t)=0, then delta = 0.

so the modified model is not suitable for my problem.

Thanks again.

[Johan Löfberg]

I don't know what you are trying to say. 

This 

constraint = constraint + [uncertain(w),1<=w<=3];
  for i = 1:N
                constraint = constraint + [delta <= w(i)];      
                constraint = constraint + [delta <= M * Y(i,c,r,t)];    
                constraint = constraint + [M*(1-Y(i,c,r,t)) + delta >= w(i)];
                con6 = con6 + delta;  

            end

is, no matter what you think or want, converted to the corresponding robustified version (as those values of w correspond to the worst-case in the linear inequalities, trivially derived)

  for i = 1:N

                constraint = constraint + [delta <= 1];      

                constraint = constraint + [delta <= M * Y(i,c,r,t)];    

                constraint = constraint + [M*(1-Y(i,c,r,t)) + delta >= 3];

                con6 = con6 + delta;  

            end

In this model, which is the model YALMIP will derive, it is evident that the first constraint implies that delta <=1, which means Y(i,c,r,t) must be equal to 0 for the last inequality to be feasible, which ultimately means delta=1 for the second inequality to be feasible.

This is not a "modified model". This is exactly the model you've encoded using the robust optimization framework

[Johan Löfberg]

and you can use w*Y in the model. In many cases, the derivation of the robust counter-part is not significantly complicated by bilinear terms of decision variables and uncertainty

Min_X max_W x1*w1 + x2*w2 where w1 and w2 are in an interval W = {w : L <= w <= U} is written as min t s.t. x1*w1 + x2*w2 <= t for all w in W, and the robust counterpart is simply min t s.t. x1*U + x2*U <= t