Dimension error with genetic algorithm optimization variable

Hello, I am trying to solve a nonlinear constrained integer problem from a paper from Daniels & Carillo (1997) on beta-robust scheduling. I failed to use a BNB method as I couldn't get it to work for a matrix input.

C = jobmeans(:,1);   % 10x1 vector
v = jobvars(:,1);    % 10x1 vector
Aeq = [ones(length(C),length(C))];   %10x10 matrix
beq = [ones(1,length(C))];           %1x10 vector
lb = zeros(length(C),length(C));     %10x10 matrix
ub = ones(length(C),length(C));      %10x10 matrix
T = 220;
fun = @(x)(-(T-C'*((n(1)+1-[1:n(1)])*x')')/sqrt(v'*((n(1)+1-[1:n(1)]).^2*x')')); 
intcon = 100;
x = ga(fun,100,[],[],Aeq,beq,lb,ub,[],intcon);

I want to optimize for a n(1) x n(1) = 10x10 integer matrix. If I define the amount of optimization variables (nvars) to be 100, Matlab states that the number of columns in Aeq (10) is not the same as the length of x0. If I set nvars = 10 without intcon = 10 I only get 1x10 non-integer vector x, and with intcon = 10 I do not get a solution. The output of the 'fun' function for a test matrix of x = rand(10,10) is a scalar result so I'm not sure what the issue could be here.

How can I get the solver to solve for a 10x10 integer matrix?

The Matlab error is

Error using preProcessLinearConstr (line 71)
The number of columns in Aeq must be the same as the length of X0.

Error in gacommon (line 97)
[Iterate.x,Aineq,bineq,Aeq,beq,lb,ub,msg,exitFlag] = preProcessLinearConstr( ...

Error in ga (line 363)
    NonconFcn,options,Iterate,type] = gacommon(nvars,fun,Aineq,bineq,Aeq,beq,lb,ub, ...

Error in BRSP (line 78)
x = ga(fun,100,[],[],Aeq,beq,lb,ub,[],100);

Answer 1

[Alan Weiss]

In general, if you have an n-by-n matrix of variables x, the linear inequality constraint A*x <= b (and linear equality constraint Aeq*x = beq) operates on x as the column vector x(:). In other words, the number of columns of A or Aeq must be equal to the number of elements in x. Your Aeq matrix needs to have 100 columns.

Also, if you want all 100 variables to be integer-valued, you need to specify

intcon = 1:100; % Not 100

Also, the ga solver expects your variables to be a row vector, not a matrix. This affects your objective function. You might need to reshape x to a matrix before calculating the objective function.

Alan Weiss

MATLAB mathematical toolbox documentation

[Quinten Rademakers]

Thank you for the explanation, Alan. I have rewritten the code to work for x(:). It now looks like this

C = jobmeans(:,1);   % cost matrix
v = jobvars(:,1);

Aeq7 = kron(eye(n(1)),ones(1,n(1)));         % constraint Equation 7
beq7 = [ones(length(C),1)];                  % constraint Equation 7

Aeq6 = zeros(length(C),length(C)*length(C));
for i = 1:length(C)
    for j = 1:length(C)
Aeq6(i,10*(j-1)+1+i-1) = 1;                 % constraint Equation 6
    end
end
beq6 = [ones(length(C),1)];                 % constraint Equation 6

Aeq = [Aeq7;Aeq6];
beq = [beq7;beq6];

A = [Aeq;-Aeq];         % Rewriting Ax=b as Ax<=b, -Ax,<=-b
b = [beq;-beq];        % since ga solver does not accept eq constraints
% Constraint matrices  Equation 6,7 BRSP paper
 
lb = zeros(length(C)*length(C),1);
ub = ones(length(C)*length(C),1);

T = 220;

% fun =
% @(x)(-(T-C'*((n(1)+1-[1:n(1)])*x')')/sqrt(v'*((n(1)+1-[1:n(1)]).^2*x')'));
% % X matrix input (not accepted by solvers)

test = rand(10,10);     % test matrix (x=test(:)) input for objective function

vec = kron(eye(n(1)),[1:n(1)]);         % k constant matrix in objective function
nplus1 = kron((n(1)+1)*eye(n(1)),ones(1,length(C))); % n+1 constant matrix in objective function
% (nplus1-vec)*jobmeans_i*x_ik =  phibar      Equation 3 BRSP paper
% (nplus1-vec)^.2*jobvars_i*x_ik =  var(phi)  Equation 4 BRSP paper

testfun = (-(T-C'*((nplus1-vec)*test(:))))/sqrt(v'*((nplus1-vec).^2*test(:)));

fun = @(x)(-(T-C'*((nplus1-vec)*x)))/sqrt(v'*((nplus1-vec).^2*x));     % X(:) vector input
% maximization function   Equation 5 BRSP paper


x0 = zeros(length(C)*length(C),1);
for i = 1:n(1)
x0(i+(i-1)*length(C),1) = 1;                % Initial job sequence {J1,J2,J3..,J10}
end

% Genetic algorithm approach
intcon = 1:100;
x = ga(fun,100,A,b,[],[],lb,ub,[],intcon);    % Equality constraint not accepted

Before I expanded the constraint matrices to include Equation 6 from the paper, the solver ran fine but did not find a solution.

Now I get the following error:

Error using  * 
Incorrect dimensions for matrix multiplication. Check that the number of columns in the first matrix matches the
number of rows in the second matrix. To perform elementwise multiplication, use '.*'.

Error in BRSP (line 85)
fun = @(x)(-(T-C'*((nplus1-vec)*x)))/sqrt(v'*((nplus1-vec).^2*x));     % X(:) vector input

Error in createAnonymousFcn>@(x)fcn(x,FcnArgs{:}) (line 11)
fcn_handle = @(x) fcn(x,FcnArgs{:});

Error in fcnvectorizer (line 13)
            y(i,:) = feval(fun,(pop(i,:)));

Error in gaminlppenaltyfcn

Error in gapenalty

Error in stepGA (line 63)
    nextScore = FitnessFcn(pop);

Error in galincon (line 62)
        [score,population,state] = stepGA(score,population,options,state,GenomeLength,FitnessFcn);

Error in gapenalty

Error in gaminlp

Error in ga (line 393)
    [x,fval,exitFlag,output,population,scores] = gaminlp(FitnessFcn,nvars, ...

Error in BRSP (line 96)
x = ga(fun,100,A,b,[],[],lb,ub,[],intcon);    % Equality constraint not accepted

Caused by:
    Failure in user-supplied fitness function evaluation. GA cannot continue.

I can not make sense of this error as my objective function works fine with the test input test(:), or x0.

[Alan Weiss]

Sorry, I don't know. I suggest that you step through with the debugger and find out what is going wrong that way.

Alan Weiss

MATLAB mathematical toolbox documentation

Answer 2

[Quinten Rademakers]

Will do so. Thanks for the help.