Algorithm: find two positive integers whose difference is minimized and whose product is known

Question

Some background...

I am currently building a macro that will estimate the cost of an injection molding tool. These tools have cavities which are filled with plastic. The number of cavities a tool has is the number of parts that will be formed.

So far my program will determine the minimum number of cavities a tool can have based on customer demand. This number is always even. The tool should have an even number of cavities. Given the bounding length and width of a cavity, and setting a limit to how much space the cavities can occupy within the tool, I need my program to calculate the combination of number of cavities along the length and width whose difference is minimized and whose product is equal to the total number of minimum cavities the tool should have.

I am programming my macro is SolidWorks VBA. I first constructed this problem in Excel and used the solver tool. But, I am unable to find a way to reference the Excel Solver Tool in SolidWorks to automate this optimization problem. I am hoping to find a clever set of equations that can solve this specific problem for me. But if someone else has a better idea of what to use, that would be awesome.

Rephrasing in an optimization format...

Variables

• x = number of cavities along width of tool
• y = number of cavities along length of tool
• z = suggested number of total cavities

Objective Function

Minimize x - y

Such that

• x * y = z
• x >= 1
• y >= 1
• x <= y
• x is an integer
• y is an integer

Example

My macro says that in order to meet demand, our tool needs to have at least 48 cavities. Find the number of cavities along the length and width of the tool such that the difference is minimized and the product is equal to 48. Ideally in this case the macro would return x = 6 and y = 8.

Thanks!

Answer 1

Just to clarify, in the question did you actually mean to Min y-x rather than Min x-y? Otherwise there is a naïve solution taking x = 1 and y = z. Min x - y = 1-z.

I don't program in VBA but here is the idea.

Since x and y are positive integers and there product is z, with x <= y. You can essentially start with x = floor(sqrt(z)) and decrement until x = 1.

For each x, check if there exists an integer y such that x * y = z. If there is, break the loop and that's the pair you are looking for. Otherwise continue until x = 1

If you need any pseudo code so you can translate it into VBA. Here it is

int x, y;
for (x = floor(sqrt(z)); x >= 1; --x)
{
    y = z / x;
    if (x * y == z)
        break;
}