Is this an integer programming problem?

  • Thread starter rumborak
  • Start date
  • #1
706
154
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.
 

Answers and Replies

  • #2
Mentallic
Homework Helper
3,798
94
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.
 
  • Like
Likes rumborak
  • #3
706
154
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
Mentallic
Homework Helper
3,798
94
For more complicated decimals, to "integeralize" it, you just need to convert it into a fraction and multiply by the denominator.

[tex]1.73853467=\frac{173853467}{100000000}[/tex]

and hence

[tex]1.73853467\times 100000000=173853467[/tex]
 
  • #5
jbriggs444
Science Advisor
Homework Helper
10,361
4,956
So, the 'a's should be considered real numbers, e.g. 1.7853467 etc.
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.
 
  • Like
Likes rumborak
  • #6
15,718
13,975
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.
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
jbriggs444
Science Advisor
Homework Helper
10,361
4,956
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.
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.
 
  • Like
Likes fresh_42
  • #8
Merlin3189
Homework Helper
Gold Member
1,668
777
Now you've soled the op, can I just ask a little BTW?
If any pair of a's has a ratio that is irrational ....
Is that the same as saying, if any a is irrational?
Or is there some other way of getting an irrational ratio?
 
  • #9
jbriggs444
Science Advisor
Homework Helper
10,361
4,956
Is that the same as saying, if any a is irrational?
Or is there some other way of getting an irrational ratio?
##\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:
  • #10
706
154
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.
 

Related Threads on Is this an integer programming problem?

Replies
3
Views
579
A
Replies
1
Views
2K
Replies
10
Views
1K
Replies
17
Views
11K
  • Last Post
Replies
5
Views
2K
Replies
8
Views
984
  • Last Post
Replies
7
Views
15K
  • Last Post
Replies
2
Views
6K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
4
Views
2K
Top