# Linear programming restricted to rational coefficients

I'm reading the appendix A of Williamson's "the design of approximation algorithms" about linear programming. In the definition of a linear programming it restricted the coefficients of cost function and conditions to be rational numbers. I guess that this restriction is because of time analysis consideration in terms of input length. Am I correct? Are there other reasons?

EDIT: And do we know that if there is a solution to the LP, then there is a rational solution to it?

EDIT 2: If the answer to the previous question is yes, is there a guarantee for the length of resulting rational numbers to be polynomially bounded as a function of input size?

• @rus9384, That's not true; integer coefficients doesn't make it NP-hard. You're getting it confused with integer linear programming. Dandelion, what alternative were you imagining? Real numbers? But real numbers can't be represented in a finite number of bits. We need some restriction so the numbers are representable; did you have something specific in mind? – D.W. Oct 6 '17 at 6:36
• @rus9384 Integer programming is about restricting solutions to be integers not coefficients. I wanted to know why it's not stated as real numbers. And as you noted I noticed that input length is probably the main reason. I just wanted to be sure about that! – Dandelion Oct 6 '17 at 6:40
• @D.W. Some reals can be expressed using roots, logarithms, etc. – rus9384 Oct 6 '17 at 7:22
• @rus9384 Sure, so one might restrict to the algebraic reals. Or their extension by some finite set of transcendentals. But the fundamental point remains: you need to be able to represent your numbers somehow, so you can only use countably many numbers. – David Richerby Oct 6 '17 at 11:20
• @DavidRicherby, but that already is extension of just quotient numbers, so, the answer would be that it is done for simplification? – rus9384 Oct 6 '17 at 11:40

A feasible linear program always has a basic feasible solution, which is obtained by taking $n$ linearly independent inequalities (where $n$ is the number of variables), and replacing them with equations. The solution of this linear system will always be rational, and furthermore will be polynomially bounded.