Integer constrained optimization using the "ga" (genetic algorithm) solver of MATLAB - can anyone help?

I tried to do mono-objective linear optimization subject to linear equality and inequality constraints and over binary decision variables (o or 1) using the "ga" solver of MATLAB. MATLAB optimization "ga" toolbox did not help, because many constraints are violated and not satisfied. However i have transformed the equality constraints to inequality constraints using a tolerance. Does anybody have an explanation or an idea to overcome this problem?

Answer 1

[Matt J]

However i have transformed the equality constraints to inequality constraints using a tolerance.

ga() already applies a tolerance parameter "TolCon" to the constraints.

http://www.mathworks.com/help/gads/gaoptimset.html

You can never expect to satisfy equality constraints exactly.

[Matt J]

imed Nasri Commented

Matt J, did you mean that the ga solver for matlab is not suitable to solve a binary or integer optimization problem when there are equality constraints?

[Matt J]

No, I meant that equality constraints can never be exactly satisfied with any solver. You always have floating point errors and imperfect convergence, so tolerances are also necessary.

However, now that you mention it, I also see here

http://www.mathworks.com/help/gads/ga.html#inputarg_IntCon

that since you are using the IntCon option, equality constraints are not allowed.

[imed NASRI]

Yes i use the IntCon option and i've transformed equality constraints to inequality constraints (for example: x1+x2+2=2 is replaced by x1+x2+2<=2 and -x1-x2-2<=-2) but some of equality and inequality constraints are violated.

[Matt J]

Again, TolCon.

[imed NASRI]

that's mean that matlab don't help to solve an integer constrained optimization problem using genetic algorithme. Because other solvers like LINGO or CEPLEX find the global optimal solution with all constraints (equality and inequality) satisfaction

[Matt J]

Because other solvers like LINGO or CEPLEX find the global optimal solution with all constraints (equality and inequality) satisfaction

No, they don't...

Again, no solver can escape from finite precision arithmetic. Everybody has to apply a tolerance, unless I suppose your Aeq, beq constraint data are all integers.

[imed NASRI]

yes they are all binary constraints

Answer 2

[imed NASRI]

in the case of my optimization problem, both equality and inequality constraints are violated when i run the mixed integer solver ga of matlab. However, the same problem is solved by CEPLEX solver using!!!!!

Answer 3

[Matt J]

I tried to do mono-objective linear optimization subject to linear equality and inequality constraints and over binary decision variables (o or 1) using the "ga" solver of MATLAB. MATLAB optimization "ga" toolbox did not help,

BINTPROG would be the more appropriate solver, if the objective and all constraints are linear.

[imed NASRI]

i've to use genetic algorithm. I know that there are other more appropriate solver. But my supervisors want to use genetic algorithm to solve the problem

[Matt J]

If you must use ga(), you could try reformulating the equality constraints with some slack, e.g. instead of x1+x2=d, you would have

 TolCon=1e-6;
 slack=TolCon*100;

 x1+x2 <=d+slack
 -x1-x2<=-d+slack

This is not the same as what you are doing already.

[imed NASRI]

i've tried this reformulation with slack=1e-3, but the constraints are violated.

[Matt J]

Well, you'll have to convince your supervisors to use BINTPROG...

[imed NASRI]

i've also tried to add an other constraint to force variable x to be equal to 0 or 1. This constraint is x*(x-1)=0. So with this constraint i'm not obliged to use the IntCon options. Unfortunately, the ga solve dont find feasible solutions.

[Matt J]

I don't think you can trick ga() into thinking that it is bintprog()...

Answer 4

[Matt J]

Another thing you could try is to eliminate the equality constraints by solving for some variables in terms of the others. For example, if you had the single equality constraint

 x1+x2+x3=d

then you could eliminate both the constraint and x3 from the problem by replacing x3 everywhere by d-x1-x2. The same kind of thing could be done with systems of inequality constraints.

Then you would be left with inequality constraints only, which ga() can handle.

[imed NASRI]

