1

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

Matthias C. M. Troffaes
  • 455
  • well, the next canonic candidate is the interior point method. – user251257 Jul 29 '15 at 09:37
  • 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. – Matthias C. M. Troffaes Jul 29 '15 at 10:44
  • there are infeasible methods, like one from Mehotra. however, it might be difficult to see if it's really unbound or just rounding error ... – user251257 Jul 29 '15 at 10:48
  • btw is $A$ fat or skinny? full rank? – user251257 Jul 29 '15 at 10:49
  • 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. – Matthias C. M. Troffaes Jul 29 '15 at 11:00
  • Most vanilla interior point methods need a full rank matrix. unboundness is "detected" by unreasonably large iterates :D – user251257 Jul 29 '15 at 11:12
  • Ok, thanks for this insight. Actually for this particular problem, as soon as there is a negative solution, we know that the solution is unbounded (because you can scale any solution x arbitrarily with a positive constant), so it may be possible to stop the algorithm much faster. – Matthias C. M. Troffaes Jul 29 '15 at 12:06
  • Why not just add $c^Tx \geq -1$ as a constraint? Now you know the solution is either $0$ or $-1$. If it's the latter, the original problem is unbounded. – Michael Grant Aug 03 '15 at 21:14
  • Thanks for suggesting. It will not help the simplex algorithm though: you'll have minimum ratio on all degenerate constraints and consequently you will never pivot on this row. It may help with convergence on the interior point method (but as noted in the comment above you could stop already as soon as it finds some negative solution). Nevertheless, my feeling is that in the fully degenerate case, there might be some clever way to exploit this fact, for instance through specific pivot rules that do not look at the ratio but look at the entries themselves instead, or some other clever trick. – Matthias C. M. Troffaes Aug 04 '15 at 07:55

1 Answers1

2

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.

Willem Hagemann
  • 618
  • 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. – Matthias C. M. Troffaes Aug 05 '15 at 16:06