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 subject to and where: and are vectors of size n (the number of variables); is a vector of size m (the number of constraints); is an m-by-n matrix; 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 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 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 such that . 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 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 {1,...,n}. Denote by the square m-by-m matrix made of the m columns of indexed by B. If is nonsingular, the columns indexed by B are a basis of the column space of . In this case, we call B a basis of the LP. Since the rank of is m, it has at least one basis; since has n columns, it has at most bases. Basic feasible solution Given a basis B, we say that a feasible solution is a basic feasible solution with basis B if all its