Mixed Integer Linear Programming using GA for solution generation of network topology

Hello,

I'm trying to use mixed integer linear programming (MILP) as recommended by Alan Weiss to solve an optimization network topology problem.

I've set all of the parameters, as documentation about MILP states (adapted to my problem), but when I run the GA function some generated solutions do not respect what I initially had defined.

I have 41 binary variables corresponding to all branches of a network composed by 30 bus with 6 generators. For this network to be radial, I need in all generated solutions to be valid ones, having exactly 24 (30-6) active branches, corresopnding to 24 1's in the solution vector x.

The problem is that I am having many solutions being evaluated by ff that do not verify this restriction.

I don't know if my text is clear, but if you can help me I really appreciate.

Best regards, Vitor Ribeiro.

Answer 1

[Matt J]

If it's a MILP, it might be more robust, as well as easier, to use intlinprog, as opposed to ga. Beyond that, we cannot say what's wrong without seeing your code.

[Vitor Ribeiro]

I really want to use GA in this problem because that is one of my objectives. Is it possible that genetic operators applied to the initial generated solutions are distorting the solutions so they can somehow differ from defined parameters?

The crossover or the mutation in the base form can actually change the initial solutions so they don't match the defined restrictions defined as parameters of the GA function. Is it possible be happening?

I present you used code referenced above, so you can possibly find some simple 'bug'. Thanks for your help.

%%Options prameters for Mixed Integer Programming

% Default parameters
options = gaoptimset;

% Modifying options setting
options = gaoptimset(options,'PopulationType', 'doubleVector');
options = gaoptimset(options,'Display', 'off','PopulationSize',200);

%%Mixed Integer GA parameters

nvars=41;

lb=zeros(1,nvars);     % bounds
ub=ones(1,nvars);
fitnessfcn=@f_perdas;  % Fitness Function

a1=ones(1,nvars);
a2=a1*(-1);

n_bus=30;
nbus_pv=6;              % Nº of PV bus (for radial constraints)
nn=n_bus-nbus_pv;       % nn - Nº of active branches

A=[a1;a2];              % Constraint of active branches
b=[nn;nn*(-1)];

nonlcon=[];

% Indentifying affected variables
IntCon=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41];

%%Running GA 

[x,fval,exitflag,output,population,scores] = ga(fitnessfcn,nvars,A,b,[],[],...
     lb,ub,nonlcon,IntCon,options);

if true
  % code
end

[Alan Weiss]

I agree that intlinprog is a far, far better choice for solving MILP problems. Also, GA does not solve equality-constrained problems very well at all, which is why they are disallowed for mixed-integer GA. You are using the workaround, but should not be surprised that the workaround does not always work.

I suggest that, if you insist on using GA, you give a much larger population for GA, and even more importantly, give an initial feasible partial population. It could be that GA is having a hard time finding a feasible initial population.

And even better, I suggest that you use intlinprog instead of GA.

Alan Weiss

MATLAB mathematical toolbox documentation

[Matt J]

I really want to use GA in this problem because that is one of my objectives.

Even when GA is known to be poorer than more standard MILP methods? Or are you saying that you question that? And if so, why?

Also, GA does not solve equality-constrained problems very well at all, which is why they are disallowed for mixed-integer GA. You are using the workaround, but should not be surprised that the workaround does not always work.

The workaround is to express an equality constraint using inequality constraints? I believe the elimination method discussed in the following Answer might be a safer way to reformulate equality constraints,

http://www.mathworks.com/matlabcentral/answers/104739#answer_114013

However, the conclusion of that discussion was that GA was not as robust as a non-stochastic LP solver, even when only inequality constraints are present and even for purely binary integer programs. I'm not optimistic that this more complicated case would be any different.

[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 in discussion. Hope you can help me. Regards, Vitor Ribeiro.

[Matt J]

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.

You need to verify, though, that it converges to the right thing. I.e., check that the final solution and objective value it gives agree with intlinprog. You also need to check that it does so 99% of the time, and not say 80%.

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.

Google's your friend,

http://www.mathworks.com/help/optim/ug/mixed-integer-linear-programming-algorithms.html

http://www.mathworks.com/help/optim/ug/binary-integer-programming-algorithms.html