Listing possible combinations of integers, given constraints (Gear Ratio Related)

The problem:

Let Gear Ratio = ( 1 + N3/N1 )/( 1 - ( ( N3*N4 )/( N5*N2) ) ), where N1, N2, ..., N5 must be integers. I'm looking to list combinations of N1, N2, ..., N5 that make the gear ratio fall within a specified range (i.e. 50 - 60), with upper limits to what the values of N1, N2, ..., N5 can be (i.e. 150).

I've done it using a for loop then and listing / filtering values that are within the given constraints, but am looking for a more efficient solution given that the for loop takes forever to finish.

I looked into using ndgrid from the following example: https://www.mathworks.com/matlabcentral/answers/308775-integer-division-problem-gear-ratio-related

But the arrays created would be much too large.

Any ideas / hints would be appreciated!

[Walter Roberson]

How does the equation distinguish between N2 and N5? Exchanging them does not change anything. You could create

[p, q] = ndgrid(1:150);
N25 = unique(p.*q);

And use N25 in calculation of the basic ratios, later substituting all N2 N5 pairs that multiply to that particular value.

[Terence Ng]

Based on the equation, you're correct that N2 and N5 can be combined and substituted afterwards.

As Aquatris mentioned below, assuming I went with a "brute force" method I'd still be 4 for loops deep.

More than likely I'll revisit the problem and apply more constraints to reduce the number of solution sets.

Answer 1

[Aquatris]

One possibility is using an optimization. Here is a simple code for it using OPTI toolbox;

clear all,clc
% round() is used to enforce integer value
gr = @(N) (1+round(N(3))/round(N(1)))/(1- round(N(3))*round(N(4))/round(N(5))/round(N(2))));
% initial guess
x0 = [1 2 3 7 11]';
% lower and upper bounds for N = [N1 N2 N3 N4 N5]'
lb = zeros(5,1);
ub = ones(5,1)*150;
% Nonlinear Constraints for desired gear ratio range(cl <= nlcon(x) <= cu)
nlcon = @(x) gr(x);
cl = [50]; 
cu = [90]; % upper is chosen 90 cause initial guess give 88
% formulate the problem in OPTI toolbox
Opt = opti('fun',gr,'bounds',lb,ub,'x0',x0,'nl',nlcon,cl,cu)
[x,fval,exitflag,info] = solve(Opt); % this will try to minimize the
                                     %   gr function and since the lower 
                                     %   limit is defined as 50, it will  
                                     %   give a gear ratio close to 50
                                     %   if optimization is succesful
N_solution = round(x)       % the necessary [N1 N2 N3 N4 N5]' = [2 2 3 7 11]'
gear_ratio = gr(N_solution) % achieved gear ratio = 55

The problem can be formulated in a similar manner for built-in Matlab function as well.

[Terence Ng]

Thank you for the input.

This is similar to what I had originally started out with (with the exception that I was using fmincon). The issue I had with formatting the problem as an optimization problem was that it would solve for a single solution when I was looking for the entire solution set, given that the problem has multiple solutions.

I found a page regarding multiple solutions for a global optimization problem https://www.mathworks.com/help/gads/multiple-solutions.html, that might be interesting to look into (though I don't have access to that toolbox).

I'll have to give it some more thought...

[Aquatris]

An alternative method would be a brute-force search as;

sol = [];
for n1 = 1:150
    for n2 = 1:150
        for n3 = 1:150
            for n4 = 1:150
                for n5 = 1:150
                    e = gr([n1 n2 n3 n4 n5]);
                    if(e < 60 & e > 50)
                        sol = [sol;n1 n2 n3 n4 n5];
                    end
                end
            end
        end
    end
end

where gr is the function from the answer I gave and each row of sol variable is a combination that would achieve desired gear ratio.

I ran the above code for 240 sec. and terminated it. It did not even reach n1 = 2 (it was at n1=1,n2=13,n3=21,n4=47,n5=134) but was able to find 150k possible combinations. So I do not think it is feasible to find all the combinations of n1 n2 n3 n4 n5 that give the desired gear ratio for your problem since I think there are billions of possible combinations.

[Terence Ng]

This is currently the method I have. (I also gave up way before n1 was able to iterate once)

I agree with your statement that it doesn't seem feasible to find all the combinations, likely I'll have to apply more constraints to reduce the number of possible solutions.