Continuous improvements of Local search techniques on Maximum Satisfiability Problem (MaxSAT) solving have resulted in a real scaling up and widening of the class of real-world problems that can be solved in practice. But MaxSAT has a poor expressive power, which make it difficult to deal with Pseudo Boolean Optimization Problems (PBO). Most of the current PBO algorithms are based on branch and bound techniques, and there is almost no local search algorithm for PBO. Recently, Extended CNF (ECNF) was proposed to deal with cardinality constraints, which is a special case of PB constraints. In this paper, we develop an efficient local search algorithm LS-PBO for PBO. Our algorithm LS-PBO adopts a well designed weighting scheme and a new scoring function. LS-PBO is compared with the methods based on other models, including MaxSAT, ECNF, Pseudo-Boolean Optimization (PBO), and Integer Linear Programming (ILP). Experiments are carried out with three real world application benchmarks, including Minimum-Width Confidence Band, Wireless Sensor Network Optimization problems, as well as Seating Arrangements Problem. Experiment results show that our solver has much better performance than the state of the art solvers based on other models, which indicates solving PBO problem with local search is promising.