However i have transformed the equality constraints to inequality constraints using a tolerance.
ga() already applies a tolerance parameter "TolCon" to the constraints.
You can never expect to satisfy equality constraints exactly.
Integer constrained optimization using the "ga" (genetic algorithm) solver of MATLAB - can anyone help?
6 次查看（过去 30 天）
显示 更早的评论
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?
采纳的回答
Matt J
2013-11-3
编辑：Matt J
2013-11-3
7 个评论
Matt J
2013-11-3
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
2013-11-3
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
that since you are using the IntCon option, equality constraints are not allowed.
imed NASRI
2013-11-3
编辑：imed NASRI
2013-11-3
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.
imed NASRI
2013-11-3
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
2013-11-3
编辑：Matt J
2013-11-3
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.
更多回答（3 个）
imed NASRI
2013-11-3
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!!!!!
Matt J
2013-11-3
编辑：Matt J
2013-11-3
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.
6 个评论
imed NASRI
2013-11-3
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
2013-11-3
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
2013-11-3
i've tried this reformulation with slack=1e-3, but the constraints are violated.
imed NASRI
2013-11-3
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
2013-11-3
编辑：Matt J
2013-11-3
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.
73 个评论
imed NASRI
2013-11-4
编辑：imed NASRI
2013-11-4
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
2013-11-4
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
2013-11-4
编辑：Matt J
2013-11-4
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
2013-11-4
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.
imed NASRI
2013-11-4
编辑：imed NASRI
2013-11-4
Yes, I have passed them as nonlinear constraints [c,ceq] and it works.
imed NASRI
2013-11-4
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
2013-11-4
编辑：Matt J
2013-11-4
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
2013-11-4
编辑：imed NASRI
2013-11-4
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
2013-11-4
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
2013-11-4
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
2013-11-4
编辑：Matt J
2013-11-4
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
2013-11-5
编辑：imed NASRI
2013-11-5
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?
imed NASRI
2013-11-5
I have tried to run your example and i recieve the following error message:
Function definitions are not permitted in this context.
Matt J
2013-11-5
Probably because the mfile you put the code in doesn't have
function in=f(out)
at the top.
imed NASRI
2013-11-5
编辑：imed NASRI
2013-11-5
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
2013-11-5
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]?
imed NASRI
2013-11-5
编辑：imed NASRI
2013-11-5
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?
imed NASRI
2013-11-5
编辑：imed NASRI
2013-11-5
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
2013-11-5
编辑：Matt J
2013-11-5
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
2013-11-6
For the linear inequalities licols(Aineq)=Aineq. Is this normal? Also Aineq is not a sqare matrix.
Matt J
2013-11-6
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
2013-11-6
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
2013-11-6
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
2013-11-6
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
2013-11-6
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
2013-11-6
lb and ub give additional inequality constraints. They can be re-expressed by adding rows to Aineq.
imed NASRI
2013-11-6
编辑：imed NASRI
2013-11-6
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
imed NASRI
2013-11-6
编辑：imed NASRI
2013-11-6
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
2013-11-6
编辑：Matt J
2013-11-6
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
2013-11-6
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
2013-11-6
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
2013-11-6
编辑：imed NASRI
2013-11-6
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
2013-11-6
编辑：Matt J
2013-11-6
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
2013-11-8
编辑：imed NASRI
2013-11-8
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
2013-11-8
编辑：imed NASRI
2013-11-8
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
2013-11-9
编辑：Matt J
2013-11-9
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
2013-11-9
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
2013-11-9
编辑：Matt J
2013-11-9
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
2013-11-9
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
2013-11-9
编辑：imed NASRI
2013-11-9
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
2013-11-10
Then maybe a feasible solution does not exist. You can always check by solving the problem (as originally formulated) using bintprog.
imed NASRI
2013-11-10
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
2013-11-10
编辑：Matt J
2013-11-10
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
2013-11-10
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.
imed NASRI
2013-11-10
编辑：imed NASRI
2013-11-10
By adding the optimal solution to the initial population, ga() converges to this solution.
imed NASRI
2013-11-13
编辑：imed NASRI
2013-11-13
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?
imed NASRI
2013-11-13
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
2013-11-13
编辑：imed NASRI
2013-11-13
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
2013-11-13
编辑：Matt J
2013-11-13
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
2013-11-13
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
2013-11-13
编辑：imed NASRI
2013-11-13
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
2013-11-13
.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
2013-11-13
because they want to add an other criterion to minimize to the problem. They think that GA is suitable for multiobjective optimization.
suvrat
2014-1-26
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
2014-1-26
编辑：Matt J
2014-8-26
@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
2014-9-10
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
2015-6-22
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. :-(
另请参阅
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!发生错误
由于页面发生更改，无法完成操作。请重新加载页面以查看其更新后的状态。
Translated by 
您也可以从以下列表中选择网站：
如何获得最佳网站性能
选择中国网站（中文或英文）以获得最佳网站性能。其他 MathWorks 国家/地区网站并未针对您所在位置的访问进行优化。
美洲
- América Latina (Español)
- Canada (English)
- United States (English)
欧洲
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)
亚太
- Australia (English)
- India (English)
- New Zealand (English)
- 中国
- 日本Japanese (日本語)
- 한국Korean (한국어)