Basic feasible solution

<h2 id="definitions">Definitions</h2>
<h3>Preliminaries: equational form with linearly-independent rows</h3>
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:

<ul><li>
 
 
 
 
 
 c
 
 T
 
 
 
 
 
 {\displaystyle \mathbf {c^{T}} }
 
 and 
 
 
 
 
 x
 
 
 
 {\displaystyle \mathbf {x} }
 
 are vectors of size n (the number of variables);</li>
<li>
 
 
 
 
 b
 
 
 
 {\displaystyle \mathbf {b} }
 
 is a vector of size m (the number of constraints);</li>
<li>
 
 
 
 A
 
 
 {\displaystyle A}
 
 is an m-by-n matrix;</li>
<li>
 
 
 
 
 x
 
 ≥
 0
 
 
 {\displaystyle \mathbf {x} \geq 0}
 
 means that all variables are non-negative.</li></ul>
Any linear program can be converted into an equational form by adding <a href="/facts/Slack_variable/X61fwPGJ">slack variables</a>.
As a preliminary clean-up step, we verify that:

<ul><li>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);</li>
<li>All m rows of the matrix 
 
 
 
 A
 
 
 {\displaystyle A}
 
 are linearly independent, i.e., its rank is m (otherwise we can just delete redundant rows without changing the LP).</li></ul>
<h3>Feasible solution</h3>
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.

<h3>Basis</h3>
A basis of the LP is a <a href="/facts/Invertible_matrix/fPqXk3V8">nonsingular</a> 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 <a href="/facts/Algebraic_curve/LnWsPmDP">nonsingular</a>, the columns indexed by B are a <a href="/facts/Basis_(linear_algebra)/89IPoN6c">basis</a> of the <a href="/facts/Column_space/INXbQVNI">column space</a> 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.

<h3>Basic feasible solution</h3>
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}
 
.

<h2 id="properties">Properties</h2>
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} }
 
.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>: 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 <a href="/facts/Bauer_maximum_principle/o0PJt964">Bauer maximum principle</a>: 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 
 
 
 
 
 
 
 (
 
 
 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 <a href="/facts/Simplex_algorithm/9fndF6cq">simplex algorithm</a> examines the BFS-s in a much more efficient way.

<h2 id="examples">Examples</h2>
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)}
 
.

<h2 id="geometric-interpretation">Geometric interpretation</h2>

The set of all feasible solutions is an intersection of <a href="/facts/Dimension/0ktmUyac">hyperspaces</a>. Therefore, it is a <a href="/facts/Convex_polyhedra/2pRHcRgC">convex polyhedron</a>. If it is bounded, then it is a <a href="/facts/Convex_polytope/2pRHcRgC">convex polytope</a>. Each BFS corresponds to a vertex of this polytope.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>: 53–56 

<h2 id="basic-feasible-solutions-for-the-dual-problem">Basic feasible solutions for the dual problem</h2>
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 <a href="/facts/Dual_linear_program/Qm3r26pm">dual linear program</a>: 

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}
 
.

<h2 id="finding-an-optimal-bfs">Finding an optimal BFS</h2>
There are several methods for finding a BFS that is also optimal.

<h3>Using the simplex algorithm</h3>
In practice, the easiest way to find an optimal BFS is to use the <a href="/facts/Simplex_algorithm/9fndF6cq">simplex algorithm</a>. 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:<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>: 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.

<h3>Converting any optimal solution to an optimal BFS</h3>
In the worst case, the simplex algorithm may require exponentially many steps to complete. There are algorithms for solving an LP in <a href="/facts/Weakly_polynomial_time_algorithm/77T62gmf">weakly-polynomial time</a>, such as the <a href="/facts/Ellipsoid_method/K3SDpleG">ellipsoid method</a>; 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.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>: see also "external links" below. 

<h3>Finding a basis that is both primal-optimal and dual-optimal</h3>
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 <a href="/facts/Simplex_algorithm/9fndF6cq">Simplex algorithm</a>. However, its run-time is exponential in the worst case. <a href="/facts/Nimrod_Megiddo/fSPK8xyr">Nimrod Megiddo</a> proved the following theorems:<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> 

<ul><li>There exists a <a href="/facts/Strongly_polynomial_time/77T62gmf">strongly polynomial time</a> algorithm that inputs an optimal solution to the primal LP and an optimal solution to the dual LP, and returns an optimal basis.</li>
<li>If there exists a <a href="/facts/Strongly_polynomial_time/77T62gmf">strongly polynomial time</a> 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).</li></ul>
Megiddo's algorithms can be executed using a tableau, just like the simplex algorithm.

<h2 id="external-links">External links</h2>
<ul><li><a href="https://or.stackexchange.com/a/7214/2576">How to move from an optimal feasible solution to an optimal basic feasible solution</a>. Paul Robin, Operations Research Stack Exchange.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN 3-540-30697-8.: 44–48
 <a href="3-540-30697-8" target="_blank">3-540-30697-8</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN 3-540-30697-8.: 44–48
 <a href="3-540-30697-8" target="_blank">3-540-30697-8</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN 3-540-30697-8.: 44–48
 <a href="3-540-30697-8" target="_blank">3-540-30697-8</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN 3-540-30697-8.: 44–48
 <a href="3-540-30697-8" target="_blank">3-540-30697-8</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Megiddo, Nimrod (1991-02-01). "On Finding Primal- and Dual-Optimal Bases". ORSA Journal on Computing. 3 (1): 63–65. CiteSeerX 10.1.1.11.427. doi:10.1287/ijoc.3.1.63. ISSN 0899-1499. <a href="https://pubsonline.informs.org/doi/abs/10.1287/ijoc.3.1.63" target="_blank">https://pubsonline.informs.org/doi/abs/10.1287/ijoc.3.1.63</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Megiddo, Nimrod (1991-02-01). "On Finding Primal- and Dual-Optimal Bases". ORSA Journal on Computing. 3 (1): 63–65. CiteSeerX 10.1.1.11.427. doi:10.1287/ijoc.3.1.63. ISSN 0899-1499. <a href="https://pubsonline.informs.org/doi/abs/10.1287/ijoc.3.1.63" target="_blank">https://pubsonline.informs.org/doi/abs/10.1287/ijoc.3.1.63</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
</ol>

Basic feasible solution open-in-new

Basic feasible solution