From Glossary

Jump to: navigation, search

Associated with a submatrix of LaTeX: A, say LaTeX: B, whose columns comprise a basis for LaTeX: \mathbb{R}^m (i.e., LaTeX: B consists of LaTeX: m linearly independent columns of LaTeX: A, which is a basis for LaTeX: \mathbb{R}^m).

Here are some related terms that arise in linear programming.

  • Adjacent basis. One that differs in exactly one column from a given basis.
  • Basic column. A column of the basis matrix.
  • Basic variable. The variable, say LaTeX: x_j, associated with the LaTeX: j-th column of the basis matrix.
  • Basic level. The value of a basic variable.
  • Basic solution. The solution, LaTeX: x, obtained by setting nonbasic values to some bound value, like 0, resulting in a unique solution for the basic variables. That is, LaTeX: Ax=b is equivalent to LaTeX: Bu + Nv = b, where LaTeX: A=[B \; N] and LaTeX: x=[u^T \; v^T]^T. Upon fixing the value of LaTeX: v, the nonsingularity of LaTeX: B gives the basic solution with LaTeX: u = B^{-1}(b - Nv). In a standard linear program, LaTeX: v=0, and hence LaTeX: u = B^{-1} b.
  • Basic feasible solution. A basic solution that is feasible --i.e., the basic values satisfy their bounds. (In a standard LP, this means LaTeX: B^{-1}b \ge 0.)
  • Basis kernel. After performing forward triangularization, if the basis does not triangularize completely, backward triangularization is applied. The result is a (rearranged) blocking of the basis into three segments:
                    | \ <--- Forward triangle
                    |__\ ______
                    |   |      |
                    |   |      | <--- Kernel
                    |   |______|
                    |          |\
                    |          | \ <--- Backward triangle
    Each row and column in the kernel has at least 2 nonzeroes.

Personal tools