1
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ "the optimal solution" assumes uniqueness, but many LPs have nonunique optimal solutions and when this happens there are also irrational optimal solutions. $\endgroup$ May 8 at 15:08

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Nice reference!! $\endgroup$ May 8 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.