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 $P$ and a vector $\backslash mathbf\{x\}^*\; \backslash in\; \backslash mathbb\{R\}^n$, $\backslash mathbf\{x\}^*$ is a basic solution if:

1. All the equality constraints defining $P$ are active at $\backslash 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.{{cite book|last1=Bertsimas|first1=Dimitris|last2=Tsitsiklis|first2=John N.|title=Introduction to linear optimization|year=1997|publisher=Athena Scientific|location=Belmont, Mass.|isbn=978-1-886529-19-9|pages=50|url=http://athenasc.com/linoptbook.html}}

A constraint is active for a particular solution $\backslash 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.