D = binvar(N,N,'full') keeps returning a symmetric matrix

[Andreas Feys]

Hi,

In our code we defined our matrix D as a Binvar(N,N,'full') which should not return a symmetric matrix. But in some way the code does not see the "full".

Our coude is processed with Matlab, Yalmip and Cplex. The dataset is added in appendix. 

%% pre-processing

 clc; clear all; close all;

 addpath('C:\Program Files\IBM\ILOG\CPLEX_Studio1271\cplex\matlab\x64_win64');

 addpath('C:\Program Files\YALMIP-master');

 addpath('C:\Program Files\YALMIP-master\extras');

 addpath('C:\Program Files\YALMIP-master\solvers');

 addpath('C:\Program Files\YALMIP-master\modules');

 addpath('C:\Program Files\YALMIP-master\modules\parametric');

 addpath('C:\Program Files\YALMIP-master\modules\moment');

 addpath('C:\Program Files\YALMIP-master\modules\global');

 addpath('C:\Program Files\YALMIP-master\modules\sos');

 addpath('C:\Program Files\YALMIP-master\operators');

% load data

dataset = xlsread('DataSet1','Tasks');

sheet1 = xlsread('DataSet1', 'Machines');

numberofmachines = sheet1(1,1);

s = sheet1(2,1);

p = [0;dataset(:,2)];

I = length(dataset);

N = I+1;

% constants

M = 10^6;

eps = 10^-6;

% variables

V = binvar(N,1);

W = binvar(N,1);

Z = intvar(N,1);

Y = binvar(N,N,'full');  %12

D = binvar(N,N,'full');  %13

C = sdpvar(N,1); 

H = sdpvar(1,1); 

O = false(N,numberofmachines); %oij all zeroes

O(1,1) = 1;

for i = 2:N % set oij=1 if task i on machine j

    for j = 1:numberofmachines

        if dataset(i-1,3) == j

            O(i,j) = 1;

        else 

            O(i,j) = 0;

        end

       

    end

end

sj = s.*ones(1,numberofmachines);

for j=1:numberofmachines

    ej(1,j) = sj(1,j)+sum(O(:,j).*p);

end

e = min(ej);

Constraint = [Z >= 0, C >= 0, diag(Y)==0]; %14 & 15 & 2a

s = max(sj);

for i = 1:N

    for k = 1:N

        if i~=k

            Constraint = [Constraint,Y(i,k) + Y(k,i) == 1]; %2

        end

    end

    

    Constraint = [Constraint, Z(1) == 1]; %extra

    Constraint = [Constraint, Z(i) == 1 + sum(Y(:,i))]; %4

    

    for k = 1:N

        if i~=k

            Constraint = [Constraint, Z(i) <= Z(k)-1+M*Y(k,i)];  %5

        end

    end

    

    build = p(i);  %6

    for j = 1:numberofmachines

        build = build + O(i,j)*sj(:,j) + sum(O(i,j).*O(:,j).*p(:).*Y(:,i));  %6

    end

    Constraint = [Constraint, C(i) == build];  %6

    

    for k = 1:N

        if i~= k

            Constraint = [Constraint, C(i) - M*(1-Y(i,k)) <= C(k)];  %7

            Constraint = [Constraint, Z(k)-Z(i) >= 1.1 - M * D(i,k)];  %8

        end

    end

    

    Constraint = [Constraint, C(i) <= s - eps + M*W(i)];  %9

    Constraint = [Constraint, C(i) >= e + eps - M*V(i)];  %10

    

    for k = 1:N

        if i~=k

            Constraint = [Constraint, H >= C(k) - C(i) -M*(1-D(i,k))-M*(1-W(i))-M*(1-V(i))];  %11

        end

    end

    

   

end

 

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

% ops = sdpsettings('verbose',1,'cplex');

% Define constraints and objective

Objective = H;

 sol = optimize(Constraint,Objective,ops);

% Analyze error flags

if sol.problem == 0

 % Extract and display value

 solution1 = value(Z)

 solution2 = value(H)

else

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

 sol.info

 yalmiperror(sol.problem)

end

Thanks for helping!

[Johan Löfberg]

Defining the matrix as full does not mean that the solution is 'not symmetric', it only means that the solution is structurally forced (by symmetric parameterization) to be symmetric. The (or a) optimal solution here is symmetric (and all ones, so my guess is your model is wrong)

BTW, using big-M constants in the order of 10^6 is a recipe for numerical disaster, and appears to be a horribly poor estimate in your case. Y is a binary matrix, hence every row and column can at most be summed up to N, hence Z can never become larger than N+1, hence a small but sufficiently large big-M constant in %5 should be something like N

Read the blue Note here which almost appears to have been written for this case :-)

https://yalmip.github.io/tutorial/bigmandconvexhulls/

[Johan Löfberg]

"... is *not* structurally forced (by symmetric parameterization) to be symmetric" of course