# Basic feasible solution

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Basic_feasible_solution
> Markdown URL: https://mediated.wiki/source/Basic_feasible_solution.md
> Source: https://en.wikipedia.org/wiki/Basic_feasible_solution
> Source revision: 1333068742
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Concept from linear programming

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources. Find sources: "Basic feasible solution" – news · newspapers · books · scholar · JSTOR (December 2018)

In the theory of [linear programming](/source/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](/source/N-dimensional_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](/source/Simplex_algorithm), which essentially travels from one BFS to another until an optimal solution is found.[1]

## 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 c T x {\textstyle \mathbf {c^{T}} \mathbf {x} }

- subject to A x = b {\displaystyle A\mathbf {x} =\mathbf {b} } and x ≥ 0 {\displaystyle \mathbf {x} \geq 0}

where:

- c T {\displaystyle \mathbf {c^{T}} } and x {\displaystyle \mathbf {x} } are vectors of size *n* (the number of variables);

- b {\displaystyle \mathbf {b} } is a vector of size *m* (the number of constraints);

- A {\displaystyle A} is an *m*-by-*n* matrix;

- x ≥ 0 {\displaystyle \mathbf {x} \geq 0} means that all variables are non-negative.

Any linear program can be converted into an equational form by adding [slack variables](/source/Slack_variable).

As a preliminary clean-up step, we verify that:

- The system A x = b {\displaystyle A\mathbf {x} =\mathbf {b} } 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 {\displaystyle A} are [linearly independent](/source/Linear_independence), 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 x ≥ 0 {\displaystyle \mathbf {x} \geq 0} such that A x = b {\displaystyle A\mathbf {x} =\mathbf {b} } . 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 x = b {\displaystyle A\mathbf {x} =\mathbf {b} } has many solutions; each such solution is called a **feasible solution** of the LP.

### Basis

A **basis** of the LP is a [nonsingular](/source/Invertible_matrix) 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 A B {\displaystyle A_{B}} the square *m*-by-*m* matrix made of the *m* columns of A {\displaystyle A} indexed by *B*. If A B {\displaystyle A_{B}} is [nonsingular](/source/Algebraic_curve#Singularities), the columns indexed by *B* are a [basis](/source/Basis_(linear_algebra)) of the [column space](/source/Column_space) of A {\displaystyle A} . In this case, we call *B* **a basis of the LP.**

Since the rank of A {\displaystyle A} is *m*, it has at least one basis; since A {\displaystyle A} has *n* columns, it has at most ( n m ) {\displaystyle {\binom {n}{m}}} bases.

### Basic feasible solution

Given a basis *B*, we say that a feasible solution x {\displaystyle \mathbf {x} } is a **basic feasible solution with basis B** if all its non-zero variables are indexed by *B*, that is, for all j ∉ B : x j = 0 {\displaystyle j\not \in B:~~x_{j}=0} .

## Properties

1. A BFS is determined only by the constraints of the LP (the matrix A {\displaystyle A} and the vector b {\displaystyle \mathbf {b} } ); 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 x {\displaystyle \mathbf {x} } is basic if-and-only-if the columns of the matrix A K {\displaystyle A_{K}} are linearly independent, where *K* is the set of indices of the non-zero elements of x {\displaystyle \mathbf {x} } .[1]: 45

4. Each basis determines a unique BFS: for each basis *B* of *m* indices, there is at most one BFS x B {\displaystyle \mathbf {x_{B}} } with basis *B*. This is because x B {\displaystyle \mathbf {x_{B}} } must satisfy the constraint A B x B = b {\displaystyle A_{B}\mathbf {x_{B}} =b} , and by definition of basis the matrix A B {\displaystyle A_{B}} is non-singular, so the constraint has a unique solution:

x B = A B − 1 ⋅ b {\displaystyle \mathbf {x_{B}} ={A_{B}}^{-1}\cdot b}

The opposite is not true: each BFS can come from many different bases. If the unique solution of x B = A B − 1 ⋅ b {\displaystyle \mathbf {x_{B}} ={A_{B}}^{-1}\cdot b} satisfies the non-negativity constraints x B ≥ 0 {\displaystyle \mathbf {x_{B}} \geq 0} , 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](/source/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](/source/Extreme_point) of the set of feasible solutions.

Since the number of BFS-s is finite and bounded by ( n m ) {\displaystyle {\binom {n}{m}}} , an optimal solution to any LP can be found in finite time by just evaluating the objective function in all ( n m ) {\displaystyle {\binom {n}{m}}} BFS-s. This is not the most efficient way to solve an LP; the [simplex algorithm](/source/Simplex_algorithm) examines the BFS-s in a much more efficient way.

## Examples

Consider a linear program with the following constraints:

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 ∀ i ∈ { 1 , … , 5 } : x i ≥ 0 {\displaystyle {\begin{aligned}x_{1}+5x_{2}+3x_{3}+4x_{4}+6x_{5}&=14\\x_{2}+3x_{3}+5x_{4}+6x_{5}&=7\\\forall i\in \{1,\ldots ,5\}:x_{i}&\geq 0\end{aligned}}}

The matrix *A* is:

A = ( 1 5 3 4 6 0 1 3 5 6 ) b = ( 14 7 ) {\displaystyle A={\begin{pmatrix}1&5&3&4&6\\0&1&3&5&6\end{pmatrix}}~~~~~\mathbf {b} =(14~~7)}

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 A B = ( 5 4 1 5 ) {\displaystyle A_{B}={\begin{pmatrix}5&4\\1&5\end{pmatrix}}} is non-singular.

