Can cplex be used as solver for integer programming problem?

[Cyan Zhou]

Hi, 

I wanted to use cplex as solver to solve an integer programming problem, while a warning "Warning: Solver not applicable (cplex)" always showed up. The cplex version in my matlab is 12.8.0, and it can be found when I run "yalmiptest". Can everyone know if cplex is applicable with yalmip for integer programming problem in Matlab?

     

[Johan Löfberg]

Of course.

Most likely you are setting up a nonconvex quadratic constraints or something like that, which isn't supported. In 90% of the cases, it is because users multiply binary and continuous variables to model on-off behavior...

[Cyan Zhou]

Hi, Thank you for your advice. The problem is nonconvex, while the bmibnb seems can get a solution of this problem. The code is shown as follows. Is this problem feasible to be solved using cplex with yalmip?

code here:

n_bs = 2;

n_files = 2;

 

canonical_mat = cell(8,1);

canonical_mat{1} = [1,0;0,1];

canonical_mat{2} = [0,1;1,0];

canonical_mat{3} = [1,1;1,0];

canonical_mat{4} = [1,1;0,1];

canonical_mat{5} = [1,0;1,1];

canonical_mat{6} = [0,1;1,1];

canonical_mat{7} = [1,1;1,1];

canonical_mat{8} = [0,0;0,0];

 

delay_mat = [3,3,2,2,2,2,1,100];

 

x = binvar(n_files,n_bs);

z = binvar(n_files,1);

y = binvar(n_files,n_bs);

 

C0 = [];

for i = 1:n_files

    C0 = [C0, y(i,:) >= 1-z(i), y(i,:) >= x(i,:), implies(z(i),sum(x(i,:))>=1)];

end

obj = 0;

for ptr = 1:length(canonical_mat)

    cur_mat = canonical_mat{ptr};

    prod_ = 1;

    for i = 1:n_files

        for j = 1:n_bs

            prod_ = prod_ * ((cur_mat(i,j)&y(i,j)) | ((1-cur_mat(i,j))&(1-y(i,j))));

        end

    end

    obj = obj + delay_mat(ptr) * prod_;

end

 

 

ops = sdpsettings('solver','cplex');

sol = optimize(C0,obj,ops);

 

if sol.problem == 0

    fprintf('\n value of x: \n');

    disp(value(x));

    fprintf('\n value of z: \n');

    disp(value(z));

    fprintf('\n value of y: \n');

    disp(value(y));

end

[Johan Löfberg]

You are completely destroying that model by creating a huge polynomial binary expression

 prod_ * ((cur_mat(i,j)&y(i,j)) | ((1-cur_mat(i,j))&(1-y(i,j))))

however, you start of with a logical representation, so why don't you do that all the way?

 prod_ = prod_ &  ((cur_mat(i,j)&y(i,j)) | ((1-cur_mat(i,j))&(1-y(i,j))));

note that x and y currently are symmetric, you maybe want binvar(n_files,n_bs,'full')

however, it feels like you are hiding some simply condition in that logical thingy you are creating. As far as I can tell, ((cur_mat(i,j)&y(i,j)) | ((1-cur_mat(i,j))&(1-y(i,j)))) simplifies to y(i,j) | 0 when curmat is 1 and simplifies to 1-y when curmat is 0, so why not introduce new variable q with constraint q==y + curmat, and then your objective is basically a sum of those q matrices or something like that (weighted with delaymat)

[Cyan Zhou]

Thank you! Cplex is applicable if I change the sentence of "prod_". 

In fact, I want to compare whether matrix y is the same as a certain cur_mat, if so, then, the objective function is the corresponding value of that cur_mat, otherwise 0. So, ((cur_mat(i,j)&y(i,j)) | ((1-cur_mat(i,j))&(1-y(i,j)))) is just to find if cur_mat(i,j) is the same as y(i,j) for every pair of (i,j). If so, prod_=1, otherwise 0. 

[Johan Löfberg]

so you simply want to count how many elements are equal in a decision variable a and a given matrix b?

[Johan Löfberg]

reformulöation: you want to check if a decision variable a and given matrix b are equal

[Cyan Zhou]

Yes, there are a set of standard matrices and a variable matrix a. The thing is to decide whether the matrix a is equal to one standard matrix b. If so, the objective is the value of matrix b. There is always a corresponding equivalent matrix b for a.