I'm currently trying to write some code that implements Phase I of the two-phase Simplex Algorithm described here: http://www.statslab.cam.ac.uk/~ff271/teaching/opt/notes/notes8.pdf

In order to test whether Phase I was successful, one must check the value of the objective function at the end of the algorithm to see whether it's zero. The issue is, since the objective function is a float to which other floats are added and subtracted throughout the algorithm, the computer may not say it's exactly zero at the end even though with infinite precision, it would be. So my question is: would it be sufficient to just check whether the objective function is within, say $10^{-8}$ or so of zero? Or is that likely to give false positives?

I had another idea I could also try, which is to just check whether or not any of the auxiliary variables are still basic variables at the end of phase I to see if it was successful. The issue with this is that if the right hand side of the simplex tableau has any zeroes in it, you could have a situation where one of the auxiliary variables is still a basic variable, but its value is zero, which would give you a false negative by this check.

  • $\begingroup$ Depends on what size of numbers you are working with. If the numbers are integers, $10^{-8}$ seems fine to me. However if the numbers are a lot smaller like $10^{-6}$ I would pick a smaller threshold. $\endgroup$ – Jan Jul 16 '15 at 16:05
  • $\begingroup$ The initial numbers in the simplex tableau will all be on the order of 1 in my algorithm, so I guess I'll go with $10^{-8}$. $\endgroup$ – Izzhov Jul 16 '15 at 16:09

Your Answer

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

Browse other questions tagged or ask your own question.