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 vertex of the polyhedron of feasible solutions.

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 one BFS to another until an optimal solution is found.

[1] For the definitions below, we first present the linear program in the so-called equational form: where: Any linear program can be converted into an equational form by adding slack variables.

As a preliminary clean-up step, we verify that: A feasible solution of the LP is any vector

A basis of the LP is a nonsingular submatrix of A, with all m rows and only m

Sometimes, the term basis is used not for the submatrix itself, but for the set of indices of its columns.

the square m-by-m matrix made of the m columns of

In this case, we call B a basis of the LP.

is a basic feasible solution with basis B if all its non-zero variables are indexed by B, that is, for all

A BFS is determined only by the constraints of the LP (the matrix

are linearly independent, where K is the set of indices of the non-zero elements of

This is a consequence of the Bauer maximum principle: the objective of a linear program is convex; the set of feasible solutions is convex (it is an intersection of hyperspaces); therefore the objective attains its maximum in an extreme point of the set of feasible solutions.

, an optimal solution to any LP can be found in finite time by just evaluating the objective function in all

Here, m=2 and there are 10 subsets of 2 indices, however, not all of them are bases: the set {3,5} is not a basis since columns 3 and 5 are linearly dependent.

The set of all feasible solutions is an intersection of hyperspaces.

[1]: 53–56 As mentioned above, every basis B defines a unique basic feasible solution

In practice, the easiest way to find an optimal BFS is to use the simplex algorithm.

The tableau is a representation of the linear program where the basic variables are expressed in terms of the non-basic ones:[1]: 65

Since non-basic variables equal 0, the current BFS is

If it is possible to do so without violating other constraints, then the increased variable becomes basic (it "enters the basis"), while some basic variable is decreased to 0 to keep the equality constraints and thus becomes non-basic (it "exits the basis").

In the worst case, the simplex algorithm may require exponentially many steps to complete.

There are algorithms for solving an LP in weakly-polynomial time, such as the ellipsoid method; however, they usually return optimal solutions that are not basic.

A basis B of the LP is called dual-optimal if the solution

is an optimal solution to the dual linear program, that is, it minimizes

In general, a primal-optimal basis is not necessarily dual-optimal, and a dual-optimal basis is not necessarily primal-optimal (in fact, the solution of a primal-optimal basis may even be unfeasible for the dual, and vice versa).

is an optimal BFS of the dual LP, then the basis B is called PD-optimal.

Every LP with an optimal solution has a PD-optimal basis, and it is found by the Simplex algorithm.

Nimrod Megiddo proved the following theorems:[2] Megiddo's algorithms can be executed using a tableau, just like the simplex algorithm.