Mosek, Gurobi or CVX bug?


(Behrooz) #1

Try this code. load variables from this mat file https://uploadfiles.io/38e79 . Mosek and Gurobi report optimal value is 118229(I think it’s correct). Now uncomment %x==[0,0,0,1;1,0,0,0;0,0,1,0]; Gurobi fails and Mosek reports 110757 as optimal value!. I think it’s an infeasible point!

cvx_clear;
for sample=1:nrofsamp
for u=1:v_nodes
for v=1:v_nodes
for i=1:s_nodes
for j=1:s_nodes
li_cost(sample,u,v,i,j)=s_link_cost(u,v,i,j);

            end
        end
    end
end   

end
%%
[row_s,col_s]=find((s_net_topology)~=0);
[row_v,col_v]=find((v_net_topology)~=0);

Timestart=tic;
cvx_begin

variable x(v_nodes,s_nodes) integer nonnegative;%nodes
%variable y(v_nodes,v_nodes,s_nodes,s_nodes) nonnegative;%links
variable y(nrofsamp,v_nodes,v_nodes,s_nodes,s_nodes) nonnegative;%links

minimize sum(sum(s_processing_cost.*x))+(1/nrofsamp)*sum(sum(sum(sum(sum(li_cost.*y)))));
subject to

for i=1:v_nodes
sum(x(i,:))==1;
end

for i=1:s_nodes
sum(x(:,i))<=1;
end

for i=1:s_nodes
for j=1:v_nodes
x(j,i)*v_processing_capacity(j)<=s_processing_capacity(i);
end
end

for sample=1:nrofsamp
for i=1:s_nodes
for j=1:sum(nonzeros(v_net_topology))%# of virtual links
[ph1]=find(s_net_topology(i,:)~=0);
[ph2]=find(s_net_topology(:,i)~=0);
ind1=zeros;
ind2=zeros;
if(~isempty(ph1)&&~isempty(ph2))
for t=1:length(ph1)
ind1(t)=sub2ind(size(y),sample,row_v(j),col_v(j),i,ph1(t));
end
for t=1:length(ph2)
ind2(t)=sub2ind(size(y),sample,row_v(j),col_v(j),ph2(t),i);
end

        %sum(y(ind1(:)))-sum(y(ind2(:)))== v_link_capacity(row_v(j),col_v(j))*(x(row_v(j),i)-x(col_v(j),i));
        sum(y(ind1(:)))-sum(y(ind2(:)))==v_link_capacity{sample}(row_v(j),col_v(j))*(x(row_v(j),i)-x(col_v(j),i));
    end
    if (isempty(ph1)&&~isempty(ph2))
         for t=1:length(ph2)
                ind2(t)=sub2ind(size(y),sample,row_v(j),col_v(j),ph2(t),i);
         end
         
         -sum(y(ind2(:)))- v_link_capacity{sample}(row_v(j),col_v(j))*(x(row_v(j),i)-x(col_v(j),i))==0;
    end
    if (isempty(ph2)&&~isempty(ph1))
        for t=1:length(ph1)
            ind1(t)=sub2ind(size(y),sample,row_v(j),col_v(j),i,ph1(t));
        end
        
        sum(y(ind1(:)))- v_link_capacity{sample}(row_v(j),col_v(j))*(x(row_v(j),i)-x(col_v(j),i))==0;
    end
    
end

end
end

for sample=1:nrofsamp
for i=1:sum(nonzeros(s_net_topology))

   arrind=null(1,4);
   for j=1:sum(nonzeros(v_net_topology))
       a=[row_v(j),col_v(j),row_s(i),col_s(i)];
       arrind=vertcat(arrind,a);
   end
   [s z]=size(arrind);
   if(~isempty(arrind))
   indices(1)=sub2ind(size(y),sample,arrind(1),arrind(2),arrind(3),arrind(4));
   for row=2:s
   indices(row)=sub2ind(size(y),sample,arrind(row-1,1),arrind(row-1,2),arrind(row-1,3),arrind(row-1,4));
   end
   end
   sum(y(indices(:)))<=s_link_capacity(row_s(i),col_s(i));

end
end
%x==[0,0,0,1;1,0,0,0;0,0,1,0];
t1=toc(Timestart);
cvx_end


Equality constraint does not hold
(Behrooz) #2

I can’t edit my post. It returns a 403 forbidden message!. so I upload it here


(Behrooz) #3

It’s Infeasible:
x(3,3)v_processing_capacity(3)<=s_processing_capacity(3)
1
6<=5!
but Mosek ignore constraints.
for i=1:s_nodes
for j=1:v_nodes
x(j,i)*v_processing_capacity(j)<=s_processing_capacity(i);
end
end


(Behrooz) #4

Dear friends,
I have a weird problem. I have a simple flow conservation constraint in the VNE problem:

I wrote the code in CVX, and for some cases it must be infeasible. But CVX solved it!
As you can see in the below code, lines 32-40 for i=3 and j=2, the right-hand
side of the equality constraint is equal to 8 but the left-hand side is equal
to 0!. So, CVX must report it’s infeasible.

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

clear all;
cvx_clear;
%cvx_solver mosek;

s_nodes=4;
v_nodes=3;

s_net_topology=[0,0,1,1;1,0,1,0;0,0,0,0;1,0,0,0];
s_link_capacity=[0,0,79,73;92,0,48,0;0,0,0,0;47,0,0,0];
[row_s,col_s]=find((s_net_topology)~=0);