I think that it can be a good idea to overcome the problem of equality constraints for a small problem. But i deal with a big problem (100.000) constraints and 40.200 variables.

[imed NASRI]

I generates automatically my constraints in a text file (.txt). Is there a matlab code that replaces the variable x3 everywhere in the generated text file by d-x1-x2 instead of replacing it manually which is very difficult to do when the problem is very complex?

[Matt J]

If your equality constraints can be partitioned

 [A1, A2]*[x1;x2]=b

where A2 is a square nonsingular matrix, then x2 can be eliminated and written in terms of x1 by re-arranging and solving:

 x2  = A2\(b-A1*x1)  =  (A2\b) - (A2\A1)*x1

Below is a function that can help make such partitions,

function [Xsub,idx]=licols(X,tol)
%Extract a linearly independent set of columns of a given matrix X
%
%    [Xsub,idx]=licols(X)
%
%in:
%
%  X: The given input matrix
%  tol: A rank estimation tolerance. Default=1e-10
%
%out:
%
% Xsub: The extracted columns of X
% idx:  The indices (into X) of the extracted columns

     if ~nnz(X) %X has no non-zeros and hence no independent columns

         Xsub=[]; idx=[];
         return
     end

     if nargin<2, tol=1e-10; end

       [Q, R, E] = qr(X,0); 

       if ~isvector(R)
        diagr = abs(diag(R));
       else
        diagr = R(1);   
       end

       %Rank estimation
       r = find(diagr >= tol*diagr(1), 1, 'last'); %rank estimation

       idx=sort(E(1:r));

       Xsub=X(:,idx);

[imed NASRI]

Thank u for your answer but I dont use matrices notations. I generate equations instead of matrices. Also, I have some variables that are equals to zero in my problem.

[Matt J]

You mean you're not using the input matrix arguments A,b,Aeq,beq to specify linear constraints? If not, then how/where are you passing them to GA?

[imed NASRI]

Yes, I have passed them as nonlinear constraints [c,ceq] and it works.

[imed NASRI]

i have tried to declare the variables which are equals to zeros (x(k)=0) and eliminated the equality constraints before calling the ga(). But it doesn't work and it doesn't give a good solution

[Matt J]

I think that it can be a good idea to overcome the problem of equality constraints for a small problem. But i deal with a big problem (100.000) constraints and 40.200 variables.

Do you mean 100000 equality constraints? It sounds wrong that you have more equality constraints than variables. This means that either you have redundant equations (which you can therefore get rid of) or the solution to the linear equalities is unique, making the problem trivial.

Yes, I have passed them as nonlinear constraints [c,ceq] and it works.

Would the matrix of coefficients be sparse? If so, it's not a good idea to disguise linear constraints as nonlinear ones. The solvers benefit from knowing which constraints are linear and which are not. I wonder vaguely whether that could explain why slack didn't work earlier.

If the linear equations are sparse, you can convert them to matrices by evaluating the equations at the columns of speye(N);

 N=42000;
 E=speye(N);
 columns=cell(1,N);

 for i=1:4N
   columns{i}=evaulate_equations(E(:,i))
 end

 matrix=cell2mat(columns);

That's what I would advise you to do. Of course, it would be better to abandon symbolic equation manipulation altogether. It doesn't make obvious sense to work this way when everything is linear. Linear equations is what the numerical side of MATLAB does best.

[imed NASRI]

no i mean 100.000 equality and inequality constraints. As i've told u earlier, i have some variables that must be equal to zero to meet the requirements of the problem. Therefore, some decision variables can be calculated easily by using relations between variables. Can u give me please a short example that explain to me how building matrices from equations? Thank u.

[Matt J]

   N=10;
   E=speye(N,N+1);
   columns=cell(1,N);

   beq=-evaluate_equations(E(:,N+1));
   for i=1:N
     columns{i}=evaluate_equations(E(:,i))+ beq;
   end
   Aeq=cell2mat(columns);

   full(Aeq),
   full(beq),

