Number of iteration is exponential with bland's pivoting rule

Question

Consider the following:

$max$ $2^{n-1}x_1 + 2^{n-2}x_2 + \cdots + 2x_{n-1} + x_n$

s.t. $x_1 \leq 5$

$4x_1 + x_2 \leq 25$

.

.

.

$2^nx_1 + 2^{n-1}x_2 + \cdots + 4x_{n-1} + x_n \leq 5^n$

$x_1, ..., x_n \geq 0 $

The result is, the last inequality is NOT binding with $x_n = 0 $, and the optimal solution will be obtained at iterations $2^n$ (shown in above). I have no idea on how to prove these...

Answer 1

Note that there are $2^n$ subsets of $\{x_1, x_2, ..., x_n\}$. One may guess that the reason there are $2^n$ iterations of this program is that each of these subsets appear in the basis exactly once.

Upon testing this hypothesis with $n=2$ and $n=3$, you'll find that the $2^2$ iterations in the $n = 2$ case have bases containing (in this order): $\{\}, \{x_1\}, \{x_1, x_2\}$, and $\{x_2\}$. Likewise, for the $n = 3$ case, the bases contain: $\{\},$ $\{x_1\}$, $\{x_1, x_2\}$, $\{x_2\}$, $\{x_2, x_3\}$, $\{x_1, x_2, x_3\}$, $\{x_1, x_3\}$, and $\{x_3\}$. In both cases, each possible subset of $\{x_1, x_2, \ldots, x_n\}$ appears in the basis.

Furthermore, if we look closer at the sequence of $8$ subsets for $n = 3$, we notice that the first $4$ of those $8$ are actually the same subsets in the same order as those in the $n = 2$ case. We could guess that the sequence for $n = 4$ will be similar, in that it will contain all $2^4$ subsets of $\{x_1, x_2, x_3, x_4\}$ and will be identical to the previous sequence for the first 8 terms. Let's check.

Using a Python script, I get:

$\mathbf{\{\} \rightarrow \{x_1\} \rightarrow \{x_1, x_2\} \rightarrow \{x_2\} \rightarrow \{x_2, x_3\} \rightarrow \{x_1, x_2, x_3\} \rightarrow \{x_1, x_3\} \rightarrow \{x_3\}}$ $\rightarrow \{x_3, x_4\} \rightarrow \{x_1, x_3, x_4\} \rightarrow \{x_1, x_2, x_3, x_4\} \rightarrow \{x_2, x_3, x_4\} \rightarrow \{x_2, x_4\} \rightarrow \{x_1, x_2, x_4\} \rightarrow \{x_1, x_4\} \rightarrow \{x_4\}.$

Indeed, we've seen those first eight subsets already.

(There are other fractal-like patterns going on here, too. For instance, in the last 8 non-boldface terms above, notice that we begin with $\{x_3, x_4\}$ instead of $\{\}$, but then proceed in the same way as before: we (1) include $x_1$, then (2) include $x_2$, then (3) remove $x_1$, and then (4) "include" $x_3$ [except $x_3$ is already included due to our starting with $\{x_3, x_4\}$, so we remove it instead], and so on. There may be a nice binary-counting interpretation to this.)

To prove that this pattern holds in general, one tool you could experiment with is induction. Notice that the matrix $A$ in the $n = 2$ case looks very similar to that in the $n = 3$ case. Looking at what you've written, it's clear that matrix $A$ for $n = k+1$ contains a submatrix identical to that for $n = k$. Similar things can be said for the RHS vector and (though it's a bit trickier) the objective function row.