We modify the algorithm of Pardalos and Rodgers [40] for the minimization of a pseudo-boolean quadratic function by introducing an easy to compute lower bound as well as a variable fixation test, based on the concept of roof-duality. Numerical results show that the new algorithm outperforms the original algorithm of Pardalos and Rodgers.