How to recognize which constraint cause the unbounded error prompt (SCIP solver)

[JackJack]

Dear fellow researcher,

Currently I am using the scip solver for my optimization problem. During it execution, a small error prompt appear to remind me that I have not bounded my variable.

Starting spatial branch-and-bound on unbounded variable <t_xvar10> ([243.723,1e+20]) - cannot guarantee finite termination

I am unable to recognize which variable or which constraint that introduce this problem. Is there anyway to get through this ?

My first attempt was to add some tag or comment to the constraint but this was not effective Any help would be appreciated ! Thank you for your enthusiasm !

clc; clear all; %Number of Antena at BS L = 2; count = 1; iter_max = 5; epsilon = 1e-5; w11_init = [0.0000 + 0.0000i;0.0000 + 5.8580i]; w21_init = [0.0000 + 0.0000i ;0.0000 +11.1433i]; alpha_init = 0.0557; tau_init = 40.1979; beta_init = 8.7969e+03; w11 = sdpvar(L,1,'full','complex'); w21 = sdpvar(L,1,'full','complex'); alpha = sdpvar(1,1,'full','real'); tau = sdpvar(1,1,'full','real'); beta = sdpvar(1,1,'full','real'); w = [w11' w21']'; a = []; option = sdpsettings('verbose',1,'solver','scip','cachesolvers',1); option.scip.tolafun = 0.001; option.scip.maxnodes = 600000; option.scip.maxtime = 100; while (count<=iter_max) %run for 5 iteration obj = -((2/beta_init) - beta/(beta_init^2)) ; gamma11lhs = 0.5*(1-alpha_init)/(tau_init+epsilon)*tau^2 + ... 0.5*tau_init/(1-alpha_init +epsilon)*(1-alpha)^2 + NoisePowerLinearBW ; gamma11rhs = (2*real((h11'*w11_init)'*(h11'*w11)) - norm(h11'*w11_init)^2)*beta; %first term- lhs - gamma21 first_lhs = norm(h21'*w11)^2 + NoisePowerLinearBW; %first term- rhs - gamma21 first_rhs = (2*real((h21'*w21_init)'*(h21'*w21)) - norm(h21'*w21_init)^2)*beta ; %second term - lhs - gamma21 second_lhs = norm(h11'*w11)^2 + NoisePowerLinearBW; second_rhs = ((2*real((h11'*w21_init)'*(h11'*w21))/(alpha_init+epsilon)) - (alpha*(norm(h11'*w21_init)^2)/(epsilon + alpha_init^2)))*beta; cons = [((norm(w)^2) <= PbsMaxLinear) :'power' ... (gamma11lhs*10000 <= gamma11rhs*10000): 'gamma11' ... (first_lhs <= first_rhs): 'first term gamma21' ... (second_lhs <= second_rhs): 'second term gamma21' ... (0 <= alpha <= 1) : 'alpha' ... (0 <= tau ) : 'tau' ... (0 <= beta): 'beta' ]; sol = optimize(cons,obj,option); mydata_new = {value(w11),value(w21),value(alpha),value(tau),value(beta)}; [w11_init, w21_init, alpha_init, tau_init,beta_init] = mydata_new{:} if (count >= 3 && abs(abs(a(end)) - abs(a(end-1))) < 0.0001) break else count = count + 1; end end

[Johan Löfberg]

your code does not run

[Johan Löfberg]

Undefined function or variable 'NoisePowerLinearBW'.

Error in Untitled5 (line 28)

        0.5*tau_init/(1-alpha_init +epsilon)*(1-alpha)^2  +

        NoisePowerLinearBW          ;

 

[JackJack]

Sorry for the missing data, I have check my code again this time it will run

clc;
clear all;
%Number of Antena at BS
L = 2;

h11 = [0.000016219438297 - 0.034701576275583i; -0.000988689560017 + 0.008111541693473i];
 h21 = [-0.0071-0.0029i; 0.0002 + 0.0013i];
%Noise Power calculation
NoisePower_dbm = -90; %dBm
BandWidth = 20*10^6; % Hertz
NoisePowerLinear = 10^(NoisePower_dbm/10) ; %  Unit mili watt / Hertz
%Noise power in the 20 Mega Hertz Bandwidth
NoisePowerLinearBW = NoisePowerLinear*BandWidth; %  Unit mili watts
%Transmit Power
PbsMax_dbm = 22; %dbM
PbsMaxLinear = 10.^(PbsMax_dbm/10);
w11_init = [4.8696 + 4.5377i ; 2.9779 + 2.3829i];
w21_init = [4.4181 + 4.3582i ; 4.5687 + 5.4850i];
alpha_init = 0.3153 ;
tau_init = 2.3641 ;
beta_init = 53.3668 ;
count = 1;
iter_max = 2;
epsilon = 1e-5;

w11 = sdpvar(L,1,'full','complex');
w21 = sdpvar(L,1,'full','complex');
alpha = sdpvar(1,1,'full','real');
tau = sdpvar(1,1,'full','real');
beta = sdpvar(1,1,'full','real');
w = [w11' w21']';

option  = sdpsettings('verbose',1,'solver','scip','cachesolvers',1);
option.scip.tolafun = 0.001;
option.scip.maxnodes = 600000;
option.scip.maxtime = 100;
while (count<=iter_max)

    obj = -((2/beta_init) - beta/(beta_init^2))   ;
    gamma11lhs = 0.5*(1-alpha_init)/(tau_init+epsilon)*tau^2 + ...
        0.5*tau_init/(1-alpha_init +epsilon)*(1-alpha)^2  +   NoisePowerLinearBW          ;
    gamma11rhs  =    (2*real((h11'*w11_init)'*(h11'*w11))   - norm(h11'*w11_init)^2)*beta;
    %first term- lhs - gamma21
    first_lhs = norm(h21'*w11)^2 + NoisePowerLinearBW;
    %first term- rhs - gamma21
    first_rhs = (2*real((h21'*w21_init)'*(h21'*w21)) - norm(h21'*w21_init)^2)*beta                 ;
    %second term - lhs - gamma21
    second_lhs = norm(h11'*w11)^2 + NoisePowerLinearBW;
    second_rhs = ((2*real((h11'*w21_init)'*(h11'*w21))/(alpha_init+epsilon)) - (alpha*(norm(h11'*w21_init)^2)/(epsilon + alpha_init^2)))*beta;

    cons = [((norm(w)^2) <= PbsMaxLinear) :'power' ...

        (gamma11lhs<= gamma11rhs): 'gamma11' ...

        (first_lhs <=    first_rhs): 'first term gamma21' ...
        (second_lhs <=  second_rhs): 'second term gamma21' ...
        (0 <= alpha <= 1) : 'alpha' ...
        (0 <= tau ) : 'tau' ...
        (0 <= beta): 'beta'   ];
    sol = optimize(cons,obj,option);
    mydata_new = {value(w11),value(w21),value(alpha),value(tau),value(beta)};
    [w11_init, w21_init, alpha_init, tau_init,beta_init] = mydata_new{:}

    if (count >= 3 && abs(abs(a(end)) - abs(a(end-1))) < 0.001)

        break
    else
        count = count + 1;

        a = [a value(obj)];
    end
end

[Johan Löfberg]

I don't get that warning in scip (I get a lot of other exception warnings though about failed solves)

However, it is correct that 2 variables are unbounded from above, as bmibnb warns about this too (note that bmibnb is roughly 10 times faster than scip here, on my machine at least)

K>> sol = optimize(cons,obj,sdpsettings('solver','bmibnb'))

* Starting YALMIP global branch & bound.

* Branch-variables : 11

* Upper solver     : fmincon

* Lower solver     : GUROBI

* LP solver        : GUROBI

* Warning: 2 branch variables are unbounded from above

 Node       Upper      Gap(%)       Lower    Open

    1 :   -3.632E-02     0.07     -3.701E-02   2  Improved solution  

* Finished.  Cost: -0.036319 Gap: 0.066411

* Termination with relative gap satisfied 

* Timing: 70% spent in upper solver (1 problems solved)

*         1% spent in lower solver (23 problems solved)

*         10% spent in LP-based domain reduction (22 problems solved)

sol = 

  struct with fields:

    yalmipversion: '20200116'

       yalmiptime: 0.2240

       solvertime: 0.6750

             info: 'Successfully solved (BMIBNB)'

          problem: 0

looking at your code, it is pretty obvious which variables are unbounded, which also is confirmed by solving with some random bound and noting that the warning goes away

 sol = optimize([cons,tau <= 100,beta <= 100], obj,sdpsettings('solver','bmibnb'))

* Starting YALMIP global branch & bound.

* Branch-variables : 11

* Upper solver     : fmincon

* Lower solver     : GUROBI

* LP solver        : GUROBI

 Node       Upper      Gap(%)       Lower    Open

    1 :   -3.632E-02     0.00     -3.701E-02   0  Improved solution  

* Finished.  Cost: -0.036319 Gap: 0

* Termination with all nodes pruned 

* Timing: 72% spent in upper solver (1 problems solved)

*         1% spent in lower solver (23 problems solved)

*         14% spent in LP-based domain reduction (24 problems solved)

sol = 

  struct with fields:

    yalmipversion: '20200116'

       yalmiptime: 0.1270

       solvertime: 0.6500

             info: 'Successfully solved (BMIBNB)'

          problem: 0

[JackJack]

Oh thank you very much, so it tau and beta. My mind has been quite wandering

[Johan Löfberg]

BTW, your objective looks awfully close to a linearization of 1/beta at the point beta_init. If so, that whole linearization is just a waste of energy and notation. If you want to minimize 1/beta, simply maximize beta, or if you want to maximize 1/beta, simply minimize beta

[JackJack]

"if you want to maximize 1/beta, simply minimize beta" this is exactly what I want thank you !