4
$\begingroup$

I have a linear programming problem. I want to know if this LP is feasible. What is the best known algorithm for checking feasibility of an LP or a linear system of equations?

$\endgroup$
8
$\begingroup$

Checking feasibility of an LP and solving an LP are essentially equivalent problems, as one can be transformed into the other by standard methods changing the complexity by a constant factor only.

The best-known algorithms are the simplex method and interior point methods. For both, there are numerous variations. Which of the two approaches is most useful depends on the size and sparsity pattern of the matrix defining the LP.

$\endgroup$
2
$\begingroup$

In general it is Phase I of the simplex method.

If you are using a black-box solver, remove the objective function or set all the coefficients to zero in it (same effect as removing the objective) then call the LP solver. The solver will stop after finding the first feasible solution or it will conclude that the problem is infeasible.

The wording "the best known algorithm" is a little unfortunate. Unless you specify the context, it is impossible to give you an accurate, general answer. Well, I've tried...

$\endgroup$

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.