I have a series of linear programs in canonical form

$$\begin{array}{ll} \text{maximize} & c^T \mathrm x\\ \text{subject to} & A x \leq b\\ & x \geq 0\end{array}$$

and I need to determine which ones are feasible as quickly as possible. However, I do not need to find solutions to the problems.

I am only vaguely familiar with linear programming techniques, but I have gathered that when using a method like the simplex algorithm, you need to solve a linear program in order to determine if it is feasible.

Michael Patriksson's answer to this post suggests using a Phase 1 type problem or a subgradient method. I have seen references to a two phase simplex method, where the first phase finds a feasible solution and the second phase finds the optimal solution, but I have not seen any solvers that allow you to only perform one phase of the operation (I am currently using the Mosek solver).

The subgradient method seems promising to me, but I am not sure how to implement it based on Michael's response alone. I would greatly appreciate some further explanation of this subgradient approach and/or a suggestion for a solver that allows you to just perform Phase 1 of the two phase method. If there are methods that parallelize well (on a gpu for instance) that would be helpful as well.

  • 2
    $\begingroup$ replace the objective with $0^Tx$, then phase 2 will return quickly; do make sure it runs simplex on the primal problem $\endgroup$ – LinAlg Mar 10 at 1:04

Your Answer

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

Browse other questions tagged or ask your own question.