what is the maximum population size handled by GA ? What are your advices for large MINLP problems?

I am trying to solve a MINLP problem using genetic algorithm.

My number of decision variables are 168.

• 96 of these decision variables are binary [0 1]
• Remaining 72 variables can take the integer values of [1 2 3].

The problem is accurately formulated and there is no doubt about it.

Following are my doubts:

1. What is the appropriate population size to be used ? I am trying : 2*168 , 3*168 and 4*168. But the size seems to be large. Since all the decision variables are integers, what do you suggest about the population size ?
2. For different initial guesses, I get different different optimized solutions. I am using 20,50 and 60 % of the population size as initial population matrix. Of-course, I know that we cannot guarantee global optimum with GA; but still what can you suggest to get global optimum ? Trying multiple times and getting lowest fval doesnt sound good to me.
3. The mutants are taken as 10% of total population. Can you suggest an appropriate size of it ?

Finally, when initial population matrix is not defined at all, I do not get the linear constraints (inequality) satisfied. But with some initial population size, I get ( but i think the optimum values are local and not global.

1. Other than genetic algorithm, are there other optimizers for such problems ? (I do not like to think surrogate-optimization)
2. Are there other toolboxes (apart from global optimization toolbox), which are free but can be use to handle large MINLP?

Thanks

Answer 1

[Alan Weiss]

General MINLP with over 100 variables are not solvable globally. How can I make this blanket statement? For a general MINLP with 100 binary variables, to guarantee a global minimum you would need to evaluate the objective on all

2^100

ans = 1.2677e+30

points, which takes entirely too long even if you could evaluate 10^10 points per second. ga uses heuristics to attempt to find a global minimum, but has no guarantees, and as I just showed, no algorithm is guaranteed to find the global minimum of a general MINLP with over 100 variables.

So what can you do? Well, it depends on whether your objective function has any nice properties. For example, if your objective function is convex, you might be able to use the technique in Mixed-Integer Quadratic Programming Portfolio Optimization: Problem-Based. The idea there is to approximate the problem by a MILP and iteratively refine it. Not so straightforward in general.

Or perhaps your objective function is close to linear. In that case, try solving it using intlinprog. Then, if necessary, refine the constraints or objective and try again.

But in general, no matter what you try you are not going to be able to guarantee that you found the global minimum.

If you must use ga, try using a large population, parallel evaluation, and maybe use intlinprog to help generate feasible initial points using random objective function vectors and the problem's linear constraints and bounds.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

[parag patil]

Thanks for your answer.

1. I am using parallel computing.
2. I want to ask : Then how people solve the big MINLP problems ? Do the dedicated optimization solvers such as GAMS are capable to solve such problems ? Or , it does not matter, what I use, I will NOT ABLE TO SOLVE it globally ?

I am trying to do following workaround :

1. Get all feasible solutions ( as I have constraints ) for some of these decision variables. And remove them from optimization problem. ( Say I have 200 feasible solutions, then I will optimize 200 times and find minimum fval to call it optimum)

However problem with above approach is, I do not have anything to find all feasible solutions ( even if i have all integers ( meaning finite) as decision variables). I will not have 2^100 ( as there are constraints too).

But yes I agree that it will be large.

What would you advice ?

Thanks

[Steven Lord]

If you wanted to guarantee a solution to the problem with 2^100 points and you had a cluster of a million machines each of which could calculate the value of your function at a million points a second, how long would it take?

million = 1e6;
npoints = sym(2)^100;
nseconds = double(npoints/(million^2));
Y = years(seconds(nseconds))

Y = 4.0170e+10

According to the timeline of the far future the Earth and moon likely have already been destroyed by the time your cluster finished.

Brute force will not work for this problem.

[parag patil]

Dear Steven,

I would slighlty disagree with you.

Why are you taking into account all 2^100 points ? Would not it be like solving a hand problem? If it is so, what is the point of optimization then ?

I am sorry but instead of showing off your fancy calculations of required years, why dont you try to find , how to solve MINLP problems of such a large number of decision variables ?

Try to refrain adding nonsense answers here and instead try help people else do not answer.

Thanks

[parag patil]

Steven, you should look into literature.

People have solved many such large MINLP problems with large number of variables.

For instance a recent paper in Computers and Chemical Engineering shows to solve a MINLP problem with following:

• Cont. vars : 7800
• Binary vars : 480
• Equality constraints: 4320
• Inequality constraints: 38164

Here is the LINK of the paper : Paper

By the way, they have solved it and the Earth is there.. Moon is here too