Restricted basis entry rule

From Glossary

Jump to: navigation, search

This is a restriction on which variables can enter the basis in a simplex method. A common rule arises in separable programming, which uses specially ordered sets: a group of non-negative variables must sum to 1 such that at most two variables are positive, and if two are positive, they must be adjacent. For example, suppose the variables are LaTeX: (x_1,x_2,x_3). Then, it is feasible to have LaTeX: (.5,.5,0) and LaTeX: (0,.2,.8), but it is not feasible to have LaTeX: (.5,0,.5) or LaTeX: (.2,.2,.6). In this case the rule is not to permit a variable to enter the basis unless it can do so without violating the adjacency requirement. For example, if LaTeX: x_1 is currently basic, LaTeX: x_3 would not be considered for entry.

Another restricted entry rule pertains to the delta form of separable programming (plus other applications): Do not admit a variable into the basis unless its predecessor variables are at their upper bound. This means there is an ordered set of bounded variables, say LaTeX: (x_1,x_2,\dots,x_n) such that LaTeX: \textstyle 0 \le x \le (U_1,\dots,U_n). Then, LaTeX: x_k is not considered for basis entry unless LaTeX: x_j=U_j for all LaTeX: j < k.

Personal tools