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

Info:

Transitive dependencies:

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