Basic feasible solutions

Dependencies:

  1. Polyhedral set and polyhedral cone
  2. Linear independence

Let $P = \{x: Ax \le b, Cx = d\} \subseteq \mathbb{R}^n$ be a polyhedron. $x$ is called a basic solution of $P$ iff at least $n$ of the defining constraints of $P$ are tight at $x$ and linearly independent.

$x$ is called a basic feasible solution (BFS) of $P$ iff it is a basic solution of $P$ and $x \in P$.

For a basic solution $x$ of $P$, if there are more than $n$ tight constraints at $x$, then $x$ is called a degenerate solution, and the number of tight constraints minus $n$ is called the order of degeneracy.

Dependency for:

  1. Polyhedron is unbounded iff it has direction
  2. Extreme point iff BFS
  3. Condition for existence of BFS in a polyhedron
  4. LP is optimized at BFS
  5. BFS iff vertex iff extreme point
  6. Point in polytope is convex combination of BFS
  7. BFS is vertex
  8. Representing point in full-rank polyhedron
  9. Condition for polyhedral cone to be pointed

Info:

Transitive dependencies:

  1. Group
  2. Ring
  3. Field
  4. Vector Space
  5. Linear independence
  6. Semiring
  7. Matrix
  8. Cone
  9. Convex combination and convex hull
  10. Convex set
  11. Polyhedral set and polyhedral cone