function F=evaluate_equations(x)

   F(1)=2*x(1)+x(2)-10;
   F(2)=x(9)+3*x(10)-7;
   F=F(:); %column vector

[imed NASRI]

What did u mean by "equations are sparse?"

It attaches a file that contains some equations of my problem. Can u show me please how to convert them to matrices?

[Matt J]

What did u mean by "equations are sparse?"

In MATLAB, a matrix which contains mostly zeros can be held in sparse form. This conserves memory and speeds up lots of different kinds of manipulations. E.g.,

>> A=eye(5000); Asparse=sparse(A); whos A Asparse

    Name            Size                  Bytes  Class     Attributes

    A            5000x5000            200000000  double              
    Asparse      5000x5000               120008  double    sparse

See "doc sparse" for more info.

It attaches a file that contains some equations of my problem. Can u show me please how to convert them to matrices?

See the example in my last Comment. There, evaluate_equations() takes the place of whatever you use to evaluate the left hand side of the equalities.

[imed NASRI]

Sorry but the example that u show for building matrices from linear equality and inequality equations is not clear for me. What is N for u?

[Matt J]

N is the number of unknowns.

[imed NASRI]

I have tried to run your example and i recieve the following error message:

Function definitions are not permitted in this context.

[Matt J]

Probably because the mfile you put the code in doesn't have

 function in=f(out)

at the top.

[imed NASRI]

yes it works now. thank u

[imed NASRI]

I have used linear constraints with Aineq and Bineq. Also, I have used slack for equality constraints. the same problem persists. Some constraints are violated. Can u tell me please if my equality constraints can be partitioned or no? if yes, can u show me please how to do it?

Below are a the matrices Aeq and Beq,

   function in=f(out) 
N=30;
   E=speye(N,N+1);
   columns=cell(1,N);
   beq=-evaluate_equations(E(:,N+1));
   for i=1:N
     columns{i}=evaluate_equations(E(:,i))+ beq;
   end
   Aeq=cell2mat(columns);
   full(Aeq),
   full(beq),
function F=evaluate_equations(u)
F(1)=u(6)+u(7)+u(8)+u(9)+u(10)-1;
F(2)=u(11)+u(12)+u(13)+u(14)+u(15)-1;
F(3)=u(16)+u(17)+u(18)+u(19)+u(20)-1;
F(4)=u(21)+u(22)+u(23)+u(24)+u(25)-1;
F(5)=u(26)+u(27)+u(28)+u(29)+u(30)-1;
   F=F(:); %column vector

[imed NASRI]

I have considered a simple example with 30 unknowns as a test.

[Matt J]

Can u tell me please if my equality constraints can be partitioned or no?

If licols(Aeq) (the function I gave you earlier) returns an NxN matrix, then it is partitionable and A2 will be the NxN matrix returned.

[imed NASRI]

If we look to the example that u have gave it earlier. If i suppose that i have the above equality constraint:

    x1+x2+x3=d

suppose that i have replaced x3 everywhere by d-x1-x2. How can the ga() return the value of x3? Because x3 was eliminated from all the constraints and my vector x=[x1;x2;x3]?

[Matt J]

Once ga has solved for x1,x2 you can recover x3 from the equation

 x3=d-x1-x2

[imed NASRI]

But in this example size(x)=(3,1) and there is no constraint that contain x3 so what value will return the ga for x3?

[Matt J]

No, once you've eliminated x3 from the problem, you are left with a 2D reformulation in which size(x)=[2,1]. It is this reduced problem that you would pass to GA.

[imed NASRI]

so i have to reformulate manually the problem? But when the problem becomes more complex which is the case of my problem (40.200 unkowns), the reformulation becomes very difficult and not convenient.

[Matt J]

No, not manually. We talked about making the matrix partition Aeq=[A1,A2] and using it to derive a matrix expression for the eliminated variables,

 x_elim = (A2\beq)-(A2\A1)*x_keep
        = c-D*x_keep

