Of particular concern in requirements engineering is the selection of requirements to implement in the next release of a system. To that end, there has been recent work on multi-objective optimization and user-driven prioritization to support the analysis of requirements trade-offs. Such work has focused on simple, linear models of requirements; in this paper, we work with large models of interacting requirements. We present techniques for selecting sets of solutions to a requirements problem consisting of mandatory and optional goals, with preferences among them. To find solutions, we use a modified version of the framework from Sebastiani et al. to label our requirements goal models. For our framework to apply to a problem, no numeric valuations are necessary, as the language is qualitative. We conclude by introducing a local search technique for navigating the exponential solution space. The algorithm is scalable and approximates the results of a naive but intractable algorithm.