5
$\begingroup$

I have the following problem: \begin{align}\max&\quad c^T x\\\text{s.t.}&\quad Ax=b\\&\quad x\ge0\end{align}

The matrix $A$ is $m\times n$, where $m<n$.

I have an optimal solution $x^*$ in which all variables are non-zero. I know that there must exist another optimal solution $x^{**}$, a "basic feasible solution", in which at most $m$ variables are non-zero.

Given $x^*$, is there an algorithm for finding $x^{**}$ using polynomially-many arithmetic operations? (I know that $x^{**}$ can be found using the Simplex method, but I am looking for a polynomial-time algorithm).

Improve this question
$\endgroup$
2
  • $\begingroup$ See scholar.google.com/… $\endgroup$
    – ErlingMOSEK
    Nov 1, 2021 at 16:33
  • $\begingroup$ @ErlingMOSEK I saw this paper before, but so far I did not manage to understand the algorithm. $\endgroup$
    – Erel Segal-Halevi
    Nov 1, 2021 at 17:50

2 Answers 2

Reset to default
5
$\begingroup$

Since the constraints are equations, solve the linear system $$ \left[\begin{array}{c} A\\ c^{\prime} \end{array}\right]y=0 $$for any nonzero solution $y$. You can look for an eigenvector with nonzero eigenvalue, or just tack on the equation $r^\prime y = 1$ for some vector $r$ randomly generated from a continuous distribution (e.g., all components uniform over $[0,1]$). Solving a linear system should be polynomial time. Now look for the largest scalar $t$ such that $x^* + t y\ge 0$ (and, if that is unbounded, repeat using $-y$ in place of $y$). Replace $x*$ with $x^* + ty$ for that value of $t$, drop the variable $x_i$ which just became 0 from the problem, and repeat until you are at a corner point (BFS).

Improve this answer
$\endgroup$
8
  • $\begingroup$ What is $c'$ - is it the same as $c$? $\endgroup$
    – Erel Segal-Halevi
    Nov 1, 2021 at 16:50
  • 1
    $\begingroup$ I guess it's $c$ transposed. $\endgroup$
    – worldsmithhelper
    Nov 1, 2021 at 18:05
  • $\begingroup$ Yes, it is $c$ as a row vector. $\endgroup$
    – prubin ♦
    Nov 1, 2021 at 18:13
  • $\begingroup$ Ah, I see. So $A y=0$ and $c'y=0$. So, for any scalar $t$, $A(x^*+ty)=Ax^*+tAy=b+0 = b$ and $c'(x^*+ty)=c'x^*+tc'y=c'x^*$, so $x^*+ty$ is still a feasible and optimal solution to the original problem. But why is it certain that some variable $x_i$ will become 0? 2nd question: when repeating the process, how do I prevent $x_i$ from becoming nonzero again - should I add an explcit constraint $x_i=0$? $\endgroup$
    – Erel Segal-Halevi
    Nov 2, 2021 at 6:25
  • $\begingroup$ First question: since $y\neq 0$, either the $+y$ or $-y$ direction must contain at least one negative component. If that component has index $i$, then $x_i$ is decreasing and, if you go far enough, must reach 0. The only thing preventing you from going that far would be some other component going to 0 first. $\endgroup$
    – prubin ♦
    Nov 2, 2021 at 15:20
5
$\begingroup$

You can find a basic solution such that

$$ c^T x^{**} \leq c^T x^{*} $$

using at most n-m simplex pivots. That is strongly polynomial time.

Any decent recent text book about the simplex method should teach you that. You may also be able to figure it out based on description of the primal simplex method in my note. (You just try to pivot each nonzero nonbasic variable in the basis. It is decreased if the reduced cost is negative otherwise it is increased.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Maybe you mean to add the following constraint to the original problem: $c^T x = c^T x^{*}$, and then just find a basic feasible solution (regardless of the optimization)? $\endgroup$
    – Erel Segal-Halevi
    Nov 2, 2021 at 6:43
  • $\begingroup$ Fixed some typos. The algorithm find a solution that is at least as good as the initial solution in terms of the objective value. $\endgroup$
    – ErlingMOSEK
    Nov 2, 2021 at 7:59
  • $\begingroup$ OK, but there is now an additional constraint. So the number of nonzeros in a BFS of the new system might be $m+1$? $\endgroup$
    – Erel Segal-Halevi
    Nov 2, 2021 at 8:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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