Practice: Adjacent Basic Solutions

Columns: $A_1=(1,2{)}^{\mathsf{T}}$, $A_2=(1,0{)}^{\mathsf{T}}$, $A_3=(1,0{)}^{\mathsf{T}}$, $A_4=(0,1{)}^{\mathsf{T}}$; $m=2$.

(a) The starting point. $A_B$ for $\{3,4\}$ is , so $x_3=6$, $x_4=8$, and the point is $(0,0,6,8)$.

(b) The edge direction. Entering $j=1$:

So as $x_1$ rises to $\theta$, $x_3$ becomes $6-\theta$ and $x_4$ becomes $8-2\theta$. The full direction is $d=(1,0,-1,-2)$.

The step limit. Both components of $u$ are positive, so both rows bound the step:

${\theta }^{\ast }=4$, attained in the second row, so $x_4$ leaves.

(c) The corner reached. $x_1=4$, $x_3=6-4=2$, $x_4=0$. The point is $(4,0,2,0)$ with basis $\{1,3\}$.

Check: $4+0+2=6$ and $8+0=8$. Both hold, all components nonnegative.

(d) Adjacency. $\{3,4\}$ and $\{1,3\}$ share $\{3\}$, which is $m-1=1$ column. Adjacent, as walking a single edge requires: $x_4$ left, $x_1$ entered.

What was chosen and what was forced. Only the entering variable was chosen. The direction $u$, the step limit, the leaving variable and the destination all followed from the constraints.

First error: adjacency is not proximity. Two corners are adjacent when the bases describing them share all but one column, equivalently, when their active sets differ in exactly one constraint. That condition mentions no distances and no coordinates. Adjacent corners may be arbitrarily far apart, and two corners very close in space may need several swaps to connect.

Second error: the method does not select on distance. The entering variable is chosen by the sign of its reduced cost, the rate at which the objective improves along the edge, not by how far the edge runs. A steep short edge and a shallow long one are judged by the same rule, which looks at neither length.

Third error: the step length is an outcome, not a criterion. How far the walk goes is , determined by when the first basic variable hits zero. It is computed after the direction is chosen, and it can be large, small, or exactly zero at a degenerate corner.

Fourth error: 'never jumps across the region' is false as stated. A single iteration can traverse a long edge from one side of the region to the other. Nothing bounds the distance of one step.

The correct account. At the current corner, examine the nonbasic variables. Any with a negative reduced cost gives an edge along which the objective improves; choose one. Its direction is then forced, $u=A_B^{-1}{A}_j$. Walk along that edge until the first basic variable reaches zero, which fixes both the step length and the leaving variable. One column swaps, and the new corner is adjacent to the old, by construction, not by being nearby.

Why the student's picture is tempting. The word 'adjacent' carries an everyday sense of nearness, and in a small drawn polygon adjacent corners usually are close. The habit fails where the intuition is no longer checkable, which is every problem large enough to matter.

The edge geometrically. As the entering variable rises, each basic variable moves by $x_{B(i)}-\theta u_i$. With every $u_i\le 0$, no basic variable falls: they rise or hold steady. Nothing is driven towards zero, so no constraint becomes active however far you walk. The edge is a ray. It leaves the corner and never reaches another one.

What the ratio test returns. The minimum is taken over , which is empty. The minimum over an empty set is undefined, and there is no leaving variable. This is not a computation that fails; it is the test correctly reporting that nothing bounds the step.

The outcome. The entering variable increases without limit while feasibility holds, and each unit changes the objective by ${\overline{c}}_j=-3$. For a minimisation the objective falls forever, so the program is unbounded and there is no finite optimal value.

Why the region's shape is not enough. An unbounded region is necessary for an unbounded program but not sufficient. The region must extend without limit along a direction in which the objective improves. The same region admits a finite optimum under a different objective, minimising $x_1+x_2$ over $x_1-x_2\le 1$, $x\ge 0$ attains $0$ at the origin despite the region running on forever.

What the two facts together establish. The direction $u$ shows the region recedes along this edge, a fact about the constraints. The reduced cost ${\overline{c}}_j=-3$ shows the objective improves along it, a fact about the objective. Unboundedness needs both, and this single iteration has supplied both simultaneously.

Why this is the transfer. Adjacency was introduced as a relation between two corners. Here there is no second corner, and the same machinery, the direction, the ratio test, the reading of which rows bound the step, delivers a verdict about the whole program rather than a destination.