This blog is talking about how to solve the basic solutions from LO problem.

Rank (Remove redundant constraints)

Recall: A polyhedron of the form ${ P = \{\bar{x} \in \mathbb{R}^n | A’ \bar{x} = \bar{b’}, \bar{x} \geq \bar{0} \} }$ where ${ A’ }$ is an ${ m\times n }$ matrix ${ \bar{b’} \in \mathbb{R}^m }$ is said to be a polyhedron in standard form.

If the rank of matrix ${ A’ }$ is ${ k }$, we can extract ${ k }$ linearly independent rows from ${ A’ }$ and the corresponding elements from ${ b }$. (Here, we need to note we have to guarantee ${ A’ \bar{x} = \bar{b’} }$ have solutions, or say ${ P }$ is not empty.) Hence, we get ${ A \in \mathbb{R}^{k \times n}, \bar{b} \in \mathbb{R}^k }$.

Theorem: Provide ${ P }$ is nonempty, the polyhedra

\[P = \{\bar{x}\in \mathbb{R}^n | A' \bar{x} = \bar{b'}, \bar{x} \geq \bar{0}\}\]

and

\[Q = \{\bar{x}\in \mathbb{R}^n | A \bar{x} = \bar{b}, \bar{x} \geq \bar{0}\}\]

coincide. (i.e. ${ P = Q }$)

Proof.

Without loss of generality, we may assume that because we can simply permute the rows of the augmented matrix $\left[ A’ \mid \bar{b} \right]$ representing the linear system $A’x = \mathbf{\bar{b}}$ without modifying the polyhedron $P$.

Thus, we may assume that

\[A' = \left[ \begin{array}{c} \bar{a}_1^{\top} \\ \bar{a}_2^{\top} \\ \vdots \\ \bar{a}_k^{\top} \\ \vdots \\ \bar{a}_m^{\top} \end{array} \right]\]

and

\[A = \left[ \begin{array}{c} \bar{a}_1^{\top} \\ \bar{a}_2^{\top} \\ \vdots \\ \bar{a}_k^{\top} \end{array} \right]\]

Clearly, $P \subset Q$ because any solution of $A’x = \mathbf{\bar{b}}$ is automatically a solution of $Ax = b$.

Then, we will show $Q \subset P$. Since the $k$ rows $\bar{a}_1^{\top}, \bar{a}_2^{\top}, …, \bar{a}_k^{\top}$ of the matrix $A$ form a basis of the row space of the matrix $A’$, every row $\bar{a}_i^{\top}$ of $A’$ can be expressed as a linear combination $\bar{a}_i^{\top} = \sum_{j=1}^k \lambda_{ij} \bar{a}_j^{\top}$ of the rows of $A$.

Since $P$ is assumed to be nonempty, we can pick an element $\bar{x}$ in $P$. We have \(b_i = \bar{a}_i^{\top} x = \left( \sum_{j=1}^k \lambda_{ij} \bar{a}_j^{\top} \right) x = \sum_{j=1}^k \lambda_{ij} \left( \bar{a}_j^{\top} x \right) = \sum_{j=1}^k \lambda_{ij} b_j \quad \quad \forall i \in \{1,2,...,m\}\)

Consider now an element $\bar{y} \in Q$. We need to show that $\bar{y} \in P$. For each $i \in {1,2,…,m}$, we have

\[\bar{a}_i^{\top} \bar{y} = \left( \sum_{j=1}^k \lambda_{ij} \bar{a}_j^{\top} \right) \bar{y} = \sum_{j=1}^k \lambda_{ij} \left( \bar{a}_j^{\top} \bar{y} \right) = \sum_{j=1}^k \lambda_{ij} b_j = b_i\]

Thus we have $\bar{y} \in P$. $\square$

Conclusion: Provided a polyhedron in standard form ${P = \{ x \in \mathbb{R}^n \mid A’x = \bar{b}, x \geq 0 \}}$ is nonempty, we can describe it equivalently (but more economically) by constraints $Ax = b, x \geq 0$ where the matrix $A$ has full row rank.

The above talking can let us describe constraints more economically as ${ A \bar{x} = \bar{b} , \bar{x} \geq \bar{0}}$, where ${ A }$ has full (row) rank.

How to solve basic solution

Now, suppose ${ A }$ is full rank, how can we solve the basic solution in standard form.

Theorem

Theorem: Assuming the ${ m }$ rows of the matrix ${ A \in \mathbb{R}^{m \times n} }$ are linearly independent, consider the constraints ${ A \bar{x} = \bar{b} }$ and ${ \bar{x} \geq \bar{0} }$.

A vector ${ \bar{x}^* \in \mathbb{R}^n }$ is a basic solution if and only if ${ A \bar{x}^* = \bar{b}}$ is satisfied and there exists indices ${ B(1),B(2),\cdots,B(m) }$ such that

(1) the columns ${ \overline{A}_{B(1)},\overline{A}_{B(2)},\cdots, \overline{A}_{B(m)} }$ are linearlu independent and

(2) ${ x^*_i = 0 }$ if ${ i \notin \{B(1),B(2),\cdots,B(m)\} }$

Proof. LO_2.3

Recipe for solving basic solutions

By above theorem, we can give the recipe to find the basic solutions of a standard form polyhedron

Assuming the ${ m }$ rows of the matrix ${ A \in \mathbb{R}^{m \times n} }$ are linearly independent, the polyhedron is in standard form ${A \bar{x} = \bar{b} }$ and ${ \bar{x} \geq \bar{0} }$.

STEP 1: Choose ${ m }$ linearly independent columns ${ \overline{A}_{B(1)},\overline{A}_{B(2)},\cdots, \overline{A}_{B(m)} }$ in matrix ${ A }$.

STEP 2: Let ${ x^*_i = 0, \forall i \notin \{B(1),B(2),\cdots,B(m)\} }$

STEP 3: Solve the system ${ A \bar{x}^* = \bar{b} }$. (In fact we only need to solve ${ B \bar{x_B}^* = \bar{b} }$, here ${ B }$ comprised by columns ${ \overline{A}_{B(1)},\overline{A}_{B(2)},\cdots, \overline{A}_{B(m)} }$, and ${ \bar{x}^*_B }$ only contains the elements with indices ${ B(1),B(2),\cdots,B(m) }$)

STEP 4: If all components of the basic solution ${ \bar{x}^* }$ obtained by STEP 3 are nonnegative, then this basic solution is a basic feasible solution.