Rational LP, its Rational solution and a minimum precision

Question

Suppose we have an LP with rational coefficients.

To my knowledge, this implies that the optimal solution to that LP is also rational. In other words, every variable may be written as:

$$x_{i}^{\star} = M_{i}/N_{i}$$

Moreover, I can scale numerator/denumerator such that all variables share the same denumerator:

$$x_{i}^{\star} = \frac{M_{i}^{\prime}} {N_{common}}$$

Is it possible to find a common denumerator $N_{common}$ before solving the LP? This would convert the optimization problem to a problem which must have an integer solution (optimizing over variables $M_{i}$.

Another interpretation of my question: Is it possible to solve any LP by having each variable take values which are multiples of $1/N_{common}$, with the latter having the notion of the required "precision" to avoid losses?

Answer 1

Finding $N_{common}$ seems equivalent to finding a column scaling such that the optimal solution is integer-valued. Surely, if you want to do this without knowledge of the optimal solution, you are looking for a column scaling to that turns your rational polyhedron into an integer polyhedron where all vertices are integer-valued. The direct approach, visiting all vertices of the polyhedron, has exponential complexity. Moreover, the encoding length of a column scaling turning all vertices integer-valued, might also be exponential in the enconding length of input data.

From a practical standpoint, you are much better of with exact rational arithmetic. See, e.g., Exact solutions to linear programming problems from 2007 by Applegate, Cook, Dash and Espinoza.