MINLP problem in MATLAB with both integer constraints and nonlinear equality constraints

Knowing that: “When there are integer constraints, ga and gamultiobj do not accept nonlinear equality constraints, only nonlinear inequality constraints.”, How do you solve MINLP problems of the following form in MATLAB?

[Torsten]

Maybe OP should first confirm that his/her nonlinear equality constraints really depend on the integer variables in the solution vector before giving explanations why such problems don't make much sense.

[John D'Errico]

@Torsten

If you want to be helpful, then be helpful. Offer a constructive solution to the case you have identified.

Of course such a problem makes sense, at least to the OP, where they apparently have such a problem. Nobody has said it does not make sense. HOWEVER...

TOOLS LIKE GA DO NOT ALLOW INTEGER VARIABLES IN ADDITION TO NONLINEAR EQUALITY CONSTRAINTS. PERIOD. AND THERE ARE GOOD REASONS WHY NOT. We have explained why such problems are so difficult to solve, and why these codes do not accept such a problem.

Confirmation of whether the constraints apply to any of the integer variables does not matter, in terms of tools such as GA. Those tools will not solve such a problem. And there are no general tools in MATLAB that I can think of that do offer solutions to that class of problem.

[Torsten]

If you want to be helpful, then be helpful. Offer a constructive solution to the case you have identified.

There will be no standard approach in MATLAB to handle such problems. A viable solution (if there is any) will depend on OP's specific problem (and we don't know this problem yet). I wanted to emphasize that cases where the integer variables don't influence the equality constraints are reasonable in my opinion and on the first view more easy to approach with the existing MATLAB tools - your answer to the OP's question was too general and sounded too destructive in my opinion. But you added an "Edit" section now ...

Answer 1

[Matt J]

Such problems usually do not have solutions (EDIT: unless the equalities depend only on the continuous variables), since a nonlinear equation is very unlikely to be satisfied by integers. This is probably one reason ga() doesn't allow it. However, you can still attempt to solve it by approximating your equalities by inequalities. I.e., replace the equalities,

ceq(x)=0

with the approximate inequalities,

  ceq(x) <= delta
 -ceq(x) <= delta

where delta>0 is some small tuning parameter chosen by you.

Alternatively, you can modify your fitness function with a penalty on the inequality violation, e.g,

 newFitness(x) = oldFitness(x) + w*abs(ceq(x))

where again the penalty weight w>0 is a tuning parameter chosen by you. This will not enforce the equality constraints exactly, but the solver will put more priority on them as w is made larger.

Answer 2

[John D'Errico]

NOPE. Were I writing that code, hoping to solve a problem with integer variables, and general nonlinear equality constraints, etc., I would say, sorry. Try somewhere else. Exactly what they told you.

Think about it, suppose the nonlinear equality constraint was of the simple looking form:

x^2 - n*y^2 == 1

Yes. A Pell equation. And while it seems pretty innocuous, it is not so much.

https://en.wikipedia.org/wiki/Pell%27s_equation

Depending on the value of n, the solutions can be nearly as rare as hen's teeth. For example, when n=61, the first solution you will trip over lies out at (x,y) = (1766319049,226153980). What is worse, that solution would cause double precision arithmetic to fail to represent the squares of those numbers correctly.

Now, how does GA work? It first finds a set of feasible solutions. Should it be expected to understand the Pell equation theory to know how to find those solutions, as well as others in that family? Of course not. In fact, it is often the case that integer solutions to nonlinear equations will be difficult to find. There will be no simple general method to find such solutions. That would often be equation specific, and if you have more than one equation? Or you also have linear equality constraints? Forget it.

You might specify any of infinitely many possible nonlinear equality constraints. Sorry, but asking a general code to solve your problem will be difficult, especially one in the class of GA. Not gonna happen.

Any possible solution in MATLAB might depend on exactly what form your constraints take. It might require you to write some code yourself, or accept a solver that will ignore the integer requirements, and then round the result. Or you might relax the nonlinear equality constraint(s) in some way. Again, remember that integer solutions to any nonlinear equation will often require an understanding of special mathematics, something that will not be accessible to a general solver.

Edit:

Even in the seemingly somewhat rare case with mixed variable types such that the integer variables are not involved in any nonlinear equality constraints, the simplest solution might then be to isolate the integer variables. Set them to all possible combinations of fixed values, then solve the problem for all continuous variables using a standard solver. Then just take the best possible solution over the entire set of combinations of the integer variables. This is not at all uncommon to do, for problems with only a few discrete variables.

In the case where the integer variables are involved in nonlinear equality constraints, this just focuses the problem on something you need to do anyway. You will need to identify the potential integer solutions. For example, suppose the problem were a simple one, where the nonlinear equality constraint is

z^2 = x^2 + y^2

where (x,y,z) must all be integer, then there are known solutions to the Pythagorean triple problem, that will generate all (infinitely many) such possible solutions as a parameterized family. Effectively, this allows you to remove the constraint, because it is implicit in that family of solutions.

Answer 3

[Matt J]

If, as @Torsten mentioned, you are in the situation where the equality constraints only depend on the continuous variables, then you may be able to work around ga's restrictions as below.

Here, I've assumed, without loss of generality, that the x(i) are ordered so that x=[y,z] where y is a C-length vector of continuous variables, and z is a length-I vector of integer variables.Thus, the nonlinear equalities ceq(y) are functions of y only.

intcon=C+1:C+I;

fun=@(z) outerFunction(z, A,b,Aeq,beq,lb,ub,intcon);

%% Outer optimization over integer variables z only - no equality constraints
z = ga(fun,I,[],[],[],[],lb(intcon),ub(intcon),[], 1:I ) 

[~,y]=fun(z); %Obtain optimal y

x=[y,z]; %Final solution


function [fval, y] = outerFunction(z, A,b,Aeq,beq,lb,ub, intcon)
%This wrapper function determines the fitness value fval by having ga()
%minimize the original fitness function f() over continuous variables y only. In this
%optimization sub-problem, the input integer variables z are fixed parameters.
%
%Because the optimization iterates over continuous variables only, we are
%free to impose equality constraints.

   C=numel(lb)-numel(intcon);   
   
   continuous=1:C;

   % Inner optimization os over 
   
   fitness=@(y) f([y,z]);
   
   Aeq=Aeq(:,continuous); beq=beq-Aeq(:,intcon)*z;
   
   A=A(:,continuous); b=b-A(:,intcon)*z;
   
   lb=lb(continuous); ub=ub(continuous);
   
   nonlcon=@(z) deal( c([y,z]), ceq(y) );
 
   [y,fval,exitflag] = ga(fitness,C,A,b,Aeq,beq,lb,ub,nonlcon); 

   %return fitness value
   fval=fval + 1/(exitflag>0);
   
end

[Matt J]

Note, for clarity, the code above is not written to be efficient. In optimized code, you would pre-compute submatrices like Aeq(:,continuous), Aeq(:,intcon), etc... rather than rebuild them in every iteration.

Also, the code has not been written to support ga's UseVector option in the outer optimization. You could use it in the inner optimization,

   %solve inner optimization - no integer constraints
   [y,fval,exitflag] = ga(fitness,C,A,b,Aeq,beq,lb,ub,nonlcon);

if f() is appropriately coded.