Rational LP to integer LP

Question

In the worst case complexity analysis of all the polynomial algorithms in linear programming such as ellipsoid method and interior point method, there is an assumption that the input data must be integer. Using this assumption, then they bound the bitlength of input data by $L$. Now, the question is as follows:

Q: How can this assumption be met for a linear programming with rational data. In other words, does there exist a way to convert the LP with rational data to an integer one? To me, it seems as though there is a way since data integrality is an assumption for these algorithms.

Answer 1

Why not multiply the data (i.e., the matrix $A$ and vector $b$ in the constraint $Ax \ge b$ and the vector $c$ in the objective function $c^Tx$) by the greatest common denominator of all entries? If you do so, you end up with a problem that has only integer constraints. Of course, you could do that for each individual constraint separately if you want to use smaller multipliers.

If all you want to do is estimate the bit size you need, then the bits you need to represent a fraction $\alpha/\beta$ in a matrix or vector entry is simply $bits(\alpha/\beta)=bits(\alpha)+bits(\beta^*)$ where $\beta^*\ge \beta$ is the smallest common multiplier, and this yields the same complexity bound for the linear program if you adjust the bit count for rational numbers. Of course, this yields the very same bound as you get if you just scale the entire problem by the largest common denominator $\beta^*$.