v_net_topology=[0,0,1;1,0,0;0,0,0];
v_link_capacity=[0,0,8;2,0,0;0,0,0];
[row_v,col_v]=find((v_net_topology)~=0);
%%% 
x=zeros(v_nodes,s_nodes);
x(3,1)=1;
x(2,2)=1;
x(1,3)=1;

%%
cvx_begin
    
   variable y(v_nodes,v_nodes,s_nodes,s_nodes) nonnegative;

    
   minimize 1000*sum(sum(sum(sum(y(:,:,:,:)))))+1000*sum(sum(x(:,:)));
   
   subject to
    
   for i=1:s_nodes
    for j=1:sum(nonzeros(v_net_topology))%# of virtual links
        [ph1]=find(s_net_topology(i,:)~=0);
        [ph2]=find(s_net_topology(:,i)~=0);
        %test with j=2 i=3 : row_v=2 col_v=1 => 0==8 !!!!
        sum(y(row_v(j),col_v(j),i,ph1(:)))-sum(y(row_v(j),col_v(j),ph2(:),i)) == v_link_capacity(row_v(j),col_v(j))*(x(row_v(j),i)-x(col_v(j),i));

    end
   end
   
  
   for i=1:sum(nonzeros(s_net_topology))
      
       arrind=null(1,4);
       for j=1:sum(nonzeros(v_net_topology))
           a=[row_v(j),col_v(j),row_s(i),col_s(i)];
           arrind=vertcat(arrind,a);
       end
       sum(y(arrind(:)))<=s_link_capacity(row_s(i),col_s(i));

       
   end
   
cvx_end

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


(Mark L. Stone) #5

I replicated the 0 == 8 using both SDPT3 and SeDuMi (SDPT3 actually had -1.910446384641988e-10 == 8)… I got cvx_optval = +11000.

Perhaps it’s a CVX bug?


(Behrooz) #6

I replicated the 0 == 8 using both SDPT3 and SeDuMi (SDPT3 actually had -1.910446384641988e-10 == 8)… I got cvx_optval = +11000.

Perhaps it’s a CVX bug?

Mosek and Gurobi reports a similar result.
just try this line
sum(y(row_v(j),col_v(j),i,ph1(:)))-sum(y(row_v(j),col_v(j),ph2(:),i)) == v_link_capacity(row_v(j),col_v(j))*(x(row_v(j),i)-x(col_v(j),i));
for i=3 and j=2.


(Mark L. Stone) #7

I think we’ll have to wait for @mcg to look at this.


(Michael C. Grant) #8

Indeed, given that all solvers are producing nearly identical but wrong results, it seems clear that somehow CVX is failing to incorporate the equality constraint.

I’ll see what I can find, but I’m afraid I can’t promise a quick turnaround here.


(Behrooz) #9

Dear Michael
Is there any progress on this issue?


(Michael C. Grant) #10

No, and I am not sure when there will be any, I’m afraid. My paid work has to take priority, and there is currently a lot of it!


(Erling D.Andersen) #11

You may be able to reimplement your model in MOSEK Fusion v8 quickly. It is not the ideal solution but may be better than the alternative.


(Behrooz) #12

I found that the problem is because of matrix dimensions. Matlab cannot check those dimensions correctly!. CVX works well.


(Mark L. Stone) #13

Can you please explain more clearly and in detail what you determined?


(Behrooz) #14

I replaced this line

with:

ind1=zeros;
ind2=zeros;
if(~isempty(ph1)&&~isempty(ph2))
    for t=1:length(ph1)
        ind1(t)=sub2ind(size(y),row_v(j),col_v(j),i,ph1(t));
    end
    for t=1:length(ph2)
        ind2(t)=sub2ind(size(y),row_v(j),col_v(j),ph2(t),i);
    end
    sum(y(ind1(:)))-sum(y(ind2(:)))== v_link_capacity(row_v(j),col_v(j))*(x(row_v(j),i)-x(col_v(j),i));
end
if (isempty(ph1)&&~isempty(ph2))
     for t=1:length(ph2)
            ind2(t)=sub2ind(size(y),row_v(j),col_v(j),ph2(t),i);
     end
    -sum(y(ind2(:)))- v_link_capacity(row_v(j),col_v(j))*(x(row_v(j),i)-x(col_v(j),i))==0;
end
if (isempty(ph2)&&~isempty(ph1))
    for t=1:length(ph1)
        ind1(t)=sub2ind(size(y),row_v(j),col_v(j),i,ph1(t));
    end
    sum(y(ind1(:)))- v_link_capacity(row_v(j),col_v(j))*(x(row_v(j),i)-x(col_v(j),i))==0;
end

(Behrooz) #15

I think I found a bug in Mosek. It doesn’t check constraints when you set a variable to some value(e.g. x==2). Gurobi does.


(Erling D.Andersen) #16

A bug in MOSEK? Could you show the MOSEK log output, then I can easily determine if MOSEK is buggy.


(Behrooz) #17

Dear @Erling
Please check this:


(Erling D.Andersen) #18

To me it seems that it is a Matlab M file. Before running that I would like to see the log output. Please email that support@mosek.com


(Erling D.Andersen) #19

Here is the solution summary

Problem status : PRIMAL_FEASIBLE
Solution status : INTEGER_OPTIMAL
Primal. obj: 1.1075748000e+005 Viol. con: 0e+000 var: 1e+000 itg: 0e+000

which got from @behrooz

It says optimal while having large violations i.e.

var: 1e+000

Therefore, the employed version is most likely buggy. The first step is to upgrade to the newest version of MOSEK. If the newest versions still have the issue then contact MOSEK support. Please include the task file as discussed at

https://mosek.com/support/faq#how-do-i-dump-a-mosek-task-file-in-cvx