Why isn't every linear program combinatorial?

Question

A linear program (LP)

\begin{alignat}{1} & \min_{x} {c}^{T}x, \\ \mathrm{s.t.} & \quad Ax = b, \\ & x \geq 0. \end{alignat}

is called combinatorial if the size of entries of matrix $A \in \mathbb{R}^{m \times n}$ is bounded by a polynomial of dimension of the LP. (See Eva Tardós, "A strongly polynomial algorithm to solve combinatorial linear programs", Operations Research (1985)) The size of a rational number is described as the length of its binary representation.

It seems as though any entry size is a polynomial of the LP dimension. In other words, size($a_{ij}$) = size($a_{ij}$) * $m^0$ $n^0$ where size of LP is $m\times n$. So it seems like any LP is combinatorial. Why isn't this statement true?

Answer 1

This is certainly true for any individual problem, but this sort of statement is typically made about a family of LPs. In that case, the dimensions of the matrix and the entries of the matrix are typically expressed in terms of other parameters $\theta = (\theta_1, \theta_2, \dotsc, \theta_k)$ for some $k \geq 1$ - i.e., we have $n(\theta)$ and $m(\theta)$. If the size of each $A_{ij}$ can be given as an expression (in $\theta$) that is bounded by a polynomial in the expressions $n(\theta)$ and $m(\theta)$, then we have a combinatorial LP.

Your argument is somewhat similar to saying, "Once I am given a graph on $n$ vertices, $n$ is a constant, so I can enumerate all $n!$ tours in constant time. Therefore I can solve the travelling salesman problem on that graph in polynomial time. But this holds for every graph. Hence P=LP."