Flexible identity

In linear programming, a discipline within applied mathematics, a basic solution is any solution of a linear programming problem satisfying certain specified technical conditions.

For a polyhedron $P$ and a vector ${\mathbf{x}}^{*}\in {\mathcal{ℛ}}^n$, ${\mathbf{x}}^{*}$ is a basic solution if:

1. All the equality constraints defining $P$ are active at ${\mathbf{x}}^{*}$
2. Of all the constraints that are active at that vector, at least $n$ of them must be linearly independent. Note that this also means that at least $n$ constraints must be active at that vector.

A constraint is active for a particular solution $\mathbf{x}$ if it is satisfied at equality for that solution.

A basic solution that satisfies all the constraints defining $P$ or in other words, one that lies within $P$ is called a basic feasible solution.