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).

$\endgroup$
2
  • $\begingroup$ See scholar.google.com/… $\endgroup$ 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$ Nov 1, 2021 at 17:50

2 Answers 2

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).

$\endgroup$
8
  • $\begingroup$ What is $c'$ - is it the same as $c$? $\endgroup$ Nov 1, 2021 at 16:50
  • 1
    $\begingroup$ I guess it's $c$ transposed. $\endgroup$ 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$ 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.)

$\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$ 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$ 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$ 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.