During the solution of some computational problem, we have arrived at a linear program of the following form:
\begin{align*} \text{maximize} ~~ c x \\ \text{subject to} ~~ A x \leq b, x \geq 0 \end{align*}
where the number of variables in $x$ is exponential in the problem size, but the number of constraints is polynomial.
The most common technique we know for solving such problems is through its dual:
\begin{align*} \text{minimize} ~~ b y \\ \text{subject to} ~~ A^T y \geq c, y\geq 0 \end{align*}
The dual has an exponential number of constraints, but it is often possible to design a separation oracle - a function that decides, given a vector $y$, whether it satisfies all constraints, and if not - returns a violated constraint. The ellipsoid method can solve the dual using a polynomial number of calls to this oracle; then, the duality theorem can be used to find a solution to the primal LP. Sometimes, there exists an approximate separation oracle - given a vector $y$, it either finds a violated constraint or asserts that all constraints are satisfied approximately; then, using the ellipsoid method and the duality theorem, we can find an approximate solution to the primal LP.
In our case, we could not find a suitable exact or approximate separation oracle; we suspect that desigining such an oracle may be NP-hard. So our questions are:
Are there techniques for approximately solving the original LP directly in polynomial time, without going through the dual? Note that, if the original LP has $m$ constraints, it has an optimal solution in which at most $m$ variables are nonzero; as $m$ is polynomial in the problem size, the solution can be output in polynomial time.
Are there techniques for proving that solving the original LP, exactly or approximately, is NP-hard?
We will be happy to receive references to papers that use such techniques.
