Adjacent Basic Solutions

The simplex method moves from corner to corner by swapping one column. This unit explains why a single swap corresponds to walking along an edge rather than jumping across the region.

Two accounts are already in place. On one side, the static account: corners are basic feasible solutions, and there are finitely many. On the other, the simplex method: it swaps a column and arrives somewhere better. What has been missing is why a swap corresponds to a walk along an edge rather than a jump across the region.

The word 'adjacent' is used here without a definition. The precise version explains several things the informal one cannot: why exactly one variable enters and one leaves, why only some rows limit the step, and why a swap at a degenerate corner can fail to move at all.

This unit assumes you can construct a basic solution, take an active set, and state the correspondence between corners and bases.

The canonical text gives the wall-releasing picture. What it does not say is where that picture stops being reliable.

The step can be zero. Releasing one constraint gives a direction, and you travel until another constraint stops you. If a constraint is already tight at the starting corner without being one of the ones you were pressing against, the permitted travel is zero. You have changed which constraints you are naming and stayed exactly where you were. That is degeneracy, and it is why the walk metaphor and the algorithm part company.

Adjacency is defined on bases, not on the picture. The method exchanges one column for another because that is an operation it can perform; the geometric claim that it has walked an edge to a new corner is a consequence that holds when each corner has exactly one basis. When it does not, several bases name one point and a swap between them traverses nothing.

Which is why the ratio test is where the geometry lives. The entering variable chooses the direction; the ratio test decides how far, by finding which basic variable reaches zero first. That minimum is the length of the edge, and a zero minimum is the algebra reporting that there is no edge to walk.

The canonical statement gives the two definitions and says when they correspond. The interesting case is when they do not.

Under degeneracy the correspondence breaks in both directions. One vertex may be named by several bases, so two adjacent bases can describe the same point: a swap that is combinatorially a move is geometrically a stay. Conversely two genuinely adjacent vertices may be describable by bases differing in more than one column, so an edge exists that no single swap traverses.

This is why the simplex method is described as walking edges rather than visiting corners. The algorithm operates on bases, which is the combinatorial object; the geometric story of travelling along an edge to a better corner is a consequence that holds when the correspondence holds. Degeneracy is exactly where the story and the mechanism part company, and where an iteration count stops matching a count of corners.

What a swap changes. Raising one nonbasic variable from zero while the basic variables adjust to keep $Ax=b$ traces a line. The step stops when some basic variable reaches zero, which is the ratio test. Under nondegeneracy that step is positive and the objective strictly improves; that is the whole guarantee, and degeneracy removes it.

Take

with columns $A_1=(1,1{)}^{\mathsf{T}}$, $A_2=(1,0{)}^{\mathsf{T}}$, $A_3=(1,0{)}^{\mathsf{T}}$, $A_4=(0,1{)}^{\mathsf{T}}$.

Two bases. $B=\{3,4\}$ gives $x_3=4$, $x_4=2$, so the point is $(0,0,4,2)$. And $B^{\prime }=\{1,3\}$ gives $x_1=2$, $x_3=2$, so the point is $(2,0,2,0)$.

Are they adjacent? $B\cap B^{\prime }=\{3\}$, which has $m-1=1$ element. Yes, $x_4$ leaves, $x_1$ enters.

The edge direction from $B$. With , entering $j=1$ gives $u=A_B^{-1}{A}_1=(1,1{)}^{\mathsf{T}}$. So as $x_1$ rises to $\theta$, $x_3$ falls to $4-\theta$ and $x_4$ falls to $2-\theta$.

How far. Both components of $u$ are positive, so both rows bound the step: $4/1=4$ and $2/1=2$. The minimum is ${\theta }^{\ast }=2$, attained in the second row, so $x_4$ leaves.

Where it lands. $x_1=2$, $x_3=4-2=2$, $x_4=0$. The point $(2,0,2,0)$, which is the basic feasible solution of $B^{\prime }$. The walk arrived exactly where the algebra said it would.

The active sets. At $(0,0,4,2)$ the active restrictions are $x_1=0$ and $x_2=0$. At $(2,0,2,0)$ they are $x_2=0$ and $x_4=0$. They share $x_2=0$ and differ in one, which is the geometric reading of the one-column change.

Problem. For the system

decide whether $B=\{3,4\}$ and $B^{″}=\{1,2\}$ are adjacent. Then, from $B$, compute the edge generated by entering $x_1$ and the corner it reaches.

Goal. An adjacency verdict and a computed edge.

Relevant principle. Adjacency is decided by the overlap of the column sets, not by comparing the points.

Step 1: the adjacency verdict. $B\cap B^{″}=\mathrm{\varnothing }$, which has $0$ elements, not $m-1=1$. So $B$ and $B^{″}$ are not adjacent: they differ in two columns, and no single swap connects them. Any route between their corners takes at least two iterations.

Step 2: the starting point. $A_B=I$, so $x_3=8$, $x_4=8$, and the point is $(0,0,8,8)$.

Step 3: the edge direction. Entering $j=1$:

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

Step 4: the step limit. Both components of $u$ are positive, so both rows count:

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

