In many interactive decision making scenarios there is often no solution that satisfies all of the user's preferences. The decision process can be helped by providing explanations. Relaxations show sets of consistent preferences and, thus, indicate which preferences can be enforced, while exclusion sets show which preferences can be relaxed to obtain a solution. Many approaches have been proposed to generate relaxations of over-constrained sets of constraints. However, most focus on generating a single relaxation. In this paper we study a variety of heuristic methods for generating diverse sets of relaxations. We show that a heuristic based approach can generate diverse relaxations quickly enough to support user interaction. We also describe a prototype explanation visualisation tool that can help a user navigate over diverse sets of explanations.