4
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ @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? $\endgroup$ – D.W. Oct 6 '17 at 6:36
  • $\begingroup$ @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! $\endgroup$ – Dandelion Oct 6 '17 at 6:40
  • 1
    $\begingroup$ @D.W. Some reals can be expressed using roots, logarithms, etc. $\endgroup$ – rus9384 Oct 6 '17 at 7:22
  • 4
    $\begingroup$ @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. $\endgroup$ – David Richerby Oct 6 '17 at 11:20
  • 1
    $\begingroup$ @DavidRicherby, but that already is extension of just quotient numbers, so, the answer would be that it is done for simplification? $\endgroup$ – rus9384 Oct 6 '17 at 11:40
3
$\begingroup$

In order to consider the computational complexity of linear programming, we need a way of encoding an instance of linear programming as a string. In particular, we need to fix an encoding of the coefficients, noting that arbitrary real coefficients cannot be encoded in a finite manner. The simplest and most canonical possibility is to ask for all coefficients to be integers or, equivalently, rational. In practice this encoding is usually good enough, so there is no reason to look any further. In principle, however, it is perfectly possible to consider more complicated coefficients. Indeed, any field which supports efficient linear algebra would do.

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.

Later on you might learn about semidefinite programs (SDPs). In the case of SDPs, we are no longer guaranteed that there exist an optimal solution over the rationals, but there is always an algebraic solution with bounded algebraic degree over the rationals. This fine point has recently been a cause for worry, see Ryan O'Donnell's SOS is not obviously automatizable, even approximately.

$\endgroup$
  • $\begingroup$ could you please explain why a basic feasible solution is polynomially bounded? Or point to a paper/book to read about it? $\endgroup$ – Elena Feb 4 at 14:34
  • $\begingroup$ It’s the solution of a linear system whose coefficients come from the linear program. $\endgroup$ – Yuval Filmus Feb 4 at 14:53
  • $\begingroup$ OK, I got it from these notes cs.cmu.edu/afs/cs/user/glmiller/public/Scientific-Computing/…. In summary, it is because the number of times we need to multiple the existing coefficients is bounded by the input size, and we represents numbers in binary, right? $\endgroup$ – Elena Feb 4 at 15:11
  • $\begingroup$ We actually have to compute a big determinant, so it’s a bit more subtle. $\endgroup$ – Yuval Filmus Feb 4 at 15:13
  • $\begingroup$ Can I then formulate it like this: each dimension of a basic solution is at most exponentially large in the size of the input, but since we represent numbers in binary, the size of solutions is polynomial in the size of the input (which is coded in unary)? $\endgroup$ – Elena Feb 4 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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