The bin packing problem is one of the classic NP-hard combinatorial optimization problems. Given a set of n items with positive sizes, the objective is to find a packing in bins of equal capacity to minimize the number of bins required. The problem finds obvious practical usage in many industrial applications, such as the container loading problem and the cutting stock problem. There are also many variations of the bin packing problem, such as the strip packing, square packing and rectangular box packing problems. We consider the three-dimensional orthogonal bin packing problem and present new lower bounds for the problem from a combinatorial point of view. In particular, we demonstrate that the bounds theoretically dominate all previous results from the literature. The comparison is also done concerning asymptotic worst-case performance ratios. The new lower bounds can be more efficiently computed in polynomial time. In addition, we study the non-oriented model, which allows items to be rotated (more details).