Summary: In linear programming based branch-and-bound algorithms, many heuristics have been developed to improve primal solutions, but on the dual side we rely solely on cutting planes to improve dual bounds. We design a dual heuristic which incorporates relaxation algorithms within a branch-and-bound framework to improve dual bounds. We study the effect of solving various relaxations with dual heuristics by conducting a series of computational tests on the multi-dimensional knapsack problem.