This elimination formula can be substituted into your existing expressions and used to derive new ones. These operations can be done using MATLAB matrix manipulation expressions independent of the problem dimension.

For example, the linear inequalities can be similarly partitioned with Aineq=[A3,A4] leading to

 [A3, A4]*[x_keep; x_elim] <=bineq

Substituting the variable elimination formula leads to

 bineq >= A3*x_keep +A4*x_elim 
        = A3*x_keep +A4*(c-D*x_keep)
        = (A3-A4*D)*x_keep +A4*c

Rearranging this leads to reduced inequalities

(A3-A4*D)*x_keep <= (bineq - A4*c)

I.e., your new Aineq is (A3-A4*D) while the vector (bineq-A4*c) replaces your original bineq.

[imed NASRI]

For the linear inequalities licols(Aineq)=Aineq. Is this normal? Also Aineq is not a sqare matrix.

[Matt J]

There's no reason to be applying licols() to Aineq. It is Aeq that is used to eliminate variables. Therefore, it is the partitioning of Aeq that determines the partitioning of everything else.

[imed NASRI]

But in the example shown above. you have done the partitioning of Aineq?

For example, the linear inequalities can be similarly partitioned with Aineq=[A3,A4] leading to

 [A3, A4]*[x_keep; x_elim] <=bineq

Substituting the variable elimination formula leads to

 bineq >= A3*x_keep +A4*x_elim 
        = A3*x_keep +A4*(c-D*x_keep)
        = (A3-A4*D)*x_keep +A4*c
Rearranging this leads to reduced inequalities

(A3-A4*D)*x_keep <= (bineq - A4*c) I.e., your new Aineq is (A3-A4*D) while the vector (bineq-A4*c) replaces your original bineq.

[Matt J]

Yes, but that partitioning is dictated by licols(Aeq), not licols(Aineq). Once you've used licols(Aeq) to partition x into x_elim and x_keep, you now want to rewrite

 Aineq*x<=bineq

in terms of the same x_elim and x_keep.

Note that licols has additional output arguments telling you the indices of the matrix columns that belong to x_elim. That info is reusable as you reformulate both your inequality constraints and any nonlinear constraints you might add later.

[imed NASRI]

The inequality constraints of my problem where size(u)=[30,1] are:

   F(1)=5*u(6)+5*u(11)+1*u(16)+6*u(21)+3*u(26)-10;
   F(2)=5*u(7)+5*u(12)+1*u(17)+6*u(22)+3*u(27)-10;
   F(3)=5*u(8)+5*u(13)+1*u(18)+6*u(23)+3*u(28)-10;
   F(4)=5*u(9)+5*u(14)+1*u(19)+6*u(24)+3*u(29)-10;
   F(5)=5*u(10)+5*u(15)+1*u(20)+6*u(25)+3*u(30)-10;
   F(6)=4*u(6)+6*u(11)+3*u(16)+8*u(21)+4*u(26)-10;
   F(7)=4*u(7)+6*u(12)+3*u(17)+8*u(22)+4*u(27)-10;
   F(8)=4*u(8)+6*u(13)+3*u(18)+8*u(23)+4*u(28)-10;
   F(9)=4*u(9)+6*u(14)+3*u(19)+8*u(24)+4*u(29)-10;
   F(10)=4*u(10)+6*u(15)+3*u(20)+8*u(25)+4*u(30)-10;
   F(11)=1*u(6)+2*u(11)+6*u(16)+5*u(21)+5*u(26)-10;
   F(12)=1*u(7)+2*u(12)+6*u(17)+5*u(22)+5*u(27)-10;
   F(13)=1*u(8)+2*u(13)+6*u(18)+5*u(23)+5*u(28)-10;
   F(14)=1*u(9)+2*u(14)+6*u(19)+5*u(24)+5*u(29)-10;
   F(15)=1*u(10)+2*u(15)+6*u(20)+5*u(25)+5*u(30)-10;
   F(16)=3*u(6)+4*u(11)+4*u(16)+2*u(21)+2*u(26)-10;
   F(17)=3*u(7)+4*u(12)+4*u(17)+2*u(22)+2*u(27)-10;
   F(18)=3*u(8)+4*u(13)+4*u(18)+2*u(23)+2*u(28)-10;
   F(19)=3*u(9)+4*u(14)+4*u(19)+2*u(24)+2*u(29)-10;
   F(20)=3*u(10)+4*u(15)+4*u(20)+2*u(25)+2*u(30)-10;
