In this paper we propose new matheuristics for solving multidimensional knapsack problem. They are based on the variable neighbourhood decomposition search (VNDS) principle. The set of neighbourhoods is generated by exploiting information obtained from a series of relaxations. In each iteration, we add pseudo-cuts to the problem in order to produce a sequence of not only lower, but also upper bounds of the problem, so that integrality gap is reduced. General-purpose CPLEX MIP solver is used as a black box for solving subproblems generated during the search process. With this approach, we have managed to obtain results comparable with the current state-of-the-art heuristics on the set of large scale multidimensional knapsack problem instances. Moreover, we have reached a few new lower bound values for some of the test instances.