Optimization problem : Find value of variables such that error is mimimum

Question

There are 3 variables x,y,z . x can have the integer values from 1-65535 , y can have integer values from 1-3 and z can have integer values from 0-2047.
The equation is
$$F = 13000000/((32x)*(y+(z/2048)))$$
F can take the values such as 4800 , 9600 . But as x,y and z are integers , we will not get the value of F exactly equal to 4800 or 9600 . The problem is to find integers x,y,z such the error in F is < 0.01% .
How to approach such kind of problems?

score 0 · Answer 1 · answered Apr 07 '14 at 21:12

The solution depends on the type of arithmetic you are assuming.

The following C# code performs a brute-force search:

  for (uint x = 1; x <= 65535; x++)
     for (uint y = 1; y <= 3; y++)
        for (uint z = 0; z <= 2047; z++ )
           for (uint F = 4800; F <= 9600; F += 4800)
              {
                double G = 13000000.0 / ((32.0 * x) * (y + (z / 2048.0)));
                double err = F - G;

                if (Math.Abs(err) < F * 0.01/100)
                  {
                    ...
                  }

It is using "double" arithmetic and results in 64 solutions. For pure integer arithmetic, the exhaustive search does not find any solutions.

Example solution:

x 82
y 1
z 66
F 4800
error 0.40612

In principle, you could use solvers like MiniZinc or Z3 for such problems. But you have to take care about the bit-length of the operands. MiniZinc is restricted to 32 bits which would be too short for the problem at hand.

Optimization problem : Find value of variables such that error is mimimum

1 Answers1