F(21)=u(6)-u(1)-0;
F(22)=u(11)-u(1)-0;
F(23)=u(16)-u(1)-0;
F(24)=u(21)-u(1)-0;
F(25)=u(26)-u(1)-0;
F(26)=u(7)-u(2)-0;
F(27)=u(12)-u(2)-0;
F(28)=u(17)-u(2)-0;
F(29)=u(22)-u(2)-0;
F(30)=u(27)-u(2)-0;
F(31)=u(8)-u(3)-0;
F(32)=u(13)-u(3)-0;
F(33)=u(18)-u(3)-0;
F(34)=u(23)-u(3)-0;
F(35)=u(28)-u(3)-0;
F(36)=u(9)-u(4)-0;
F(37)=u(14)-u(4)-0;
F(38)=u(19)-u(4)-0;
F(39)=u(24)-u(4)-0;
F(40)=u(29)-u(4)-0;
F(41)=u(10)-u(5)-0;
F(42)=u(15)-u(5)-0;
F(43)=u(20)-u(5)-0;
F(44)=u(25)-u(5)-0;
F(45)=u(30)-u(5)-0;
F(46)=u(6)+u(16)-1;
F(47)=u(7)+u(17)-1;
F(48)=u(8)+u(18)-1;
F(49)=u(9)+u(19)-1;
F(50)=u(10)+u(20)-1;
F(51)=u(11)+u(16)-1;
F(52)=u(12)+u(17)-1;
F(53)=u(13)+u(18)-1;
F(54)=u(14)+u(19)-1;
F(55)=u(15)+u(20)-1;

And the equality constraints of the same problem are:

F(1)=u(6)+u(7)+u(8)+u(9)+u(10)-1;
F(2)=u(11)+u(12)+u(13)+u(14)+u(15)-1;
F(3)=u(16)+u(17)+u(18)+u(19)+u(20)-1;
F(4)=u(21)+u(22)+u(23)+u(24)+u(25)-1;
F(5)=u(26)+u(27)+u(28)+u(29)+u(30)-1;
F(6)=u(6)-0;
F(7)=u(7)-0;
F(8)=u(8)-0;
F(9)=u(9)-0;
F(10)=u(11)-0;
F(11)=u(12)-0;
F(12)=u(13)-0;
F(13)=u(14)-0;
F(14)=u(16)-0;
F(15)=u(17)-0;
F(16)=u(21)-0;
F(17)=u(22)-0;
F(18)=u(25)-0;
F(19)=u(28)-0;
F(20)=u(29)-0;
F(21)=u(30)-0;

I wonder what system i must to give to the ga() to solve? And how can i calculate then automatically

 x_elim and x_keep

[imed NASRI]

Also how can determine the indices of the matrix columns (called idx in your function licols) that belong to x_elim. Because licols(Aeq) return only A2 called X in your code of the function licols. Is idx=A1? Thank u.

[Matt J]

 A2=Aeq(:,idx)
 x_elim=x(idx);

Indicies not in idx correspond to x_keep and A1.

[imed NASRI]

Note that:

    lb=zeros(30,1) and ub=ones(30,1) and IntCon=1:30

[imed NASRI]

my objective function to minimize is:

    sum(u(1:5))

[Matt J]

lb and ub give additional inequality constraints. They can be re-expressed by adding rows to Aineq.

[imed NASRI]

Yes but it makes no difference if they are declared as lb and ub? ga solves integer problems best when you provide lower and upper bounds for every x component which is mentionned in

