# Is this an integer programming problem?

1. Feb 22, 2016

### rumborak

At work I am writing a somewhat complex piece of software, and inside it at some point I have to solve the following problem:

I have several "streams", each of which has equally spaced points according to a proportionality factor 'a', i.e. X=a*n. Each stream has a different 'a'.
As an example:
Stream 1, a = 1.5: X = 0, 1.5, 3, 4.5 etc
Stream 2, a = 1.0, X = 0, 1, 2, 3 etc
Stream 3 ....

The question to solve: is there a value X that is a valid point for all streams, other than the trivial 0?
This problem strikes me as integer programming, but I have no good idea how to go about it, short of brute force.

2. Feb 23, 2016

### Mentallic

To get a value of X that will be valid for all streams, you'll first need to multiply the value of 'a' in each stream by a sufficient integer such that the result is an integer if 'a' happens to not be an integer itself. Once you've done that for all streams, then multiply all the resulting values from each stream together. In your example, since a1 (a in stream 1) is 1.5, then multiplying that by 2 gives us 3, and since a2 is already an integer, we calculate that X=3*1=3 will be in both streams. Extending your example such that a3=7.25, then multiply that by 4 to give 29 and hence X=3*1*29=87 will be found in all streams.

3. Feb 23, 2016

### rumborak

Hmm, that's an interesting idea (and somehow it feels similar to Common Denominator calculation), but sadly my example used simple values for 'a' for illustrative purposes, not because they are actually constrained to it.
So, the 'a's should be considered real numbers, e.g. 1.7853467 etc. Maybe I'm not seeing it, but I don't think your method would work for those, as it seemed to rely on the easy "integerizability" of the a values.

4. Feb 23, 2016

### Mentallic

For more complicated decimals, to "integeralize" it, you just need to convert it into a fraction and multiply by the denominator.

$$1.73853467=\frac{173853467}{100000000}$$

and hence

$$1.73853467\times 100000000=173853467$$

5. Feb 23, 2016

### jbriggs444

If any pair of a's has a ratio that is irrational then there can be no non-zero integer multiple of one that can also be an integer multiple of the other.

6. Feb 23, 2016

### Staff: Mentor

Yes, but in programming you will always have finitely many digits. Irrationals cannot occur explicitly, so they will always look like those in post #4.

7. Feb 23, 2016

### jbriggs444

Agreed, but that just pushes the problem back. Any instance of the problem that can be successfully input into the computer using a's presented as finite decimal strings can be solved. But not every solvable instance of the problem can be input into the computer using finite decimal strings.

8. Feb 23, 2016

### Merlin3189

Now you've soled the op, can I just ask a little BTW?
Is that the same as saying, if any a is irrational?
Or is there some other way of getting an irrational ratio?

9. Feb 23, 2016

### jbriggs444

$\pi, \frac{\pi}{2} and \frac{3\pi}{7}$ are all in rational ratios with one another despite all being irrational.

But yes, if one were to trivially re-scale the problem so that $a_1 = 1$, "if any pair of a's has a ratio that is irrational" would be equivalent to saying "if any [rescaled] a is irrational".

Last edited: Feb 23, 2016
10. Feb 23, 2016

### rumborak

Thanks everybody. While (as it so often is) it didn't "solve" my programming problem, it definitely made me understand the problem space much better now.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook