Solve as Optimization Problem in Matlab

I want to solve this simple equation as an optimization problem in Matlab. I have tried linprog, fmincon and fminunc and all do not seem to get it done. It is trivial to solve with brute-force in a loop (as below) and with Excel's Solver, but I want to be able to use one of Matlab's optimization routines too.

Solve:

15*i + 16*j + 17*k = 121

i, j and k are integers.

With loops, the solution is trivial:

for i = 0:100
    for j = 0:100
        for k = 0:100
            val = 15*i + 16*j + 17*k;
            if val == 121
                disp('here!')
                i,j,k
            end
        end
    end
end

The solution is i=7, j=1, k=0.

I want to solve as:

min 121 - 15*i - 16*j - 17*k

s.t. i,j,k are >=0 integers.

What is the appropriate formulation as a optimization problem in Matlab?

Thanks!

Answer 1

[Ameer Hamza]

MATLAB have genetic algorithm ga() from the global optimization toolbox to solve such problems

f = @(x) 121 - 15*x(1) - 16*x(2) - 17*x(3);
sol = ga(@(x) f(x).^2, 3, [], [], [], [], [0 0 0], [], [], 1:3);

Result

>> sol
sol =
     7     1     0

Of course, the problem has an infinite number of solutions. This is one of them

[Paul Safier]

There is the constraint that the solution is greater than or equal to 0.

[Ameer Hamza]

I missed that part before. See the updated answer.

[Paul Safier]

Thanks, I was able to implement ga as you suggest but with the lb added as,

sol = ga(@(x) f(x).^2, 3, [], [], [], [], [0,0,0], [], [], 1:3)

Now I get the correct solution. Thanks.

I must say though, that it seems this problem is so simple, that I find it hard to believe the it cannot be solved with simpler, easier and linear Matlab optimization routines... Why wouldn't linprog work??

[Ameer Hamza]

Although Bruno already posted a solution using intlinprog(), I too realized that it can be done as integer linear programming problem.

f = [121 -15 -16 -17];
sol = intlinprog(f, 1:4, -f, 0, [1 0 0 0], 1, [0 0 0 0], []);

I = sol(2);
J = sol(3);
K = sol(4);

[John D'Errico]

It is NOT a nonlinear problem at all.

[John D'Errico]

You asked why linprog would not work. The answer is trivial - linprog does NOT offer integer programming. It cannot constrain the solutions to be integer.

Intlinprog and ga work, because they have the necessary integer contraints.

[Paul Safier]

Thanks.

[Ameer Hamza]

@John, I later realized my mistake of calling it a nonlinear problem. intlinprog() can also be used.

Answer 2

[Bruno Luong]

c=[15 16 17];
t = 121;

A = [ c -1;
     -c -1];
b = [ t;
     -t];
f = [zeros(length(c),1); 1];
LB = 0*f;
x = intlinprog(f, 1:size(f), A, b, [], [], LB, []);
x = round(x);
i = x(1)
j = x(2)
k = x(3)

[Paul Safier]

This works as well! Thanks Bruno Luong!!

Answer 3

[Jon]

I think you can use the MILP mixed integer linear programming functionality if you have the optimization toolbox

https://www.mathworks.com/discovery/integer-programming.html

Answer 4

[John D'Errico]

In MATLAB, the solution is intlinprog. Of course, there may be multiple solutions. intlinprog does not give them, if any could exist. But there is no need for loops either, nor even to go out as far as 100.

Since we know

8*15
ans =
   120

then we can limit the variables to be no larger than 8.

[x,y,z] = ndgrid(0:8,0:8,0:8);
ind = find(15*x + 16*y + 17*z == 121)

ind =
    17

>> x(17)
ans =
     7
     
>> y(17)
ans =
     1
     
>> z(17)
ans =
     0

So the only possible solution in positive integers is as found. Fast, efficient, and trivial to write. Sometimes brute force is the easiest thing. Would I have used intlinprog? Of course, as that is the obvious way to solve any problem of this class.

Had the problem been larger, perhaps to find a solution in integers to this?

137*x + 291*y + 313*z + 997*u + 1329*v + 237*w == 1 + 1e15

Now brute force will fail, because the search will push the search space out into numbers on the order of 1e13. And of course, even intlinprog might be at risk, due to the size of the right hand side, compared to the dynamic range of a double. This latter problem can now be solved more easily using number theory. How? Consider this...

(writing)

[Bruno Luong]

Actually for (c1, ... ck) we all know for integers (n1,...,nk)

c1*n1 + ... + ck*nk

generate the set pZ

where p is gcd of { c1, ... ck }.

So we can just serach pZ the closest to the value to be approximate, then using euclide's division algorithm to find the solution, and even he formula for ALL solutions.

You can approximate as close as you like any number x by

x ~ n + m*pi for n, m integers (sine 1 and pi does not have gcd > 0, they are relatively "prime").

[John D'Errico]

:) Too fast for me to write, is Bruno. The point being, you use number theoretic concepts to solve larger problems that might be otherwise to large for brute force. This will also provide an avenue to solving the problem in general, when more than one solution exists.

[Paul Safier]

Good discussion @John and @Bruno. Thanks!

The number theory approach to a problem of this type is new to me. I'd like to learn a bit more and maybe do it. I'm not sure I can get enough key words from what's written here to properly Google more info. Would either of you guys be able to lead me to an article or worked example?

[Bruno Luong]

I remember I wrote some code based on GCD 12 years ago, and one can find here thank to mother Google.

This code list ALL positive integer solutions of the equation.

The (almost) same code are attached for reference.

[Paul Safier]

Thanks!