http://www.mathworks.fr/fr/help/gads/mixed-integer-optimization.html#bs1clc2

[Matt J]

After you've reduced the problem, you can still include those bounds on x_keep.

[imed NASRI]

what does it change? frankly, I do not see how to reduce automatically the problem and then find x_elim and x_keep just by manipulating matrices in Matlab. Because I have done it manually, but it's so difficult as a procedure especially when you are face a very complex problem with multiple variables.

[Matt J]

frankly, I do not see how to reduce automatically the problem and then find x_elim and x_keep just by manipulating matrices in Matlab.

What about everything we discussed yesterday?!?! How can you not see it, when you've already been shown matrix equations for it?

Anyway, let me be clear. This whole reformulation exercise has only been to accomodate your supervisor's peculiar obsession with GA. The true recommendable way to solve the problem is bintprog.

[imed NASRI]

In the case of the problem that i have sent to you

    u_keep=[u(1);u(2);u(3);u(4);u(5);u(19);u(20);u(24);u(27)]

Therefore the size of the vector u is reduced from [30x1] to [9x1]. The ambiguity for me is how to change the indices of the components of the new vector u, in order to use ga().

i.e. In the new reformulation of the problem

    u(19) becomes u(6) in the new vector u
    u(20) becomes u(7)
    u(24) becomes u(8) and
    u(27) becomes u(9)

I wonder if i can do automatically and not manually this changement of indices. I hope that i'm clear.

[Matt J]

As I said before, the output idx from licols tells you the indices to be eliminated. Therefore

 idx_keep = setdiff(1:30,idx);

 u_keep=u(idx_keep);

[imed NASRI]

You didn't understand what i try to explain to you. In the above problem:

   idx_keep = setdiff(1:30,idx)=[1 2 3 4 5 19 20 24 27]

Therfore:

    u_keep=[u(1);u(2);u(3);u(4);u(5);u(19);u(20);u(24);u(27)]

Consequently, the new constraints of my problem are:

F(1)=-3*u(27)-7;
F(2)=3*u(27)-10
F(3)=-u(19)-u(20)-6*u(24)-3
.
.
.
F(21)=f(u_keep)+d

My problem is how to change automatically the indices in the new reduced vector u to have the new formulation as follow:

   F(1)=-10;
F(2)=-3*u(9)-10
F(3)=-u(6)-u(7)-6u(8)-3
.
.
.

Consequently, i will give to the ga() the new Aineq whose size is [21x9] and the new u to find whose size is [9x1]

[Matt J]

My problem is how to change automatically the indices in the new reduced vector u to have the new formulation as follow:

You aren't using ga to solve for u anymore. You are also not writing your functions in terms of

[u(1);u(2);u(3);u(4);u(5);u(19);u(20);u(24);u(27)].'

You are supposed to be writing them in terms of

 u_keep = [u_keep(1),...,u_keep(9)].'

Furthermore, in your code, you don't need to index either u_keep(i) or u(i) individually, because you now have matrices to represent the objective and constraints. You should be calling ga() using the syntax

 x = ga(fitnessfcn,9,A,b,Aeq,beq,LB,UB)

where A,b,Aeq,beq are the reduced matrices and LB,UB are bounds on u_keep that we've been talking about.

You shouldn't have to use the nonlcon nonlinear constraint arguments anymore, but even if you were to do so, you wouldn't write individual equations for F(i). You would write vector/matrix expressions for F, and you would write them in terms of u_keep, not u:

x = ga(fitnessfcn,9,[],[],[],[],LB,UB,...
       @(u_keep) constraints(u_keep,Aeq,beq,Aineq,bineq) )

function [Fineq, F]=constraints(ukeep, Aeq,beq,Aineq,bineq)

   F=Aeq*u_keep-beq;
   Fineq=Aineq*u_keep-bineq;

end

The only indexing you need to do is at the very end when you want to translate ga's solution for u_keep back into the full u in the original formulation. For that, you would do

 u=zeros(30,1);

 u(idx_keep)= u_keep;
 u(idx)=c-D*u_keep; %the elimination equation

