about adjacent vertices in LP

[Xiaosong DING]

Given an LP, when variables have upper and lower bounds, it is possible for two vertices to have the same set of basic variables but different values, due to a non-basic variable switching between its lower and upper bounds. Whether these two vertices are considered adjacent depends on how adjacency is defined:

1. Adjacency in the Standard Simplex Method (Without Bound Constraints) In the classical simplex method (where variables are only subject to non-negativity constraints and no upper bounds), two vertices are considered adjacent if and only if their basic variable sets differ by exactly one variable—that is, one variable enters the basis while another leaves.

2. Adjacency When Bounds Are Present When variables have both upper and lower bounds, a non-basic variable can switch between its lower and upper bounds, which may change the values of some basic variables while keeping the same basic variable set. In this case:

   • The non-basic variable remains non-basic but moves between its lower and upper bounds, potentially affecting the values of the basic variables.

   • Since the set of basic variables does not change, according to the classical simplex definition, these two vertices are not adjacent.

   • However, from a geometric perspective, they are directly connected on the feasible region’s boundary.

The question is: the same basis with different solution vectors, can they be considered adjacent vertices in LP?

Many thanks!

Cris