Correspondence Between BFS and Vertices

Consider a polyhedron in standard form

$$P = \{ \mathbf{x} \in \mathbb{R}^n : A\mathbf{x} = \mathbf{b},\ \mathbf{x} \geq \mathbf{0} \},$$

where $A$ is an $m \times n$ matrix with full row rank and $m \leq n$.

The fundamental result of linear programming is the following correspondence:

A point $\mathbf{x}^* \in P$ is a vertex of $P$ if and only if $\mathbf{x}^*$ is a basic feasible solution.

Recall how a BFS is built. We select $m$ linearly independent columns of $A$ — this set of column indices is the basis $B$. The variables indexed by $B$ are the basic variables $\mathbf{x}_B$; the remaining $n - m$ are non-basic. Setting the non-basic variables to zero and solving $A_B \mathbf{x}_B = \mathbf{b}$ yields a candidate point. If $\mathbf{x}_B \geq \mathbf{0}$, the candidate is a basic feasible solution, and the correspondence theorem guarantees it is a vertex of $P$.

To illustrate, consider the single-constraint system

$$x_1 + x_2 + s_1 = 4, \qquad x_1, x_2, s_1 \geq 0.$$

Here $n = 3$ and $m = 1$, so each basis consists of one column. The $\binom{3}{1} = 3$ choices give:

• $B = \{s_1\}$: set $x_1 = x_2 = 0$, so $s_1 = 4$. BFS $(0, 0, 4)$, corresponding to the vertex $(x_1, x_2) = (0, 0)$.
• $B = \{x_1\}$: set $x_2 = s_1 = 0$, so $x_1 = 4$. BFS $(4, 0, 0)$, corresponding to the vertex $(4, 0)$.
• $B = \{x_2\}$: set $x_1 = s_1 = 0$, so $x_2 = 4$. BFS $(0, 4, 0)$, corresponding to the vertex $(0, 4)$.

Each basic feasible solution is a vertex of the triangle $\{x_1 + x_2 \leq 4,\ x_1, x_2 \geq 0\}$, and every vertex of the triangle is a BFS.