LP feasibility checking

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

To add on to the answers of checking if a linear program is feasible or not by using an LP solver.

The LP solver efficiently detects infeasibility, however that doesn't mean that we should stop here.

Linear programming is typically used to model something. Then the infeasibility indicates that the thing we are modelling is not within the constraints of reality. This could indicate an error of some kind in our model. And we could try to relax the constraints a bit in order to correct the model.

Thus, upon detecting infeasibility, we can try to detect the meaningless infeasible constraints and find the error in our model.

---

One simple approach is to directly model the sources of infeasibility by introducing extra variable for each constraint with high penalty cost. This way, we relax the constraints and get a new relaxed problem. After solving this new problem, the positive optimal values of extra variables indicate infeasibilities in the original model.

Example: \begin{align*} & \text{maximize:} \ x + y \\ & \text{subject to: } \\ & \qquad x + y \geq 7 \tag{P}\\ & \qquad 3x - y \leq 6 \\ & \qquad x - 3y \geq -6 \end{align*} is infeasible. This can be seen from the plot of constraints in Figure (a) below. Or if we try to solve it using CVXPY in python:

import cvxpy as cp
import numpy as np

x = cp.Variable()
y = cp.Variable()

objective = cp.Maximize(x + y)
constraints = [x + y >= 7, 
               3*x - y <= 6, 
               x - 3*y >= -6]

problem = cp.Problem(objective, constraints)
problem.solve()

we get:

-inf

We can now introduce extra variable $e_i$ for each constraint $i = 1,2,3$, to locate the infeasibility, and get a new relaxed problem: \begin{align*} & \text{maximize:} \ x + y - 100 e_1 - 100 e_2 - 100 e_3 \\ & \text{subject to: } \\ & \qquad x + y + e_1 \geq 7 \tag{P'}\\ & \qquad 3x - y - e_2 \leq 6 \\ & \qquad x - 3y + e3 \geq -6 \\ & \qquad e_1 \geq 0, e_2 \geq 0, e_3 \geq 0 \end{align*}

Note that the values of the coefficients of these extra variables must be negative when maximizing to achieve high penalty cost in the objective. After solving this new problem:

e1 = cp.Variable()
e2 = cp.Variable()
e3 = cp.Variable()

objective = cp.Maximize(x + y - 100*e1 - 100*e2 - 100*e3)
constraints = [x + y + e1 >= 7, 
               3*x - y - e2 <= 6, 
               x - 3*y + e3 >= -6,
               e1 >= 0, e2 >= 0, e3 >= 0]

problem = cp.Problem(objective, constraints)
problem.solve()

we can print the optimal values of the new variables:

print(["{0:0.2f}".format(var.value) for var in [x, y, e1, e2, e3]])

and see that the optimal values of variables $x, y$ and extra variables $e_1, e_2, e_3$ are $3, 3, 1, 0, 0$ respectively:

['3.00', '3.00', '1.00', '0.00', '0.00']

The optimal value of the first extra variable $e_1$ is $1$, which indicates that first constraint $x + y \geq 7$ was relaxed to $x + y \geq 6$ in our original model. This can be seen from plot of relaxed constraints in Figure (b) below.

Adding the penalty cost $100$ to the optimal value of objective function:

print("{0:0.2f}".format(problem.value + 100))

we get that the optimal value of objective function in our original model is $6$:

6.00

Note that multiple solutions are possible. In this case, the first constraint was relaxed to make the model feasible. For example, we could relax the first constraint even more, say to $x + y \geq 2$, by setting $e_1 = 5$, to reach the same solution. This is shown in Figure (c) below:

This is just one simple approach to determine how to correct the model when we encounter infeasibility in our LP.

---

There is an active research on different algorithms to deal with infeasibility, see for example [1]. And some of these algorithms are incorporated into LP solvers.

[1]: Kristóf Bérczi, Alexander Göke, Lydia Mirabel Mendoza-Cadena, and Matthias Mnich. Resolving infeasibility of linear systems: A parameterized approach. arXiv:2209.02017 [cs.DS], September 2022. https://arxiv.org/pdf/2209.02017.pdf

Answer 4

i had this same problem when using a solver when using lpsolver i found the solution use IDE or API

lpsolve, .is_feasible

http://lpsolve.sourceforge.net/5.5/lp_solveAPIreference.htm

http://web.mit.edu/lpsolve_v5520/doc/lp_solveAPIreference.htm