Binary variable contains a non-binary value


(Tajiki) #1

I have a piece of code in which there is a binary matrix (A) as CVX variable. In some cases, program returns a non-binary value in binary matrix.
How is it possible?

> function BLP_Function_940825(n, p, Relax_Enable)
>     D = ones(n,n);
>     JT = ones(n,n);
>     C = 3*ones(p,3);
>     miu = 1;
>     Topology_Generator;
>     [flowStart, flowEnd,C(:,3)] = ReadFlows(p,n);
>     CT=C(:,3)';
>     PT=2*CT;
>     cvx_begin 
>         cvx_solver MOSEK
>         variable A(n,n,p) binary;
>         subject to
>             for i=1:n
>                 for j=1:n
>                     if ~B(i,j)
>                         for f=1:p
>                             A(i,j,f)==0
>                         end
>                     end
>                 end
>             end
>             for f = 1:p
>                 sum(sum(A(:,:,f).*D))<=C(f,1) %(3)
>                 sum(sum(A(:,:,f).*JT))<=C(f,2) %(5)
>             end
>             temp = permute(A, [1 3 2]);
>             for i = 1:n
>                 for j = 1:n
>                     temp(i,:,j)*C(:,3)<=miu*B(i,j) %(7) 
>                 end
>             end
>             for f = 1:p
>                 sum(A(:, flowStart(f),f)) == 0%8
>                 sum(A(flowEnd(f),:,f)) == 0%9
>                 sum(A(flowStart(f),:,f)) == 1%10
>                 sum(A(:,flowEnd(f),f)) == 1%11
>             end
>             for f = 1:p
>                 for i = 1:n
>                     if i~=flowStart(f) && i~=flowEnd(f)
>                         sum(A(i,:,f)) == sum(A(:,i,f))
>                     end
>                     sum(A(i,:,f))<=1
>                 end
>             end
>             Obj = 0;
>             for i = 1:n
>                 for j = 1:n
>                     tmp=0;
>                     if B(i,j)~=0
>                         for f = 1:p
>                             tmp = tmp+A(i,j,f)*max(PT(f),CT(f));
>                         end
>                         Obj = max(tmp/B(i,j), Obj);
>                     end
>                 end
>             end 
>             minimize(Obj)
>     cvx_end
>     Display_Result
> end

(Mark L. Stone) #2

How far from 0 and 1 are the returned values, for example, within “roundoff”? Are you being informed that the problem has been successfully solved?


(Tajiki) #3

The optimizer say the problem is solved
-6.3109e-30
1.0097e-28
-1.9722e-31
1
1.1102e-16
1.0097e-28
1.7875e-18
1.6964e-11
2.5244e-29
2.2011e-18
I test the program for different input. Below value were repeated in two or more different run:
1
1.7875e-18
1.0097e-28
1.6964e-11
I set a piece of code to find the wrong answer. I don’t know why it return “1” as a wrong answer. below is the written code:

> for i = 1:n
>     for j = 1:n
>         for k = 1:p
>             if A(i,j,k)~=1
>                 if A(i,j,k)~=0
>                     display(['error',' ',num2str(i),' ',num2str(j),' ',num2str(k),' ',num2str(A(i,j,k))]);
>                     if A(i,j,k)<= 0.5
>                         A(i,j,k)=0;
>                     else
>                         A(i,j,k)=1;
>                     end
>                 end
>             end
>         end
>     end
> end

It should be mentioned that in all cases that the answer is something between 0 and 1, the optimizer time is sufficiently greater than normal run. I test the program for 16 different input.
A(22,22,10), A(22,22,30), A(22,22,50),A(22,22,70), A(22,22,90), A(22,22,110), A(22,22,130), A(22,22,150)
A(22,22,200), A(22,22,220), A(22,22,250), A(22,22,300), A(22,22,320), A(22,22,350), A(22,22,400)

It return wrong value for A(22,22,200), A(22,22, 220), A(22,22,300), A(22,22, 32), A(22,22,400)
optimizer time for all of cases are less than 2 second while for A(22,22,200), A(22,22,220), A(22,22,300), A(22,22,320), A(22,22,400) is 12, 15, 27, 35, and 43 respectively

there is an exception, A(22,22,350) values are all correct but the optimizer time is 41 second.


(Mark L. Stone) #4

You are not allowing for any tolerance around 0 and 1. The solver does not necessarily return values which are exactly 0 or 1. I think you just need to need to treat these (round off) as being 0 or 1.


(Michael C. Grant) #5

Mark is right. That’s simple roundoff error there, and is to be expected. Your code must be designed to expect and correct for roundoff error.


(Tajiki) #6

Thaks for the answer,