Adjacent Basic Solutions

Two bases are adjacent when they differ in exactly one column. Under nondegeneracy the distinct corners they describe are joined by an edge of the feasible region; at a degenerate corner two adjacent bases can name the same point, and the edge between them has length zero. The edge has a direction computable from the basis, and moving along it until a basic variable reaches zero is what carries you from one corner to the next. This is the bridge between the static geometry of corners and the step the simplex method takes.

Definition

Let $B$ and $B^{'}$ be bases of the same standard-form system.

Adjacent bases. $B$ and $B^{'}$ are adjacent when they share $m - 1$ columns, differing in exactly one: one column leaves and one enters.

Adjacent basic feasible solutions. Two distinct basic feasible solutions are adjacent when they can be described by adjacent bases. Geometrically they are joined by an edge of the feasible region. A one-dimensional face.

Three relations, and when they coincide. Basis adjacency is combinatorial: a statement about columns. Vertex adjacency is geometric: a statement about points and edges. They correspond cleanly under nondegeneracy, where each basic feasible solution has exactly one basis and each basis swap moves you somewhere new. Degeneracy breaks the correspondence in both directions: a degenerate vertex is described by several bases, so two adjacent bases may name the same point and the swap takes a step of length zero; and the active sets of two adjacent vertices differ in exactly one constraint only when no extra constraint happens to pass through either. Read 'adjacent' as a relation between bases unless the nondegenerate case has been stated.

The edge direction. Fix a basis $B$ and a nonbasic index $j$ . Raising $x_{j}$ from zero to $θ$ while keeping $A x = b$ forces the basic variables to compensate. With

u = A_{B}^{- 1} A_{j},

the point moves to $x_{B (i)} - θ u_{i}$ in each basic coordinate, with $x_{j} = θ$ . The direction of travel is determined entirely by $B$ and the entering column.

Why exactly one column changes. Moving along the edge keeps every other nonbasic variable at zero, so every other active nonnegativity constraint stays active. Only one constraint is released, the entering variable leaving zero, and the walk ends when another becomes active, namely when some basic variable reaches zero. One constraint released, one acquired, and the basis differs by one column.

Feasibility of the move. The step is limited by the requirement $x_{B (i)} - θ u_{i} \geq 0$ . Only components with $u_{i} > 0$ fall towards zero and so bound the step; if none does, the edge is infinite in that direction.

Formal statement

$B, B^{'}$ adjacent iff $| B \cap B^{'} | = m - 1$ . Edge direction for entering $j$ : $d_{j} = 1$ , $d_{B (i)} = - u_{i}$ with $u = A_{B}^{- 1} A_{j}$ , $d_{k} = 0$ otherwise. Step limit: $θ^{*} = min_{i : u_{i} > 0} x_{B (i)} / u_{i}$ , unbounded if no $u_{i} > 0$ .

Assumptions and scope

Adjacency is defined between bases, and it transfers to points only through the corners those bases describe. At a degenerate corner two adjacent bases may describe the same point, so adjacent bases do not always mean distinct corners.
The edge direction depends on the basis and the entering column together. The same entering variable gives a different direction from a different basis.
Only components with $u_{i} > 0$ limit the step, since only those basic variables fall towards zero as the entering variable rises. This is the geometric reason for the restriction in the minimum ratio test.
If no component of $u$ is positive the edge extends without limit, and the region is unbounded in that direction. Whether the program is unbounded additionally depends on the objective.
Sharing an edge is not the same as being close. Adjacency is a combinatorial relation between active sets, and two adjacent corners may be arbitrarily far apart in distance.

Worked material

Example

Two bases, and the edge joining their corners

Take

\begin{aligned} x_{1} + x_{2} + x_{3} & = 4, \\ x_{1} + x_{4} & = 2, \\ x_{1}, x_{2}, x_{3}, x_{4} & \geq 0, \end{aligned}

with columns $A_{1} = (1, 1)^{T}$ , $A_{2} = (1, 0)^{T}$ , $A_{3} = (1, 0)^{T}$ , $A_{4} = (0, 1)^{T}$ .

Two bases. $B = {3, 4}$ gives $x_{3} = 4$ , $x_{4} = 2$ , so the point is $(0, 0, 4, 2)$ . And $B^{'} = {1, 3}$ gives $x_{1} = 2$ , $x_{3} = 2$ , so the point is $(2, 0, 2, 0)$ .

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

The edge direction from $B$ . With $A_{B} = (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}) = I$ , entering $j = 1$ gives $u = A_{B}^{- 1} A_{1} = (1, 1)^{T}$ . So as $x_{1}$ rises to $θ$ , $x_{3}$ falls to $4 - θ$ and $x_{4}$ falls to $2 - θ$ .

How far. Both components of $u$ are positive, so both rows bound the step: $4 / 1 = 4$ and $2 / 1 = 2$ . The minimum is $θ^{*} = 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^{'}$ . 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.

Non-example

What adjacency is not

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} \leq 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.

Contrast

Adjacency is combinatorial, not spatial

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 $θ^{*}$ 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 $θ^{*} = 4$ . Had $b$ been $(80, 8)^{T}$ instead, the same entering choice from the same basis would have travelled until $x_{4}$ hit zero, at $θ^{*} = 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.

Common errors

Common misconception

Adjacent corners are the ones closest together, so the simplex method moves to whichever neighbouring vertex is nearest.

Adjacent Basic Solutions

Assumptions and scope

Worked material

Two bases, and the edge joining their corners

What adjacency is not

Adjacency is combinatorial, not spatial

Common errors

Related units

Requires

Connected

Learn this topic

Used in

Sources

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history