How can I convert equality constraints into inequality constraints?

I m solving a problem using ga with equality and inequality constraints and want to optimise it while using binary variables. But do not solve it with equality constraints.

Answer 1

[Matt J]

See these threads

https://www.mathworks.com/matlabcentral/answers/167216-genetic-algorithm-ga-with-integer-equality-and-inequality-constraint

https://www.mathworks.com/matlabcentral/answers/104739-integer-constrained-optimization-using-the-ga-genetic-algorithm-solver-of-matlab-can-anyone-he#answer_114013

[John]

I read both threads but it is difficult to understand them. If you have any code example then share it.

Thanks.

[Matt J]

As a simple 2-variable example, suppose your problem is

min 3*x1+2*x2

subject to

    x1+x2=5;
     x2>=0
     x1>=1

The equality constraint implies x2=5-x1 so you can eliminate x2 and reduce the above to a lower dimensional problem with inequality constraints only:

min. 3*x1+2*(5-x1)

subject to

   5-x1>=0
     x1>=1

The links I provided talk about how to do this in higher dimensions, but basically you reorder your variables so that your equality constraint matrix partitions as Aeq=[P,Q] where Q is an NxN invertible matrix. The equality constraints then become,

beq =  Aeq*x  = P*x1 + Q*x2

and you can eliminate the variables associated with Q according to x2=inv(Q)*(beq-P*x1).

[John]

Thank Matt J.

But what is the P here and should we eliminate Q at end? If we convert all equality constraints into inequality constraints by this way then may be we get infeasible solution.

[Matt J]

But what is the P here and should we eliminate Q at end?

Q is not an unknown variable. It is an NxN invertible matrix formed from linearly independent columns of Aeq. You can identify these columns using licols.m attached. P is a matrix formed from the remaining columns.

If we convert all equality constraints into inequality constraints by this way then may be we get infeasible solution.

I don't see why you would. The reduced problem should be equivalent to the original.

Answer 2

[Alan Weiss]

Did you see the documentation dealing with equality constraints for mixed-integer optimization using ga?

Alan Weiss

MATLAB mathematical toolbox documentation

[John]

Yes I read it and also some other threads. But by converting equality constraints into inequality constraints they will cancel each other and we will get infeasible solution.