Skip to main content
Cleaned up the question, added a reference.
Source Link
Geoff Oxberry
  • 30.4k
  • 9
  • 65
  • 130

Combinatorial LP Why isn't every linear program combinatorial?

We call aA linear programmingprogram $Ax=b$(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$$A \in \mathbb{R}^{m \times n}$ is bounded by a polynomial of dimension of the LP problem. (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.

What I am thinking is thatIt seems as though any entry size is a polynomial of the LP dimension. In other words, sizesize($a_{ij}$) = size($a_{ij}$) * $m^0$ $n^0$ where size of LP is $m\times n$.

In my viewpoint So it seems like any LP is combinatorial. I must think wrongly but whyWhy isn't this statement true?

Combinatorial LP

We call a linear programming $Ax=b$ combinatorial if the size of entries of matrix $A$ is bounded by a polynomial of dimension of the LP problem. The size of a rational number is described as the length of its binary representation.

What I am thinking is that 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$.

In my viewpoint any LP is combinatorial. I must think wrongly but why?

Why isn't every linear program combinatorial?

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?

Source Link
Star
  • 585
  • 4
  • 13

Combinatorial LP

We call a linear programming $Ax=b$ combinatorial if the size of entries of matrix $A$ is bounded by a polynomial of dimension of the LP problem. The size of a rational number is described as the length of its binary representation.

What I am thinking is that 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$.

In my viewpoint any LP is combinatorial. I must think wrongly but why?