Reducing linear programming to positive linear programming

Suppose we have an oracle that solves problems of the form

\begin{align*}
\text{maximize} ~~ & c^T x
\\
\text{subject to} ~~ & A x = b, x\geq 0
\end{align*}

when $c\geq 0$ (all coefficients in the maximization target are non-negative).

Can it be used to efficiently solve general linear programs?

FAILED ATTEMPT #1: replace each variable $x_i$ that appears with a negative coefficient in $c^T x$, with another variable $y_i := - x_i$.
Unfortunately, this $y_i$ does not satisfy the non-negativity constraint.

FAILED ATTEMPT #2: Ensure that all elements in $b$ are non-positive (multiplying the equation by -1 if necessary). Then create the dual LP:

\begin{align*}
\text{maximize} ~~ & - b^T y
\\
\text{subject to} ~~ & A^T y \geq c
\end{align*}

Here, all the coefficients in the objective are non-negative. However, this form does not match the form that the oracle can solve, since the constraints are not equational constraints and the variables $y$ are unbounded.

You can add a variable $y$ and a linear equality $y=c^Tx+c_0$ for some $c_0$. Then, the original problem is equivalent to maximizing $y$ in the new system.

Except for the condition $y\geq 0$. That is where $c_0$ comes in. We need to make $c_0$ large enough that for some feasible $x$ (that is $Ax=b$ and $x\geq 0$ hold) we have $c^Tx+c_0\geq 0$. In that case it does not matter that non-negativity cuts away parts of the feasible space. The optimal value is still the same.

So how to choose $c_0$? I am not an expert in linear optimization. Is finding some feasible $x_0$ easier than finding one that maximizes the objective function? If so, we can take $c_0$ to be $-c^Tx_0$.

If the given coefficients are rationals, there is another way.
First, let us establish that the polytope of feasible $x$ has vertices (unless it is empty):
Let $p$ be a point in a minimum-dimensional boundary cell of said polytope.
For contradiction, assume that the dimension of this cell is $\geq 1$.
Then, there is a different point $q$ in the same cell. As the cell has minimum dimension, it is unbounded, so points of the form $r=p+t(q-p)$ are in the same cell and thus in the polytope. As $q-p\not=0$, some such $r$ have negative coordinates, contradicting the polytope condition $r\geq 0$.

Now, make all coefficients of $A$ and $b$ integer by multiplying with the common denominator. Let $n$ be the dimension (the length of the vector $c$) and let $M$ be the maximum absolute value of any coefficient of $A$, $b$, or $c$. Then we can bound the coordinates of any vertex of the feasible polytope by $n!\cdot M^n$. Thus, choose $c_0:=n\cdot n!\cdot M^{n+1}$.

[EDIT]

Yet another approach, in case you are willing to call the oracle multiple times: First, try the above with $c_0=0$. If you get a solution or the answer "unbounded", you are fine. If the answer is "unsolvable", you need to find out if there are solutions with negative objective function. Hence, set $z=-c^T$ and maximize $z$ instead. If you get a solution, you can use it as $x_0$. If you get "unsolvable" again, you are done as well. The last case is the answer "unbounded". Then, you need to try out ever larger $c_0$ (for few oracle calls, use a fast-growing function; the Ackermann function may do) until you get a solution.

StackExchange Computer Science Q#102284, answer score: 5