The unique BFS corresponding to this basis is x B = ( 0 2 0 1 0 ) {\displaystyle x_{B}=(0~~2~~0~~1~~0)} .

## Geometric interpretation

The set of all feasible solutions is an intersection of [hyperspaces](/source/Dimension). Therefore, it is a [convex polyhedron](/source/Convex_polyhedra). If it is bounded, then it is a [convex polytope](/source/Convex_polytope). Each BFS corresponds to a vertex of this polytope.[1]: 53–56

## Basic feasible solutions for the dual problem

As mentioned above, every basis *B* defines a unique basic feasible solution x B = A B − 1 ⋅ b {\displaystyle \mathbf {x_{B}} ={A_{B}}^{-1}\cdot b} . In a similar way, each basis defines a solution to the [dual linear program](/source/Dual_linear_program):

- minimize b T y {\textstyle \mathbf {b^{T}} \mathbf {y} }

- subject to A T y ≥ c {\displaystyle A^{T}\mathbf {y} \geq \mathbf {c} } .

The solution is y B = A B T − 1 ⋅ c {\displaystyle \mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c} .

## 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](/source/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:[1]: 65 x B = p + Q x N z = z 0 + r T x N {\displaystyle {\begin{aligned}x_{B}&=p+Qx_{N}\\z&=z_{0}+r^{T}x_{N}\end{aligned}}} where x B {\displaystyle x_{B}} is the vector of *m* basic variables, x N {\displaystyle x_{N}} is the vector of *n* non-basic variables, and z {\displaystyle z} is the maximization objective. Since non-basic variables equal 0, the current BFS is p {\displaystyle p} , and the current maximization objective is z 0 {\displaystyle z_{0}} .

If all coefficients in r {\displaystyle r} are negative, then z 0 {\displaystyle z_{0}} is an optimal solution, since all variables (including all non-basic variables) must be at least 0, so the second line implies z ≤ z 0 {\displaystyle z\leq z_{0}} .

If some coefficients in r {\displaystyle r} are positive, then it may be possible to increase the maximization target. For example, if x 5 {\displaystyle x_{5}} is non-basic and its coefficient in r {\displaystyle r} is positive, then increasing it above 0 may make z {\displaystyle z} 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 z {\displaystyle z} 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](/source/Weakly_polynomial_time_algorithm), such as the [ellipsoid method](/source/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*.[2]: 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 y B = A B T − 1 ⋅ c {\displaystyle \mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c} is an optimal solution to the dual linear program, that is, it minimizes b T y {\textstyle \mathbf {b^{T}} \mathbf {y} } . 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 x B = A B − 1 ⋅ b {\displaystyle \mathbf {x_{B}} ={A_{B}}^{-1}\cdot b} is an optimal BFS of the primal LP, and y B = A B T − 1 ⋅ c {\displaystyle \mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c} 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](/source/Simplex_algorithm). However, its run-time is exponential in the worst case. [Nimrod Megiddo](/source/Nimrod_Megiddo) proved the following theorems:[2]

- There exists a [strongly polynomial time](/source/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](/source/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](/source/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 [fast matrix multiplication algorithms](/source/Computational_complexity_of_matrix_multiplication) [3].

## External links

- [How to move from an optimal feasible solution to an optimal basic feasible solution](https://or.stackexchange.com/a/7214/2576). Paul Robin, Operations Research Stack Exchange.

## References

1. ^ [***a***](#cite_ref-gm06_1-0) [***b***](#cite_ref-gm06_1-1) [***c***](#cite_ref-gm06_1-2) [***d***](#cite_ref-gm06_1-3) Gärtner, Bernd; [Matoušek, Jiří](/source/Ji%C5%99%C3%AD_Matou%C5%A1ek_(mathematician)) (2006). *Understanding and Using Linear Programming*. Berlin: Springer. [ISBN](/source/ISBN_(identifier)) [3-540-30697-8](https://en.wikipedia.org/wiki/Special:BookSources/3-540-30697-8).: 44–48

1. ^ [***a***](#cite_ref-:0_2-0) [***b***](#cite_ref-:0_2-1) Megiddo, Nimrod (1991-02-01). ["On Finding Primal- and Dual-Optimal Bases"](https://pubsonline.informs.org/doi/abs/10.1287/ijoc.3.1.63). *ORSA Journal on Computing*. **3** (1): 63–65. [CiteSeerX](/source/CiteSeerX_(identifier)) [10.1.1.11.427](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.427). [doi](/source/Doi_(identifier)):[10.1287/ijoc.3.1.63](https://doi.org/10.1287%2Fijoc.3.1.63). [ISSN](/source/ISSN_(identifier)) [0899-1499](https://search.worldcat.org/issn/0899-1499).

1. **[^](#cite_ref-3)** Beling, Peter A.; Megiddo, N. (1998). "Using fast matrix multiplication to find basic solutions". *Theoretical Computer Science*. **205** (1–2): 307–316. [doi](/source/Doi_(identifier)):[10.1016/S0304-3975(98)00003-6](https://doi.org/10.1016%2FS0304-3975%2898%2900003-6).

---
Adapted from the Wikipedia article [Basic feasible solution](https://en.wikipedia.org/wiki/Basic_feasible_solution) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Basic_feasible_solution?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.