Step 5: the corner reached. $x_1=4$, $x_3=0$, $x_4=8-4=4$. The point is $(4,0,0,4)$ with basis $\{1,4\}$.

Step 6: confirm adjacency of what we actually walked between. $B=\{3,4\}$ and $\{1,4\}$ share $\{4\}$, exactly $m-1=1$ column. Adjacent, as the walk requires.

Check. $(4,0,0,4)$ against the constraints: $8+0+0=8$ and $4+0+4=8$. Both hold, all components nonnegative.

What decided the direction. Nothing was chosen except which variable to raise. The rates at which $x_3$ and $x_4$ had to fall were forced by the equality constraints, and $u$ recorded them.

Not adjacency: being close together. Adjacency is a combinatorial relation between column sets. Two adjacent corners may be arbitrarily far apart in distance, and two corners very near each other in space may require several swaps to connect. Distance plays no part in the definition.

Not adjacent: bases differing in two columns. $\{3,4\}$ and $\{1,2\}$ in the worked example share nothing. One swap cannot connect them, and the corners they describe are not joined by an edge.

Not a free choice: the edge direction. Once the entering variable is named, $u=A_B^{-1}{A}_j$ is determined. There is no latitude about which way the edge runs; the constraints fix it.

Not a limit on the step: a row with $u_i\le 0$. That basic variable is rising or holding steady as the entering variable increases, so it never reaches zero and never ends the walk. Including it in the ratio test produces a meaningless number, and if it is negative, one that would be wrongly selected as the minimum.

Not always two distinct corners: adjacent bases at a degenerate point. When the corner is degenerate, a swap can produce a basis describing the same point. The bases are adjacent, the edge between them has length zero, and the walk goes nowhere. Adjacency of bases does not guarantee distinctness of the corners they name.

The word 'adjacent' carries an everyday suggestion of nearness, and the suggestion misleads in a way that produces wrong expectations about the simplex method.

The tempting picture. The method is at a corner, looks around at the neighbouring corners, and steps to whichever is nearest, or perhaps to whichever is nearest among those that improve the objective.

What is actually true. Adjacency is decided by column sets: two bases are adjacent when they share all but one column. That condition mentions no distances and no coordinates. Two adjacent corners can be a hair apart or half the region apart, and the step length ${\theta }^{\ast }$ is whatever the ratio test returns. It is a consequence of the walk, never a criterion for choosing it.

A concrete illustration. In the worked example, entering $x_1$ from $\{3,4\}$ travels a distance determined entirely by when $x_3$ hits zero, which was ${\theta }^{\ast }=4$. Had $b$ been $(80,8{)}^{\mathsf{T}}$ instead, the same entering choice from the same basis would have travelled until $x_4$ hit zero, at ${\theta }^{\ast }=8$, landing much further away. Same adjacency relation, same direction, very different distance. Nothing about the relation changed.

What the method actually selects on. The entering variable is chosen by the sign of its reduced cost, by the rate at which the objective improves along the edge, not by how far the edge goes or where it ends. A steep short edge and a shallow long one are judged by the same rule, and the rule looks at neither length.

Why the confusion is expensive. A learner expecting a nearest-neighbour walk will find the iteration count inexplicable, sometimes a long stride across the region, sometimes a step of length zero at a degenerate corner. Both are ordinary once adjacency is understood as a relation between active sets rather than a statement about proximity.

1. For the system $x_1+x_2+x_3=6$, $x_1+x_4=4$, $x\ge 0$, decide which pairs among $\{3,4\}$, $\{1,3\}$, $\{1,2\}$ and $\{2,4\}$ are adjacent.

2. From the basis $\{3,4\}$ in that system, compute the edge direction generated by entering $x_1$, the step limit, and the corner reached.

3. Repeat with $x_2$ entering. Which basic variable leaves, and why is the answer different?

4. Suppose an entering variable gives $u=(-1,-3{)}^{\mathsf{T}}$. What does the edge look like, and what does that say about the feasible region?

5. Two adjacent bases describe the same point. What must be true of that point, and what was the step length?

Two bases are adjacent when they share all but one column. Under nondegeneracy the distinct corners they describe are joined by an edge of the feasible region and their active sets differ in exactly one constraint. The same fact read algebraically and geometrically. Degeneracy breaks the correspondence: several bases can describe one corner, so adjacent bases need not name distinct points.

The edge direction is forced, not chosen. Naming the entering variable $j$ determines $u=A_B^{-1}{A}_j$, the rates at which the basic variables must compensate, and the direction $d$ with $d_j=1$ and $d_{B(i)}=-u_i$.

Exactly one column changes because exactly one constraint is released and one acquired: the entering variable rises off zero, the walk continues until some basic variable is driven to zero, and that one leaves.

Only components with bound the step, since only those are falling towards zero. If none is positive the edge runs on without limit, and the region is unbounded in that direction.

Adjacency is combinatorial rather than spatial. Adjacent corners may be far apart, the step length is an outcome of the ratio test rather than a criterion for the move, and at a degenerate corner two adjacent bases can name the same point with an edge of length zero between them.

This is the geometry a simplex iteration walks on. That unit decides which edge to take and executes the arithmetic; the edge itself, and why taking it is one column's worth of change, is what this unit supplies.