Reducing linear programming to positive linear programming

Question

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.

Answer 1

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.

Answer 2

You can replace a variable x that has no restriction to be positive with two variables $x^+ - x^-$ where both $x^+$ and $x^-$ are restricted to be positive. All their coefficients will be identical except that they have the opposite sign.

In the simplex algorithm, it is always possible to put only one of these into the basis. Actually, you can avoid any additional calculations by just keeping track whether any basis variable is currently positive or negative.