The bound flipping ratio test (BFRT) appears to be an important feature of modern Simplex implementations.
What is it, and how does it work?
Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.Sign up to join this community
When taking a step in the dual simplex method, if a dual variable is zeroed, the dual objective may continue to improve if the variable passes through zero. To maintain dual feasibility, the variable must be associated with a primal variable with finite lower and upper bounds. As the dual variable passes through zero, the corresponding primal variable [which is necessarily nonbasic] "flips" from one bound to the other. This process changes the gradient of the dual objective, making it less attractive to make a further change in the dual variable. Thus, eventually, the ratio test will terminate (unless the LP is dual unbounded).