8

The bound flipping ratio test (BFRT) appears to be an important feature of modern Simplex implementations.

What is it, and how does it work?

Michael Feldmeier
  • 2,856
  • 14
  • 40
  • 2
    I assume that the answers in google "bound flipping ratio test koberstein" don't satisfy you? – Marco Lübbecke Jul 03 '19 at 09:58
  • 1
    The Koberstein paper is what I will be summing up in my own answer later, if noone else takes the opportunity first. – Michael Feldmeier Jul 03 '19 at 11:50
  • 1
    ah, OK, you are still in beta mode... – Marco Lübbecke Jul 03 '19 at 12:10
  • 1
    Does it really matter if it stays in beta? https://scicomp.stackexchange.com/ has been in beta for over 7 1/2 years and I think is doing just fine..People there aren't posting questions just for the sake of posting questions, or artificially breaking up questions into a bunch of little pieces just to have more questions. If the OR site "wins" by being promoted out of beta, is that a real victory if it comes at the cost of clutter and questions for the sake of questions? – Mark L. Stone Jul 03 '19 at 18:44

1 Answers1

5

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).

SparseRunner
  • 362
  • 1
  • 9