[imed NASRI]

Thank you very much. It works :).

[Matt J]

Hurray!!

[imed NASRI]

i have tried to apply the method that you have proposed to me to an other example which is more complex(420 unknowns). Unfortunately, some

    u_elim=u(idx)=c-D*u_keep<0

I don't why i have some negative variables?

[imed NASRI]

I know why i have some negative values. the equality constraints in my problem have the following form:

    x1+x2+x3=1

seeing that xi={0,1}, the above equality means that just one of the variables is equal to 1 the others are set to 0. When you eliminate for example x3 and you replace it by 1-x1-x2 in the inequality equations, ga () can return x2=x1=1 which can satisfy the inequality constraints. But when you deduced the value of x3 from the value of x1 and x2 you have x3=-1. To conclude, it's not a good idea to eliminate equality constraints because they can be violated !!!!!

[Matt J]

To conclude, it's not a good idea to eliminate equality constraints because they can be violated !!!!!

No, you overlooked part of what I told you earlier. You must use the reduction formula to convert your upper and lower bound inequalities in addition to your original Aineq, bineq inequalities.

So for example, in your original 3-variable formulation above, you originally have the bound inequality

 x3>=0

When you apply the reduction formula you obtain

 1-x1-x2>=0

or equivalently

 x1+x2<=1

This must be appended to the reduced Aineq, bineq. If it is, the algorithm will not be allowed to accept x1=x2=1 as a solution, since it clearly violates the above inequality.

[imed NASRI]

even by converting the upper and lower bound inequalities in addition to my original Aineq, bineq inequalities, The ga() violetes in some runs these inequality constraints!!!

[Matt J]

If ga() couldn't find a point x_keep that satisfies the constraints, the exitflag and exit messages would tell you that a feasible point was not found. In that case, it's always possible that your constraints are not feasible. For example, the following constraint set is non-empty on the reals, but empty on the integers

 x1>=0
 x2>=0
 x1+x2<=.5

If a feasible x_keep point was found, but the constraints on x_elim are still violated, then you have a coding error.

[imed NASRI]

in some runs the ga() finds a feasible x_keep and the exitflag=1 (all constraints are satisfied) but in some runs the ga() violates some lower and upper bound added inequalities.

[imed NASRI]

In the case where the ga() has found x_keep feasible (only the first two runs) x_elim are satisfied). in the other runs that i have done, the ga() is not able to find a feasible x_keep!!!

[Matt J]

Then maybe a feasible solution does not exist. You can always check by solving the problem (as originally formulated) using bintprog.

[imed NASRI]

A feasible solution exists because ga() finds a feasible solution in some runs. I have tried to solve the same problem using LINGO solver because bintprog is very slow. LINGO finds quickly an optimal solution that satisfied all constraints.

[Matt J]

A feasible solution exists because ga() finds a feasible solution in some runs.

Meaning that you are not changing the problem data at all between runs? You are running ga() multiple times with the exact same initial population in the exact some way on the exact same problem?

LINGO finds quickly an optimal solution that satisfied all constraints.

You should take the LINGO solution and check if it satisfies the reduced constraints as well. If it does not, you have a coding error in the reduction step. The reduced problem is equivalent to the original problem.

If the LINGO solution does satisfy both the original constraints and the reduced constraints, then it confirms what I think we suspected all along: GA is not the most robust solver you can use for these problems. You can report that to your supervisor, who insists on using it.

Regardless, you might try including the LINGO solution in the Initial Population when running GA. It could be just an initialization issue.

[imed NASRI]

Regardless, you might try including the LINGO solution in the Initial Population when running GA. It could be just an initialization issue.

I have tried to add some feasible solutions generated by LINGO in the initial population of ga(). But the ga() converges to the best solution belonging to the initial population.

[Matt J]

No, I meant you should try adding the optimal solution as computed by LINGO to the initial population. It would just be a simple check that GA can find it if it has the right population.

[imed NASRI]

