In this chapter, a greedy randomized adaptive search procedure (GRASP) approach for solving the Quadratic Knapsack Problem (QKP) is presented. In addition, a new local search has been developed that manages to explore a larger neighborhood of a solution while maintaining the same asymptotical computational cost as the commonly used ones. The second contributions of this paper is the introduction of a new set of test instances, which makes it possible to better evaluate the performance of algorithms designed for the QKP. The performed computational experiments show that the developed GRASP algorithm is highly competitive with existing ones on the standard test instances. Further, we have used the new set of test instances to evaluate the performance of the newly proposed local search against the one commonly used for the QKP. These tests have shown that although the proposed local search overall outperforms the existing one, they have a notably different behavior. Further, our tests have shown that the proposed instances are significantly harder to solve than the standard benchmark ones.