Am I right that the basis in the revised simplex should never be singular?
I programmed the algorithm by my own and after several hundreds of steps the basis becomes singular.
Does this might be occur due to a rounding error somewhere and is there any standard behavior how to get around this?
Normally a singular matrix means that the problem is infeasible, right?
In my problem I'm 100% sure that it is feasible.
So the main question is: Is it "normal" that a basis might be singular due to rounding errors? And also how can I solve this?
You are correct that the basis matrix should never be singular.
Yes, rounding error could account for this.
There are three things that might help avoid it (two algorithmic, one related to the model being solved). First, never invert the basis matrix. It's both slow and (I think) more vulnerable than other methods to rounding problems. Use some kind of matrix factorization (LU, SVD, ...). I don't write solvers, so I can't recommend a specific one over the others.
Typically the factorization is updated incrementally with each pivot, rather than refactoring the basis matrix each time. So the second suggestion is to periodically refactor the basis matrix, to flush out accumulated rounding errors.
The third (model related) suggestion is to avoid having both very large magnitude and very small magnitude constraint coefficients. Once the ratio of the largest to the smallest (nonzero) coefficient gets up around 10^14 (give or take), you're begging for rounding problems.
Note: If you programmed it the way it's taught in introductory books (pivoting via Gaussian elimination), and you want to stick with that, then at least adopt a version of refactoring. Every so often, go back to the original tableau and pivot on the columns of the current basis matrix (ignoring the reduced costs), to get back to the current basis. That will shake out some decimal dust.
No, a singular basis matrix does not mean the problem is infeasible: it means you don't have a valid basis.