Partial orders provide a convenient way to express preferences on multiple criteria. Prominent examples are Pareto-dominance and the preference relations of (T)CP-nets [1]. In advanced personalized recommender systems, the user may also specify a partial order over the possible values of a single criterion. We introduce a technique called outer branching to compute the non-dominated frontier of optimization problems with partial orders. It can be used to compute all Pareto-optimal solutions for n criteria by performing a systematic search over the criteria space. Dominance constraints avoid the generation of non-optimal solutions.