HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Linear programming restricted to rational coefficients

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
linearprogrammingcoefficientsrationalrestricted

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#82086, answer score: 4

Revisions (0)

No revisions yet.