Binary solutions with GA

Hi

I am currently working with GA on resource allocation and the goal is to find binary solutions with a non linear objective and linear constraints.

At the beginning of the project, I had a problem with more than 700 variables with many constraints and the solutions that I had from GA were very irrelevant. I thought the size of the problem was the issue.

So I broke down the problem into many models in order to have less that hundreds variables (in occurrence 30 variables for the current model I am building) and around hundreds constraints too for each model (in occurrence 95 linear constraints for the same current model). Besides, some of the constraints are normally equality constraints that I transformed into inequality constraints to help GA to find a solution. BUT at the end I still have solutions that don't correspond to the constraints. For the instance, for example if we want to allocate 30 bags in 5 cabinets so that each bag is allocated only in one cabinet, I got some results where one bag is allocated in many cabinets, even though the inequality constraints that I wrote seem totally correct.

I have this report at the end "Optimization terminated: average change in the penalty fitness value less than options.FunctionTolerance and constraint violation is less than options.ConstraintTolerance".

I don't really know what to do with this problem and I am quite in a need of a solution for an industrial (confidential) problem after having purchased GA weeks ago (the trials for smaller sizes seemed to work previously). Please could you give any support for that?

Thanks,

Loic

[Walter Roberson]

For your "30 bags in 5 cabinets" portion, are you handling that by using 30*5 = 150 binary decision variables, like taking the vector equivalent of (a 30 x 5 matrix in which a 1 in the J'th column indicated that the bag was in the J'th cabinet) ?

You are already using integer constraints in order to do binary, so you are already unable to use a nonlinear constraint function except by supplying your own population and mutation functions, so it might seem to make some sense to use a single integer in the range 1 to 5 for each bag, indicating which cabinet it is in, thus making it impossible for the system to consider it in multiple cabinets at the same time. (I think I worked out once how you could do capacity restraints on integer variables but it does not come to mind immediately.... perhaps I only worked out how to do it for binary decision variables.)

[Loic Wilfried Biakeu Njia]

The answer is "Yes" to your first question.

I am not quite sure to understand when you say "You are already unable to use a nonlinear constraint function": Do you mean my objective function must not be a non linear linear function as I already have linear constraints?"

For the capacity restraints on integer variables, did you change the coefficients that affect the constraints as you use now a single integer in the range of 1 to 5? (Just trying to figure out how you worked out on that previously)

[Walter Roberson]

https://www.mathworks.com/help/gads/ga.html#inputarg_nonlcon

nonlcon - nonlinear constraint function

"Function handle that returns two outputs:

[c,ceq] = nonlcon(x)

ga attempts to achieve c ≤ 0 and ceq = 0. c and ceq are row vectors when there are multiple constraints. Set unused outputs to [].

ga does not enforce nonlinear constraints to be satisfied when the PopulationType option is set to 'bitString' or 'custom'.

If IntCon is not empty, the second output of nonlcon (ceq) must be an empty entry ([])."

===

This has nothing to do with your objective function being non-linear: there are restrictions on using constraints with intcon set. nonlinear constraints are the easy way to code the kind of bounds you mentioned, but nonlinear equality constraints are not supported if you have IntCon set. Also,

"Note: When IntCon is nonempty, Aeq and beq must be an empty entry ([]), and nonlcon must return empty for ceq. For more information on integer programming, see Mixed Integer Optimization."

so linear equality constraints are not supported either. That makes it a nuisance to code equalities such as that the number of bags in a cabinet must be exactly 5. However, in some situations you can recode the equality constraint by first coding -1 entries in the A matrix and setting the b entry to the negative of the total: this ensures that at least that many entries are set. Then you code +1 entries in the A and set the corresponding b to the positive of the total: this ensures that no more than that many entries are set. The combination of "at least" and "no more than" can achieve an equality. However, at the moment I am not confident that the same kind of technique can be applied to non=binary integer decision variables.

[Loic Wilfried Biakeu Njia]

Hi. Thank you for your answers.

So, please what could finally be the solution of this? If when IntCon is set, Aeq and Ceq must be empty, what to do to have integer solutions at the end? Is it any way possible to still have integer solutions without IntCon but only using Aeq and Ceq? If not, what is the point or the purpose (as you said "nonlinear constraints are the easy way to code the kind of bounds you mentioned") for a MINLP to set Aeq and/or Ceq with no assurance to get integer solutions?

For my case, I already did exactly what you suggested on coding the -1 entries and then the +1 entries. As results, sometimes for the the same system and the same script, the solution seem relevant and sometimes not. I am wondering what could be the cause of that discrepancy?

At the end, please let us consider I use a single integer from 1 to 5 for each bag, I must certainly in that case change the constraints or totally change the objective function because of the new values of the decision variables that are actually now kind of "affectation" variables. Any idea on that please?

Thank you for your answers. Best,

Loic

[Loic Wilfried Biakeu Njia]

Please no one got an answer on this? Any other idea is welcome.

Thanks, Loic

[Walter Roberson]

"Is it any way possible to still have integer solutions without IntCon but only using Aeq and Ceq?"

No. In order to get integer solutions, you need to use IntCon or you need to provide custom creation and mutation functions that just happen to only return integers in the range you want. It is not possible to get integer solutions only using Aeq and Ceq. However, if you provide a custom creation and mutation function, and use PopulationType 'doubleVector' (the default) then you can use Aeq and Ceq. (You might need to provide custom crossover function as well.)

I have not figured out yet if it is possible to use just the nonlinear constraints to enforce maximum number of bags per cabinet when the variables are set to the cabinet number. Looking again, though, I do not see you mention a maximum number of bags per cabinet: you say 30 must go into 5 cabinets, but you did not (in what you posted) say that it was not permitted for all 30 bags to go into a single cabinet. Are there maximums? Is the requirement that each cabinet receive exactly 6 bags?

[Loic Wilfried Biakeu Njia]

"Are there maximums? Is the requirement that each cabinet receive exactly 6 bags?"

The objective is to balance the repartition of bags into the cabinet. The maximum a cabinet can receive is ceil(number of bags/number of cabinets), because we can have some cases where the number of bags is not even. For the second question, I didn't write exactly that requirement as an equality constraints. However, to avoid equality constraints, I wrote that each cabinet could receive more than floor(number of bags/number of cabinets) and less than ceil(number of bags/number of cabinets).

For your suggestion about custom creation and mutation function, I don't know more about. I will probably have a look on that.

Thanks,

[Walter Roberson]

Ah, good point about the number sometimes having to vary.

Answer 1

[Brendan Hamm]

This will be a bit length to answer this question again, but I have provided a way you can solve this problem in a previous post:

https://www.mathworks.com/matlabcentral/answers/303045-is-there-a-work-around-to-use-gamultiobj-with-linear-constraints-and-binary-variables

This does use a multiobjective problem, but the idea of writing the population, crossover and mutation functions is the same.

[Loic Wilfried Biakeu Njia]

Thanks Brendan for your answer! I like the way you took on the issue.

I have tried your solution but unfortunately it doesn't work for my case. It get stuck in the popFun function and indefinitely computes but I think never finds a Population that conforms all the constraints.

[Brendan Hamm]

If you post it on here I will take a look when I have some time and suggest some possible alternatives.