9
$\begingroup$

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

What is it, and how does it work?

$\endgroup$
  • 2
    $\begingroup$ I assume that the answers in google "bound flipping ratio test koberstein" don't satisfy you? $\endgroup$ – Marco Lübbecke Jul 3 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 at 11:50
  • 1
    $\begingroup$ ah, OK, you are still in beta mode... $\endgroup$ – Marco Lübbecke Jul 3 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 at 18:44
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.