Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Is this an integer programming problem?

  1. Feb 22, 2016 #1
    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. jcsd
  3. Feb 23, 2016 #2

    Mentallic

    User Avatar
    Homework Helper

    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.
     
  4. Feb 23, 2016 #3
    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.
     
  5. Feb 23, 2016 #4

    Mentallic

    User Avatar
    Homework Helper

    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]
     
  6. Feb 23, 2016 #5

    jbriggs444

    User Avatar
    Science Advisor

    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.
     
  7. Feb 23, 2016 #6

    fresh_42

    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.
     
  8. Feb 23, 2016 #7

    jbriggs444

    User Avatar
    Science Advisor

    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.
     
  9. Feb 23, 2016 #8

    Merlin3189

    User Avatar
    Gold Member

    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?
     
  10. Feb 23, 2016 #9

    jbriggs444

    User Avatar
    Science Advisor

    ##\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
  11. Feb 23, 2016 #10
    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




Similar Discussions: Is this an integer programming problem?
Loading...