1
$\begingroup$

I am looking for efficient computational methods for solving a class of linear programs whose right hand side is zero:

$$ \min c^T x \qquad\text{ subject to }\qquad Ax\ge 0 $$

What is the best general purpose algorithm for solving such linear program?

Note 1: $x=0$ is always a basic feasible solution, and moreover, it is the only basic feasible solution. Consequently, the solution to this linear program is either zero or unbounded, and I'm interested in deciding which is the case.

Note 2: The standard simplex algorithm with the minimum ratio rule does not provide a good way of selecting a pivot row because all ratios are zero, so any row is admissible for pivoting (provided the entry is positive).

$\endgroup$
9
  • $\begingroup$ well, the next canonic candidate is the interior point method. $\endgroup$ – user251257 Jul 29 '15 at 9:37
  • $\begingroup$ If the primal is unbounded, then the dual is infeasible so has no interior. Therefore, at least from an intuitive point of view, it is not clear that interior point methods are a good natural candidate for solving this sort of problem as those methods try to move along feasible primal/dual pairs. $\endgroup$ – Matthias C. M. Troffaes Jul 29 '15 at 10:44
  • $\begingroup$ there are infeasible methods, like one from Mehotra. however, it might be difficult to see if it's really unbound or just rounding error ... $\endgroup$ – user251257 Jul 29 '15 at 10:48
  • $\begingroup$ btw is $A$ fat or skinny? full rank? $\endgroup$ – user251257 Jul 29 '15 at 10:49
  • $\begingroup$ Thanks. I'm aware of the infeasible methods (although not an expert by far), maybe they can or cannot easily tell unboundedness... in any case they do not seem to be specifically designed to detect it. On the second question, in the specific application I have in mind, in most cases we would have more constraints than variables, and $A$ may or may not have full rank but usually I'd expect it to have full rank. $\endgroup$ – Matthias C. M. Troffaes Jul 29 '15 at 11:00
2
$\begingroup$

Any general purpose algorithm which solves your specialized problem can also be used for feasibility checks of arbitrary systems of linear inequalities:

Let $A\mathbf{x} \leq \mathbf{a}$ be a system of linear inequalities. The feasibility of this system is equivalent to the feasibility of the system $A\mathbf{y} - \mathbf{a}\lambda \geq \mathbf{0}, -\lambda > 0$. ($\Rightarrow$: multiply with $\lambda < 0$, $\Leftarrow$: clearly $\lambda < 0$, set $\mathbf{x}=\frac{1}{\lambda}\mathbf{y}$). The latter system is feasible if and only if the linear program \begin{gather*} \mbox{minimize }\lambda \mbox{ s.t. } \begin{pmatrix}A &-\mathbf{a}\\&-1\end{pmatrix} \begin{pmatrix}\mathbf{y}\\\lambda\end{pmatrix}\geq\mathbf 0 \end{gather*} is unbounded. Now, the final system has exactly the specialized form as given in your question.

In summary, I'm afraid there will be no better method than the well-known linear programming algorithms.

$\endgroup$
1
  • $\begingroup$ Thanks sharing your insight that any algorithm for this problem also implies an algorithm for feasibility checks. In fact the converse holds as well: check feasibility of $Ax\ge 0$, $c^T x\le -1$. So the two problems are equivalent. I've marked this as an accepted answer. $\endgroup$ – Matthias C. M. Troffaes Aug 5 '15 at 16: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.