Linear Pseudo-Boolean Optimization (PBO) has found applications in several areas, ranging from Artificial Intelligence to Electronic Design Automation. Due to important advances in Boolean Satisfiability (SAT), new algorithms for PBO have emerged, which are effective on highly constrained instances. However, those algorithms fail in dealing properly with the objective function of PBO. This paper proposes an algorithm that uses lower bound estimation methods for pruning the search tree in integration with techniques from SAT algorithms. Moreover, the paper shows that the utilization of lower bound estimates can dramatically improve the overall performance of PBO solvers for specific classes of instances. In addition, the paper describes how to apply non-chronological backtracking in the presence of conflicts that result from the bounding process, using different lower bound estimation methods.