Relaxation and dual-based heuristics have been a part of research in combinatorial optimisation since the early 1970s. This thesis extends that strand of research into less popular forms of relaxations in particular surrogate relaxation, which is theoretically a tighter relaxation than the two most common relaxations (Linear Programming and Lagrangian relaxations). The aim is to show surrogate dual information can add to the performance of dual-based matheuristics. In chapter 2 we provide some theoretical results related to surrogate and group relaxation. We follow it up with an exact and a heuristic surrogate dual method along with computation results, in chapters 3 and 4 respectively.

Finally, in chapter 5, we take a step back and seek to make an introductory empirical investigation into the value of good and better dual solutions in guiding primal heuristics using LP relaxation as an example.