Basic solution (linear programming)

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 [math]\displaystyle{ P }[/math] and a vector [math]\displaystyle{ \mathbf{x}^* \in \mathbb{R}^n }[/math], [math]\displaystyle{ \mathbf{x}^* }[/math] is a basic solution if:

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

A constraint is active for a particular solution [math]\displaystyle{ \mathbf{x} }[/math] if it is satisfied at equality for that solution.

A basic solution that satisfies all the constraints defining [math]\displaystyle{ P }[/math] (or, in other words, one that lies within [math]\displaystyle{ P }[/math]) is called a basic feasible solution.