basic feasible solution

In the theory of linear programming, a basic feasible solution (BFS) is a solution with a minimal set of non-zero variables. Geometrically, each BFS corresponds to a corner of the polyhedron of feasible solutions. If there exists an optimal solution, then there exists an optimal BFS. Hence, to find an optimal solution, it is sufficient to consider the BFS-s. This fact is used by the simplex algorithm, which essentially travels from some BFS to another until an optimal one is found.

Definitions

Preliminaries: equational form with linearly-independent rows

For the definitions below, we first present the linear program in the so-called ''equational form'':
:maximize $\mathbf \mathbf$
:subject to $A\mathbf = \mathbf$ and $\mathbf \ge 0$
where:
* $\mathbf$ and $\mathbf$ are vectors of size ''n'' (the number of variables);
* $\mathbf$ is a vector of size ''m'' (the number of constraints);
* $A$ is an ''m''-by-''n'' matrix;
* $\mathbf \ge 0$ means that all variables are non-negative.

Any linear program can be converted into an equational form by adding slack variables.

As a preliminary clean-up step, we verify that:
* The system $A\mathbf = \mathbf$ has at least one solution (otherwise the whole LP has no solution and there is nothing more to do);
* All ''m'' rows of the matrix $A$ are linearly independent, i.e., its rank is ''m'' (otherwise we can just delete redundant rows without changing the LP).

Feasible solution

A feasible solution of the LP is any vector $\mathbf \ge 0$ such that $A\mathbf = \mathbf$. We assume that there is at least one feasible solution. If ''m'' = ''n'', then there is only one feasible solution. Typically ''m'' < ''n'', so the system $A\mathbf = \mathbf$ has many solutions; each such solution is called a feasible solution of the LP.

Basis

A basis of the LP is a nonsingular submatrix of ''A,'' with all ''m'' rows and only ''m''<''n'' columns.

Sometimes, the term basis is used not for the submatrix itself, but for the set of indices of its columns. Let ''B'' be a subset of ''m'' indices from . Denote by $A_B$ the square ''m''-by-''m'' matrix made of the ''m'' columns of $A$ indexed by ''B''. If $A_B$ is nonsingu