The bound flipping ratio test (BFRT) appears to be an important feature of modern Simplex implementations.
What is it, and how does it work?
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ I assume that the answers in google "bound flipping ratio test koberstein" don't satisfy you? $\endgroup$ – Marco Lübbecke Jul 3 '19 at 9:58
-
1$\begingroup$ The Koberstein paper is what I will be summing up in my own answer later, if noone else takes the opportunity first. $\endgroup$ – Michael Feldmeier Jul 3 '19 at 11:50
-
1$\begingroup$ ah, OK, you are still in beta mode... $\endgroup$ – Marco Lübbecke Jul 3 '19 at 12:10
-
1$\begingroup$ Does it really matter if it stays in beta? 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? $\endgroup$ – Mark L. Stone Jul 3 '19 at 18:44
Add a comment
|
$\begingroup$
$\endgroup$
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).
