7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You can try using the reduction from optimizing to feasibility (essentially binary search). $\endgroup$ – Yuval Filmus Jan 6 at 19:35
  • $\begingroup$ May I ask what is the motivation for this nonnegativity? $\endgroup$ – Apass.Jack Jan 6 at 20:17
  • 1
    $\begingroup$ @Apass.Jack I tried to prove hardness of some problem, and thought that a potential way is to reduce to it from linear programming. However, in my problem the coefficients are all positive. So I wanted to know if positive linear programming is as hard as the general problem. $\endgroup$ – Erel Segal-Halevi Jan 7 at 15:33
5
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sounds good. I think you do not even need the last part. In order to find a feasible solution, you can just solve a dummy problem such as "maximize 1 subject to $Ax = b, x\geq 0$". The answer should be 1 iff there is a feasible solution (not sure about that though). $\endgroup$ – Erel Segal-Halevi Jan 12 at 21:13
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I did not understand this answer. If you replace $x$ with two variables, then the coefficients in the maximization objective will be negative.. $\endgroup$ – Erel Segal-Halevi Jan 12 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.