infeasible problem (trying to implement MINLP in YALMIP)

[NIRZHAR SAHA]

Hello,

My program is in the following, where I am trying to solve a Nash bargaining problem formulated as a MINLP. I have posted the code as well as YALMIP response in the following. C


clc;

clear all

M=5;

N=2;

WRange = [0.1 0.6; 0.1 1];

WMmin = [0.1 0.5 0.2 0.1 0.5];

Ttau = ones(1,M);

Gammai = 10;

Cq = 1;

x = binvar(N, M);

w = sdpvar(N, M);

Constraints = [sum(x,1) == ones(1, M), sum(w, 1) >= WMmin, sum(w,2) <= WRange(:, 2)];

for m=1:M

    Constraints = [Constraints, sum((x(:,m)*Cq)./(w(:,m)*(1+Gammai))) <= Ttau(m)];

    

end

Objective = sum(log(Ttau - sum((x*Cq)./(w*(1+Gammai)))));

ops = sdpsettings('solver','bnb','bnb.solver','fmincon');

sol = optimize(Constraints,Objective,ops);

% Analyze error flags

if sol.problem == 0

 % Extract and display value

 solution = value(x)

else

 display('Hmm, something went wrong!');

 sol.info

 yalmiperror(sol.problem)

end


and I am getting following message

* Starting YALMIP integer branch & bound.

* Lower solver   : fmincon-standard

* Upper solver   : rounder

* Max iterations : 300

 Node       Upper       Gap(%)      Lower    Open

    1 :          Inf      Inf     -1.915E+01   2  Successfully solved 

    2 :          Inf      Inf     -1.915E+01   1  Infeasible problem 

    3 :          Inf      Inf     -1.915E+01   0  Infeasible problem 

+   3 Finishing.  Cost: Inf

Hmm, something went wrong!

ans =

Infeasible problem (BNB)

ans =

Infeasible problem 

[Johan Löfberg]

First, awfully optimistic to use bnb on this problem. bnb assume the local nodes are solved to global optimality, which will fail here, with nasty singularities, bilinearities etc

However, it looks like you really have simply stuff like x1/w1 + x2/w2 + ... <= constant, where x is binary.

Introduce ti to upper bound xi/wi, xi/wi <= ti, and then t1+ t2+...<= constant

xi/wi<= ti is equivalent to xi^2/wi <= ti (since xi^2 = xi for  binary). 

xi^2/wi <= ti is SOCP representable

The objective is perhaps trickier, but you should work further along these lines. 

[NIRZHAR SAHA]

Dear Johan,

Thank you for your reply.  I have attached my optimisation problem for you. Where X a is binary decision variable and W in an allocation variable (bandwidth), remaining parameters are constant. 

Could you please give some advice how I can simplify xi/wi terms.

Do you mean that I should simplify the objective function and constraint function which include xi/wi tems.

Also I have tried to transform the problem into a GP but the objective function doesn't allow that transformation.

also should I consider xi/wi tems as bilinear terms, and if so, then how can I relax bilinear terms like xi/wi. I know about McCormick relaxation which is applicable in case of (XY) where both are binary decision variables.

THank you and eagerly looking forward to your reply.

Kind regards,

Nirzhar Saha  

[Johan Löfberg]

Since w_mi only enters as 1/w_mi, why even parameterize the problem in that variable? Introduce a new varible Y which is the elementwise inverse of W, and express the whole problem in terms of that variable. That way you get rid of the divisions.

You still have nonconvexity due to log, and products of x and y. However, that product can be linearized as it simply is a logical statement, x*y is zero if x=0 and it is equal to y if x = 1. That is easily modelled using implies (or being lazy with binmodel)

With that, you will end up with a model which is predominantly linear, except for the log in the objective. In contrast to you code which minimizes the log, the picture says maximize, hence the problem will be convex, and bnb should then work (in theory)

[NIRZHAR SAHA]

Dear Johan,

Thank you very much. It helps a lot.

I still have one more question. After the transformation of original problem by introducing a elementwise operator y, how do I mathematically solve the problem. More specifically can I apply 

(1) constraint relaxation to compute a closed form expression and 

(2) Lagrange relaxation to compute a iterative solution.  

Thank you again and eagerly looking forward to your reply.

[Johan Löfberg]

If you do the variable change and then model the binary products as I said, the problem will be a convex mixed-integer exponential cone program, that YALMIP should be able to solve easily using bnb