By adding the optimal solution to the initial population, ga() converges to this solution.

[Matt J]

Then it sounds like you've concluded your research on this subject: GA can work, but isn't as robust as a dedicated binary linear programming algorithm.

[imed NASRI]

You should take the LINGO solution and check if it satisfies the reduced constraints as well. If it does not, you have a coding error in the reduction step. The reduced problem is equivalent to the original problem.

The LINGO solution does not satisfy the reduced constraints. However i have applied your method to reduce the problem and to create A_keep and A_elim?

[Matt J]

The LINGO solution has to satisfy the reduced constraints because you already said that GA converges to it when it is included in the initial population. GA cannot converge to something that does not satisfy the constraints given to it.

[imed NASRI]

Sorry i have done a mistake when i have copied the solution of LINGO. It satisfies the reduced constraints. So the problem is the robustness of ga().

[imed NASRI]

i have noticed that when i add the optimal solution of LINGO to the intial population and when i set EliteCount to 0, the ga() can not find a solution. But if i add the optimal solution of LINGO to the intial population and when i set EliteCount to 1 or more, the ga() converges to this solution. I think that the problem is the evalution function of ga() (penality function). This function is not suitable

[Matt J]

i have noticed that when i add the optimal solution of LINGO to the intial population and when i set EliteCount to 0, the ga() can not find a solution.

EliteCount is supposed to be a positive integer less than the population size. Otherwise, no population members survive to the next generation.

This function is not suitable

I'd be curious to know what advantage your supervisor thought it would have over bintprog (or LINGO).

[imed NASRI]

There is an other thing that i don't understand. Why all the files of the mixed integer ga solver of the ga toolbox are .p files? Do you know if i can open these files?

[imed NASRI]

they have used binary programming optimization with an other candidate and now they want to use Genetic Algorithms to compare the two methods.

[Matt J]

.p files are encrypted mfiles. TMW wants to keep their contents proprietary.

Why compare with GA, though? Why even expect it to be better than bintprog/LINGO?

[imed NASRI]

because they want to add an other criterion to minimize to the problem. They think that GA is suitable for multiobjective optimization.

[suvrat]

So finally you concluded mixed integer linear programming with equality constrain and inequality constrain can't be solved by ga in matlab? problem is due to equality constrain? if remove eqaulty constrain will it work? secondly binary integer programming with inequality constrain only no eqaulity can be solved by ga.is it will be better than lingo? please help my. thank you.

[Matt J]

@suvrat,

No, the conclusion of imed's findings is that GA does not robustly solve binary linear programs even when only inequality constraints are present. More general mixed integer and non-binary problems were never looked at.

I don't have the Global Optimization Toolbox, so I have no way of verifying imed's findings. However, to my understanding, GA is a stochastic algorithm. If so, it makes sense in my mind that it has some probability of failure, in contrast to bintprog/LINGO

[Vitor Ribeiro]

In fact, after some simulations, with GA working in same parameters as I initially state, I can see that when it finds a feasible solution GA rapidly learn and apparently converge because it is evaluating more feasible solutions around the 1st one it reach.

In many literature there are results showing that GA is a really good choice for solving problems of topology optimization with his basic heuristic formulation. I'm not certain about the mean code of GA function but I am convinced that it respects the heuristic core.

I'm not saying that GA in matlab works better then any other optimization function cause I do not have the knowledge for that. I don't know if BINTPROG or even INTLINPROG works better. I am interested in see documentation explaining how it works before seeing how it's used. If you can provide some link it would be really helpful.

After I can see how it works this functions, about how the solutions are generated or even search space composed by solutions are really searched by this algorithms, if they have an heuristic base, I would be able to choose research more in literature and probably understand which works better before I apply it in my problem indiscriminately.

Thank you all for your answers. I really appreciate each one.

[Matt J]

I've only now realized that there is a pitfall with the variable elimination approach. When using the equality constraints alone to eliminate variables, there is nothing ensuring that the eliminated variables will end up being integers. :-(