{{Short description|Concept from linear programming}} {{one source|date=December 2018}} 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 [[N-dimensional polyhedron|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 one BFS to another until an optimal solution is found.<ref name=gm06>{{Cite Gartner Matousek 2006}}{{rp|44–48}}</ref>
== 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 <math display="inline">\mathbf{c^T} \mathbf{x}</math> :subject to <math>A\mathbf{x} = \mathbf{b}</math> and <math>\mathbf{x} \ge 0</math> where: * <math>\mathbf{c^T}</math> and <math>\mathbf{x}</math> are vectors of size ''n'' (the number of variables); * <math>\mathbf{b}</math> is a vector of size ''m'' (the number of constraints); * <math>A</math> is an ''m''-by-''n'' matrix; * <math>\mathbf{x} \ge 0</math> means that all variables are non-negative.
Any linear program can be converted into an equational form by adding [[slack variable]]s.
As a preliminary clean-up step, we verify that: * The system <math>A\mathbf{x} = \mathbf{b}</math> 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 <math>A</math> are [[Linear independence|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 <math>\mathbf{x} \ge 0</math> such that <math>A\mathbf{x} = \mathbf{b}</math>. 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 <math>A\mathbf{x} = \mathbf{b}</math> has many solutions; each such solution is called a '''feasible solution''' of the LP.
=== Basis === A '''basis''' of the LP is a [[Invertible matrix|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 <math>A_B</math> the square ''m''-by-''m'' matrix made of the ''m'' columns of <math>A</math> indexed by ''B''. If <math>A_B</math> is [[Algebraic curve#Singularities|nonsingular]], the columns indexed by ''B'' are a [[Basis (linear algebra)|basis]] of the [[column space]] of <math>A</math>. In this case, we call ''B'' '''a basis of the LP.'''
Since the rank of <math>A</math> is ''m'', it has at least one basis; since <math>A</math> has ''n'' columns, it has at most <math>\binom{n}{m}</math> bases.
=== Basic feasible solution === Given a basis ''B'', we say that a feasible solution <math>\mathbf{x}</math> is a '''basic feasible solution with basis B''' if all its non-zero variables are indexed by ''B'', that is, for all <math>j\not\in B: ~~ x_j = 0</math>.
== Properties == 1. A BFS is determined only by the constraints of the LP (the matrix <math>A</math> and the vector <math>\mathbf{b}</math>); it does not depend on the optimization objective.
2. By definition, a BFS has at most ''m'' non-zero variables and at least ''n''-''m'' zero variables. A BFS can have less than ''m'' non-zero variables; in that case, it can have many different bases, all of which contain the indices of its non-zero variables.
3. A feasible solution <math>\mathbf{x}</math> is basic if-and-only-if the columns of the matrix <math>A_K</math> are linearly independent, where ''K'' is the set of indices of the non-zero elements of <math>\mathbf{x}</math>.<ref name="gm06" />{{rp|45}}
4. Each basis determines a unique BFS: for each basis ''B'' of ''m'' indices, there is at most one BFS <math>\mathbf{x_B}</math> with basis ''B''. This is because <math>\mathbf{x_B}</math> must satisfy the constraint <math>A_B \mathbf{x_B} = b</math>, and by definition of basis the matrix <math>A_B</math> is non-singular, so the constraint has a unique solution: <blockquote><math>\mathbf{x_B} = {A_B}^{-1}\cdot b</math> </blockquote>The opposite is not true: each BFS can come from many different bases. If the unique solution of <math>\mathbf{x_B} = {A_B}^{-1}\cdot b</math> satisfies the non-negativity constraints <math>\mathbf{x_B} \geq 0</math>, then ''B'' is called a '''feasible basis'''.
5. If a linear program has an optimal solution (i.e., it has a feasible solution, and the set of feasible solutions is bounded), then it has an optimal BFS. 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.
Since the number of BFS-s is finite and bounded by <math>\binom{n}{m}</math>, an optimal solution to any LP can be found in finite time by just evaluating the objective function in all <math>\binom{n}{m}</math>BFS-s. This is not the most efficient way to solve an LP; the [[simplex algorithm]] examines the BFS-s in a much more efficient way.
== Examples == Consider a linear program with the following constraints:
<math>\begin{align} x_1 + 5 x_2 + 3 x_3 + 4 x_4 + 6 x_5 &= 14 \\ x_2 + 3 x_3 + 5 x_4 + 6 x_5 &= 7 \\ \forall i\in\{1,\ldots,5\}: x_i&\geq 0 \end{align}</math>
The matrix ''A'' is:
<math>A = \begin{pmatrix} 1 & 5 & 3 & 4 & 6 \\ 0 & 1 & 3 & 5 & 6 \end{pmatrix} ~~~~~ \mathbf{b} = (14~~7)</math>
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 ''B''={2,4} is a basis, since the matrix <math>A_B = \begin{pmatrix} 5 & 4 \\ 1 & 5 \end{pmatrix} </math> is non-singular.
The unique BFS corresponding to this basis is <math>x_B = (0~~2~~0~~1~~0) </math>.
== Geometric interpretation == [[File:Elongated pentagonal orthocupolarotunda.png|thumb|100x100px]] The set of all feasible solutions is an intersection of [[dimension|hyperspaces]]. Therefore, it is a [[Convex polyhedra|convex polyhedron]]. If it is bounded, then it is a [[convex polytope]]. Each BFS corresponds to a vertex of this polytope.<ref name="gm06" />{{rp|53–56}}
== Basic feasible solutions for the dual problem == As mentioned above, every basis ''B'' defines a unique basic feasible solution <math>\mathbf{x_B} = {A_B}^{-1}\cdot b</math> . In a similar way, each basis defines a solution to the [[dual linear program]]: :minimize <math display="inline">\mathbf{b^T} \mathbf{y}</math> :subject to <math>A^T\mathbf{y} \geq \mathbf{c}</math>. The solution is <math>\mathbf{y_B} = {A^T_B}^{-1}\cdot c</math>.
== Finding an optimal BFS == There are several methods for finding a BFS that is also optimal.
=== Using the simplex algorithm === In practice, the easiest way to find an optimal BFS is to use the [[simplex algorithm]]. It keeps, at each point of its execution, a "current basis" ''B'' (a subset of ''m'' out of ''n'' variables), a "current BFS", and a "current tableau". The tableau is a representation of the linear program where the basic variables are expressed in terms of the non-basic ones:<ref name="gm06" />{{rp|65}}<math display="block">\begin{align} x_B &= p + Q x_N \\ z &= z_0 + r^T x_N \end{align}</math>where <math>x_B</math> is the vector of ''m'' basic variables, <math>x_N</math> is the vector of ''n'' non-basic variables, and <math>z</math> is the maximization objective. Since non-basic variables equal 0, the current BFS is <math>p</math>, and the current maximization objective is <math>z_0</math>.
If all coefficients in <math>r</math> are negative, then <math>z_0</math> is an optimal solution, since all variables (including all non-basic variables) must be at least 0, so the second line implies <math>z\leq z_0</math>.
If some coefficients in <math>r</math> are positive, then it may be possible to increase the maximization target. For example, if <math>x_5</math> is non-basic and its coefficient in <math>r</math> is positive, then increasing it above 0 may make <math>z</math> larger. 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").
If this process is done carefully, then it is possible to guarantee that <math>z</math> increases until it reaches an optimal BFS.
=== Converting any optimal solution to an optimal BFS === 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 algorithm|weakly-polynomial time]], such as the [[ellipsoid method]]; however, they usually return optimal solutions that are not basic.
However, Given any optimal solution to the LP, it is easy to find an optimal feasible solution that is also ''basic''.<ref name=":0" />{{Rp|page=see also "external links" below.}}
=== Finding a basis that is both primal-optimal and dual-optimal === A basis ''B'' of the LP is called '''dual-optimal''' if the solution <math>\mathbf{y_B} = {A^T_B}^{-1}\cdot c</math> is an optimal solution to the dual linear program, that is, it minimizes <math display="inline">\mathbf{b^T} \mathbf{y}</math>. 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).
If both <math>\mathbf{x_B} = {A_B}^{-1}\cdot b</math> is an optimal BFS of the primal LP, and <math>\mathbf{y_B} = {A^T_B}^{-1}\cdot c</math> 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]]. However, its run-time is exponential in the worst case. [[Nimrod Megiddo]] proved the following theorems:<ref name=":0">{{Cite journal |last=Megiddo |first=Nimrod |date=1991-02-01 |title=On Finding Primal- and Dual-Optimal Bases |url=https://pubsonline.informs.org/doi/abs/10.1287/ijoc.3.1.63 |journal=ORSA Journal on Computing |volume=3 |issue=1 |pages=63–65 |doi=10.1287/ijoc.3.1.63 |issn=0899-1499|citeseerx=10.1.1.11.427 }}</ref> * There exists a [[strongly polynomial time]] algorithm that inputs an optimal solution to the primal LP ''and'' an optimal solution to the dual LP, and returns an optimal basis. * If there exists a [[strongly polynomial time]] algorithm that inputs an optimal solution to ''only'' the primal LP (or only the dual LP) and returns an optimal basis, then there exists a strongly-polynomial time algorithm for solving any linear program (the latter is a famous [[open problem]]). Megiddo's algorithms can be executed using a tableau, just like the simplex algorithm. Megiddo in co-work with Beling proposed also fast algorithm which uses the [[Computational complexity of matrix multiplication|fast matrix multiplication algorithms]] <ref>{{cite journal |last1=Beling |first1=Peter A. |last2=Megiddo |first2=N. |date=1998 |title=Using fast matrix multiplication to find basic solutions|journal=Theoretical Computer Science |volume=205|issue=1-2 |pages=307-316 |doi=10.1016/S0304-3975(98)00003-6}}</ref>.
== External links ==
* [https://or.stackexchange.com/a/7214/2576 How to move from an optimal feasible solution to an optimal basic feasible solution]. Paul Robin, Operations Research Stack Exchange.
== References == {{reflist}}
[[Category:Linear programming]]