Ordinal Optimization Through Multi-objective Reformulation

We analyze combinatorial optimization problems with ordinal, i.e., non-additive, objective functions that assign categories (like good, medium and bad) rather than cost coefficients to the elements of feasible solutions. We review different optimality concepts for ordinal optimization problems and discuss their similarities and differences. We then focus on two prevalent optimality concepts that are shown to be equivalent. Our main result is a bijective linear transformation that transforms ordinal optimization problems to associated standard multi-objective optimization problems with binary cost coefficients. Since this transformation preserves all properties of the underlying problem, problem-specific solution methods remain applicable. A prominent example is dynamic programming and Bellman's principle of optimality, that can be applied, e.g., to ordinal shortest path and ordinal knapsack problems. We extend our results to multi-objective optimization problems that combine ordinal and real-valued objective functions.


Introduction
Ordinal objective functions occur whenever it is only possible to represent the quality of an element by a ordered category and not by a numerical value. As an example, consider the problem of finding optimized routes for cyclists in a road network: While edges may be associated with different categories like asphalt, gravel or sand-or, when related to safety considerations, very safe (there is a bicycle path), neutral (a quiet road) or unsafe (a main road without bicycle path)-such categories do not immediately translate into monetary or cost values. Bi-objective shortest path problems with route safety criteria are addressed, for example, in the web application geovelo and in the associated publications Kergosien et al. (2021); Sauvanet & Néron (2010). In these references, only two categories are considered (safe or unsafe edges), and the safety criterion is translated into a cost function that evaluates the total length of unsafe route segments. In contrast, an ordinal shortest path problem is investigated in Schäfer et al. (2020). A major difficulty when considering ordinal objective functions is that "optimality" may be defined in many different ways. Schäfer et al. (2020) suggests an optimality concept that is based on sorted category vectors. A similar concept is used in Klamroth et al. (2021), where matroid optimization problems with one real-valued and one ordinal objective function are investigated. A different perspective is proposed in Schäfer et al. (2021) who define ordinal optimality for knapsack problems on the basis of numerical representations for the categories.
In this paper, we consider general combinatorial optimization problems and provide a new cone-based interpretation of the optimiality concept for ordinal objectives suggested in Schäfer et al. (2021). In particular, we interrelate ordinal optimality with the classical concept of Pareto optimality for an associated multi-objective optimization problem. For a general introduction to multi-objective optimization we refer to Ehrgott (2005). Since the underlying transformation of the objective function is linear and bijective and hence preserves the combinatorial structure of the respective problems, our results immediately lead to efficient solution strategies as, for example, dynamic programming for shortest path problems. The respective transformations are based on a representation of dominance relations by cones.
The paper is organized as follows. In Section 2 we review three optimality concepts for ordinal optimization based on Schäfer et al. (2021). These results and optimality concepts are then extended and re-interpreted as a special case of cone-optimality (see, e.g., Engau, 2007) in Section 3. A detailed analysis of the properties of the corresponding ordering cones then leads to a linear transformation of ordinal optimization problems to associated multi-objective optimization problems with the Pareto cone defining dominance and optimality. This transformation is used in Section 4 to formulate a general algorithm for solving ordinal optimization problems. Furthermore, we investigate the relation between the definition of ordinal optimality and the weight space decomposition of the associated multi-objective problem. In Section 5 we extend our results to more general problem types with additional real-valued objective functions. We conclude in Section 6 with a summary and an outlook on future research.

Problem Definition
We consider combinatorial optimization problems with an ordinal objective function. In general, an ordinal optimization problem (OOP) can be formulated as " ordinally minimize " o(x) where X is the set of feasible solutions. We assume that X is a subset of the power set of a discrete set S, i.e., X ⊆ 2 S . Every element of S is assigned to one of K ordered categories. This assignment is encoded by a mapping o : S → C with C = {η 1 , . . . , η K }. We assume that category η i with i ∈ {1, . . . , K − 1} is strictly preferred over category η i+1 , written as η i ≺ η i+1 . The objective function of a feasible solution x = {e 1 , . . . , e n } is given by the ordinal vector o(x) = sort(o(e 1 ), . . . , o(e n )), where the operator sort( ) means that the components of o(x) are sorted w.r.t. non-decreasing preferences, i.e., o 1 (x) ≺ = o 2 (x) ≺ = · · · ≺ = o n (x). Note that different feasible solutions may have different numbers of elements, and hence the length of the ordinal vector o(x) may vary for different x ∈ X.
Instead of using the un-aggregated, ordered ordinal vector o(x) one can count the number of elements in a feasible solution per category. Accordingly, we use the counting vector c : X → Z K ≧ with Z K ≧ := {y ∈ Z K : y i ≥ 0 for all i = 1, . . . , K}. Thereby, the i-th component of c(x) equals the number of elements in x which are in category η i , i. e., c i (x) = |{e ∈ x : o(e) = η i }|. Obviously, there is a one to one correspondence between the vectors o ∈ R n and c ∈ R K , since the ordinal vector o can be determined from a given counting vector c by o i (x) = η j with j = argmin{j ∈ {1, . . . , K} : i ≤ j l=1 c l (x)}. Note again that the number of elements n of a feasible solution, and hence the length of the ordinal vectors o ∈ R n , may vary while the number of categories K and therefore the length of the counting vectors c ∈ R K is fixed. Hence, we get the following formulation of an ordinal counting optimization problem (OCOP) which will be shown to be equivalent to problem (OOP) for an appropriate definition of "ordinal minimization". In the following, we also consider an incremental tail counting vectorc ∈ R K that counts, in its i-th component, the number of elements of a feasible solution x which are in category η i or worse, i.e.,c i (x) = |{e ∈ x : η i ≺ = o(e)}| = K j=i c j (x). In particular, the total number of elements of a solution x is given in the first component ofc, i.e., |x| =c 1 (x) = K i=1 c i (x). As an example, consider the shortest path problem shown in Figure 1 together with the outcome vectors o(x) (for problem (OOP)) and c(x) (for problem (OCOP)) for all feasible solutions x ∈ X. In addition, the incremental tail counting vectorc(x) is given for all x ∈ X.

Optimality Concepts for Ordinal Objective Functions
In the following, we review three different concepts of optimality for ordinal optimization. All of them try to answer the question what minimization could mean for the problems (OOP) and (OCOP). The first concept is to use numerical representations that assign a numerical value to every category such that the order of the categories is respected. In this context, a numerical representation respects the order of the categories whenever the numerical value of a o cc e 4 e 5 e 6 e 7 e 8 Figure 1: Instance of an ordinal shortest path problem. A dotted-green edge is in the best category η 1 , a dashed-orange edge is in category η 2 and a solid-red edge is in the worst category η 3 . All possible s − t paths x i , i = 1, . . . , 6 and their respective objective function vectors are given.
better category is strictly smaller than the numerical value of a less preferred category. If we take the sum over all numerical values of a vector o(x ′ ) for a feasible solution x ′ , we obtain a unique numerical value that can be compared to the corresponding numerical value of another feasible solutionx. A feasible solution x ′ is called efficient if there is no other feasible solutionx which is better w.r.t. all numerical representations. The second concept is to maximize the number of elements in the good categories, and the third concept is to minimize the number of elements in the bad categories. After the formal introduction of these three optimality concepts, we investigate their interrelation.
Optimality by Numerical Representations. We consider the problems (OOP) and (OCOP). The concept of optimality by numerical representation for ordinal objectives as introduced in Schäfer et al. (2021) is based on a previous and more general work of Fishburn (1999). It assigns an order preserving numerical value to each category. Following Schäfer et al. (2021), we call a function ν : Note that we assume strictly ordered categories, i.e., there are no categories that are indifferent. As a consequence, we do not allow ν(η i ) = ν(η j ) for i = j since this would make two different categories indistinguishable in the numerical representation. Let V denote the set of all numerical representations for a given number of categories K.
For a given numerical representation ν, we define the numerical value of a feasible solution x = {e 1 , . . . , e n } ∈ X w.r.t. ν (cf. Schäfer et al., 2021) as The numerical value ν(x) of a feasible solution x ∈ X can be evaluated in different ways by re-arranging the terms and using the counting vector c or the incremental tail counting vectorc, respectively: An illustration for different ways to evaluate ν(x) is given in Figure 2.
Example 1. We apply the concept of numerical representations to the shortest path problem given in Figure 1. As a motivation, suppose that there are two decision makers A and B who have to select a most preferred path. They would agree, for example, that path x 1 is worse than path x 2 , because x 1 has a dashedorange edge more than x 2 and, other than that, their outcome vectors are the same. But they do not agree on the question whether x 2 or x 5 is preferred, because decision maker A chooses the numerical representation ν A (η 1 ) = 1, ν A (η 2 ) = 2 and ν A (η 3 ) = 5, while decision maker B chooses ν B (η 1 ) = 2, ν B (η 2 ) = 3 and ν B (η 3 ) = 4. Therefore, decision maker A would prefer path x 5 because ν A (x 5 ) = 4 < 6 = ν A (x 2 ) while decision maker B would prefer path x 2 because ν B (x 2 ) = 6 < 7 = ν B (x 5 ). Hence, the path x 2 does not ordinally dominate the path x 5 , i.e., x 2 is not better than x 5 for all numerical representations. Similarly, the path x 5 does not ordinally dominate the path x 2 since also x 5 is not better than x 2 for all numerical representations. Figure 2: Consider an example with n = 7 and K = 4. Different ways to compute the numerical value of a feasible solution x with o(x) = (η 1 , η 2 , η 2 , η 3 , η 4 , η 4 , η 4 ) ⊤ , c(x) = (1, 2, 1, 3) ⊤ , ν(η 1 ) = 2, ν(η 2 ) = 4, ν(η 3 ) = 7 and ν(η 4 ) = 8 are illustrated. The different colors represent the summands and visualize the different slicing strategies.
Definition 2 (cf. Schäfer et al., 2021). Let x ′ ,x ∈ X be feasible solutions. Then, and c(x ′ ) weakly ordinally dominates c(x), denoted by , respectively, if and only if for every ν ∈ V, it holds that , respectively, if and only if x ′ weakly ordinally dominatesx and there exists ν * ∈ V such that ν * (x ′ ) < ν * (x). 3. x * ∈ X is called ordinally efficient, if there does not exist an x ∈ X such that x x * . 4. o(x * ) and c(x * ) are called ordinally non-dominated outcome vectors of Problem (OOP) and (OCOP), respectively, if x * is ordinally efficient.
Optimality by Maximization of Elements in Good Categories. Another optimality concept in ordinal optimization is to maximize the number of elements in good categories. The intuition behind this concept is that solutions with many good elements are to be preferred over solutions with few good elements. The drawback, however, is that this concept rewards solutions with larger numbers of elements as long as these are in (relatively) good categories, which may not be wanted in practice. This optimality concept is defined only for the problem (OCOP), as we need the counting vector c for its definition.
Definition 3. We say x ′ weakly head-dominatesx, denoted by x ′ ≧ hx or Optimality by Minimization of Elements in Bad Categories. The drawback that longer solutions may be preferred over shorter solutions, as long as the elements are in good categories, can be avoided by taking the converse perspective, i.e., when minimizing the number of elements in the bad categories. Again, this optimality concept is defined only for the problem (OCOP).
Definition 4. We say x ′ weakly tail-dominatesx, denoted by (2) , if and only if (2) holds and c(x ′ ) = c(x). Moreover, x * ∈ X is called tail-efficient if there is no x ∈ X such that x t x * . The corresponding outcome vector c(x * ) is called tail-non-dominated.
Remark 5. Note that head-dominance as well as tail-dominance are equivalently defined on the feasible set X ⊆ 2 S and on its image set c(X) ⊆ R K . The definitions immediately extends to the complete R K .

Properties of and Interrelations between Optimality Concepts for Ordinal Optimization
In addition to the concepts described above, there are further ways to define efficiency. This has been done, for example, in Schäfer et al. (2020) for the ordinal shortest path problem. Their definition has the disadvantage that Bellman's principle of optimality (see Bellman, 1957) does not hold in general, i.e., not every subpath of an efficient path is necessarily efficient w.r.t. this optimality concept. The definition of head-optimality has the same disadvantage, see Remark 10 below for more details. In contrast, the definitions of ordinal optimality and tail-optimality can be proven to be equivalent. Moreover, they are compliant with Bellman's principle of optimality. Note that, for the special case of a knapsack problem, this was shown in Schäfer et al. (2021).
Proof. First let ν ∈ V be an arbitrary numerical representation. Then ν( Note that since n < m, and due to the above assumptions, there must exist a category η j , j ∈ {1, . . . , K} such that c j (x) < c j (x ′ ). Therefore, there exists a numerical representation ν * such that ν * (η j ) > 0 and thus ν * (x) < ν * (x ′ ), which concludes the proof.
Note that the condition of Lemma 6 is always satisfied ifx, x ′ ∈ X withx x ′ . Thus, in Example 1 the path x 2 is always preferred over the path x 1 . This is also the case for tail-efficiency, but not for head-efficiency, see Remark 10 below. In many application contexts this is meaningful property, since adding additional elements to a solution (no matter from which category) does generally not improve the solution quality. As an example, we refer again to paths representing bicycle routes as in the app geovelo, where we are not interested in routes that are unnecessarily long.
Lemma 7 (Schäfer et al. 2021). The ordinal dominance relation ≺ = defined on the feasible set X is a preorder, i.e., it is reflexive and transitive.
for every ν ∈ V by definition and therefore, we have shown transitivity.
Note that the ordinal dominance relation ≺ = is in general not antisymmetric on the feasible set X since two different feasible solutions may have the same number of elements in each category like the paths x 3 and x 4 in Example 1.
The following two results show that (weak) ordinal dominance and (weak) tail-dominance are actually equivalent on the feasible set X.
Proof. The proof is a simplified variant of the proof in Schäfer et al. (2021). Note, that they consider maximization problems while we consider minimization problems.
First we show by contradiction that The idea of the proof is to make the bad categories η j * , . . . , η K very expensive, such that an element of this category can not be replaced by elements of the lower categories. Hence, we define the numerical representation For the other direction we use the reformulation of ν(x), which is visualized in Figure 2(c). It follows that for any ν ∈ V

The inequality holds because of the assumptionc
For the other direction it is sufficient to show that c( Now the result follows analogously to the proof of Lemma 8 with exchanged roles of x ′ andx. Remark 10. Lemma 8 (and thus also Lemma 9) does not hold in general for the relation h . As a counter example, consider the paths x 1 and x 2 with c(x 1 ) = (1, 1, 1) ⊤ and c(x 2 ) = (1, 0, 1) ⊤ from Figure 1. Obviously, x 1 headdominates x 2 . But for every numerical representation it follows ν(x 1 ) > ν(x 2 ), which contradicts Note that the crucial point in the counter example given in Remark 10 is the different cardinality of the solutions, |x 1 | = |x 2 |. For ordinal optimization problems with fixed cardinality, for which matroid optimization problems as studied in Klamroth et al. (2021) are an example, it can be shown that head-and taildominance are equivalent.
Lemma 11. If all feasible solutions have the same cardinality, i.e., if |x ′ | = |x| for all x ′ ,x ∈ X, then head-and tail-dominance as defined in Definitions 3 and 4, respectively, are equivalent.
Lemma 12. The relation ≦ t is a partial order on R K , i.e., it is reflexive, transitive and antisymmetric. Moreover, the relation t is a strict partial order on R K , i.e., it is irreflexive and transitive.
This implies that u = v and hence ≦ t is antisymmetric. Therefore, ≦ t is a partial order. Now consider the relation t . Since u t u for all u ∈ R K , it holds that t is irreflexive. It remains to show that t is transitive. Towards this end, consider three vectors u, v, w ∈ R K such that u t v and v t w. This implies . . , K and u = w, i.e., u t w. Consequently, we have shown that t is irreflexive and transitive which concludes the proof.
As a consequence of the discussion in Sections 2.2 and 2.3, we focus in the following on the ordinal optimization problem (OOP) w.r.t. optimality by numerical representation, or equivalently, on the ordinal counting optimization problem (OCOP) w.r.t. the concept of tail-dominance.

Ordinal Optimality versus Pareto Optimality: An Interpretation Based on Ordering Cones
A prominent example of an order relation in the context of multi-objective optimization is the component-wise order or Pareto order, see, e.g., Ehrgott (2005). For two vectors u, v ∈ R K , we write and say that u Pareto dominates v if and only if u v. The associated weak and strict component-wise orders, respectively, are defined by Note that ≦ defines a partial order in R K while as well as < define strict partial orders in R K .
In the following, basic properties of orders and their relation to cones are discussed and illustrated at the example of the Pareto order. This leads to a novel perspective on ordinal optimality in comparison to Pareto optimality.

Orders and Cones
Orders and cones are closely related. The following review of basic concepts relevant in our context is on Ehrgott (2005); Engau (2007); Ziegler (1995).
A cone in R K is a subset C ⊆ R K such that λ u ∈ C for all u ∈ C and for all λ ∈ R, λ > 0. A cone C ∈ R K is called pointed if u ∈ C implies that (−u) ∈ C for all u = 0. Moreover, a cone C ⊆ R K is called a polyhedral cone if there exists a matrix A ∈ R m×K \ {0} such that C = hcone(A) := {y ∈ R K : A y ≧ 0}. The rows of the matrix A are normal vectors of hyperplanes, and thus a polyhedral cone can be seen as the finite intersection of m (closed and linear) halfspaces. Polyhedral cones can also be described by their extreme rays. This property is an immediate consequence of the well-known Weyl-Minkowski Theorem: Theorem 13 (Weyl-Minkowski-Theorem, cf. Ziegler 1995). A cone C ⊆ R K is finitely generated by n vectors in R K , i.e., C = vcone(B) := Bλ : λ ∈ R n , λ ≧ 0 for some B ∈ R K×n if and only if it is a finite intersection of m halfspaces in R K , i.e., C = hcone(A) = y ∈ R K : A y ≧ 0 for some A ∈ R m×K . Now let C ⊂ R K be a cone. Then the sets are called the dual cone and the strict dual cone of C, respectively. Every cone C ∈ R K induces a binary (ordering) relation R ⊆ R K × R K by defining that (u, v) ∈ R if and only if (v −u) ∈ C. Depending on the context, we also write uRv whenever (u, v) ∈ R (as, for example, in the case of the binary relations defined in (3), (4) and (5) above). Binary relations that are induced by cones are always compatible with scalar multiplication, i.e., (u, v) ∈ R implies (λ u, λ v) ∈ R for all u, v ∈ R K and λ > 0. Moreover, they are compatible with addition, i.e., (u, v) ∈ R implies (u + w, v + w) ∈ R for all u, v, w ∈ R K .
Conversely, binary (ordering) relations that are compatible with scalar multiplication induce cones that represent the respective relation. The following result will be particularly useful in our context.
Lemma 14 (see, e.g., Ehrgott 2005). Let R ⊆ R K × R K be a binary relation on R K which is compatible with scalar multiplication. Then C R := {(v − u) ∈ R K : (u, v) ∈ R} is a cone, and C R induces the binary relation R. If R is additionally compatible with addition, then the following statements hold: It is easy to see that all three orders (3), (4) and (5) are compatible with scalar multiplication and addition. The component-wise order (3) induces the Pareto cone given by P : Similarly, the weak component-wise order (4) induces the closure of the Pareto cone given by R K ≧ = {y ∈ R K : y ≧ 0} = P ∪ {0}, which is a proper, pointed and convex cone (see Lemma 14). Moreover, it is a polyhedral cone that is defined by the identity matrix, i.e., P ∪ {0} = hcone(I) = vcone(I) (where I is the K × K identity matrix). Note also that the Pareto cone is self dual, i.e., P * = P .
Lemma 14 implies that binary relations R that are compatible with scalar multiplications can be equivalently represented by associated cones C R . This interrelation was used, among others, in Engau (2007) to define the concept of cone-efficiency (or C R -efficiency). For a general introduction to ordering cones in the context of vector optimization see, e.g., Tammer & Göpfert (2003); Jahn (2011).
Definition 15 (c.f. Engau 2007). Let Y ⊂ R K be a nonempty set and let C R ⊂ R K be a cone induced by a strict partial order R ⊂ R K × R K (i.e., R is irreflexive and transitive). Then the sets are called the C R -non-dominated and the weakly C R -non-dominated set of Y , respectively. The corresponding pre-images x ∈ X are called C R -efficient and weakly C R -efficient, respectively. Thereby, int(C R ) denotes the interior of C R .
Furthermore, we say that Note that when R is the component-wise order (or Pareto order) defined in (3), then C R = P is the Pareto cone in R K , N (Y, P ) is the non-dominated set (or Pareto set ) of Y , and N w (Y, P ) is the weakly non-dominated set of Y , see, e.g., Ehrgott (2005).

The Ordinal Cone
In the following we show that tail-dominance, represented by the binary relation t , is induced by a polyhedral cone in R K . We will refer to this cone as the ordinal cone. As a first step towards this goal, we prove that Lemma 16. The relation t is compatible with scalar multiplication and with addition.
Proof. To show that t is compatible with scalar multiplication, let λ > 0 and u, v ∈ R K with u t v. It follows that λ Furthermore, it holds that λ u = λ v, and hence λ u t λ v, which implies that t is compatible with scalar multiplication.
It remains to show that t is also compatible with addition. Let u, v, w ∈ R K with u t v, i.e., K i=j u i ≤ K i=j v i for all j = 1, . . . , K and u = v. This implies that K i=j (u i + w i ) ≤ K i=j (v i + w i ) for all j = 1, . . . , K and (u + w) = (v + w), i.e., u + w t v + w. Hence we have proven the compatibility with addition.
It can be proven analogously that ≦ t is also compatible with scalar multiplication and addition.
From Lemma 14 and Lemma 16 we can conclude that the cone C t := {(v −u) ∈ R K : u t v} induced by the strict partial order t is pointed, convex and it does not contain 0. We call this cone the ordinal cone to emphasize that C t equivalently represents ordinal dominance and show that its closure, the cone C t ∪ {0}, is a polyhedral cone that can be described as the intersection of K halfspaces.
Theorem 17. The closure of the ordinal cone is a polyhedral cone. In particular, it holds that C t ∪ {0} = hcone(A t ) with A t ∈ R K×K given by Proof. First note that 0 ∈ (C t ∪ {0}) ∩ hcone(A t ). It thus remains to show that for allũ ∈ R K \ {0}, it holds thatũ ∈ C t if and only if A tũ 0. Now letũ ∈ R K \ {0} with A tũ 0. We define u := 0 ∈ R K and v :=ũ. Hence, it holds v − u =ũ and Thus, we obtain hcone(A t ) \ {0} = C t , which concludes the proof.
Theorem 13 implies that the closure of the ordinal cone C t ∪ {0}, which is a polyhedral cone by Theorem 17, must also have a description based on a finite number of extreme rays. Indeed, the following result provides such a description based on exactly K extreme rays.
Theorem 18. It holds that hcone(A t ) = vcone(B t ) for A t defined according to Theorem 17 and B t ∈ R K×K given by Proof. We first show that hcone(A t ) ⊆ vcone(B t ). Let d ∈ hcone(A t ). Hence, it holds A t d ≧ 0 which is equivalent to K i=j d i ≥ 0 for all j = 1, . . . , K. Set λ j := K i=j d i ≥ 0 and let B j• denote the j-th row of B t , for j = 1, . . . , K.
Note that these descriptions of the closure of the ordinal cone C t ∪ {0} are not unique. Indeed, both the normal vectors in A t as well as the extreme rays in B t could be reordered, and they could be multiplied by arbitrary positive scalars without changing the cone that they define. In the particular description given in Theorems 17 and 18, however, we observe that the matrix B t is the inverse of the matrix A t , i.e., (A t ) −1 = B t .
Remark 19. It holds (hcone(A t )) * = hcone((B t ) ⊤ ) and (vcone(B t )) * = vcone((A t ) ⊤ ) since the normal vectors of the halfspaces given in A t are orthogonal to the extreme rays contained in B t .
It is easy to see that the Pareto cone, P , is a subset of the ordinal cone, C t . Moreover, the dual cone of the ordinal cone is a subset of the Pareto cone, i.e., (C t ) * ⊆ P ⊆ C t . This holds since z ∈ P implies that z 0 and hence A t · z 0, i.e., z ∈ C t . Moreover, z * ∈ (C t ) * is equivalent to (z * ) ⊤ c ≥ 0 for all c ∈ C t which implies z * i ≥ 0, because the i-th unit vector e i ∈ R K is contained in C t for all i = 1, . . . , K. These cones and their duals are visualized in Figure 3.
Remark 20. Note that head-dominance (c.f. equation (1)), represented by the binary relation h , also induces a polyhedral cone. Indeed, we have that Now we can use the ordinal cone C t as described in Definition 15 to reformulate the optimization problem (OCOP) as follows: Here, min C t denotes the minimization in the sense of Definition 15 for the ordinal cone C t = hcone(A t ) \ {0}. In other words, the C t -non-dominated set of problem (OCOP) is given by N (Y, C t ), where Y = c(X). In the following, we use this notation to clearly distinguish between the optimization w.r.t. different ordering cones.

Bijective Linear Transformation Between Ordinal and Pareto Optimization
In the previous subsection we showed that tail-dominance, and hence also ordinal dominance due to Lemma 9, can be equivalently described by the ordinal cone C t . Moreover, the closure C t ∪ {0} of the ordinal cone is the polyhedral cone hcone(A t ) = vcone(B t ) that is spanned by K linearly independent extreme rays in R K , c.f. Theorems 17 and 18. Since the closure of the Pareto cone P ∪ {0} is also a polyhedral cone that is spanned by K linearly independent extreme rays in R K (namely the K unit vectors in R K ), there exists a bijective linear transformation that maps the (closure of the) ordinal cone onto the (closure of the) Pareto cone.
We thus define the following transformed Pareto cone optimization problem where min P denotes the optimization w.r.t. the Pareto cone P according to Definition 15. Note that the objective vector of problem (TOP) corresponds to the incremental tail counting vectorc(x) = A t · c(x) ∈ R K introduced in Section 2.1, that counts in its jth component the number of elements of x that are in category η j or worse. Indeed, for a feasible solution x = {e 1 , . . . , e n } ∈ X we getc(x) = n i=1c (e i ), wherẽ Thus, problem (TOP) is actually a multi-objective optimization problem with K binary objective functionsc 1 , . . . ,c K defined on the ground set S, and with feasible set X ⊆ 2 S . Recall from Section 2.1 thatc 1 (e) = 1 for all e ∈ S and hencec 1 (x) simply counts the number of elements in a solution x ∈ X. Moreover, the vectorc(e) has the consecutive ones property in the sense that whenever a component ofc(e) is zero, then all subsequent components ofc(e) are also zero.
In order to show that the ordinal counting optimization problem (OCOP) (and hence the ordinal optimization problem (OOP)) can be solved by using the above transformation to the "standard" multi-objective optimization problem (TOP), we use a classical non-dominance mapping result for polyehdral cones. This result can be found in Engau (2007) and the references therein among several others. We include a proof, which is similar to the more general proof in Hunt & Wiecek (2003), for the sake of completeness.
Theorem 21 (see, e.g., Engau, 2007). Let Y ⊂ R K be a nonempty set and let hcone(A) be a cone induced by a matrix A ∈ R m×K . Then it holds Proof. This follows immediately from Lemma 9, the relation between orders and cones and Theorem 21.

Solution Strategies
In this section, we discuss a generic algorithmic framework for ordinal optimization problems that takes advantage of the close relationship to multiobjective optimization problems. Since the weighted sum scalarization is a popular approach in multi-objective optimization, the interpretation of weights in the context of ordinal optimization and Pareto optimization is analyzed in more detail, and their relation to numerical representations is discussed.

Ordinal Optimization by Pareto Transformation
From the theory above it follows that we can solve the problems (OCOP) and (OOP) by solving the transformed problem (TOP), which is a standard multi-objective combinatorial problem w.r.t. Pareto optimality. After the computation of the Pareto-efficient set of problem (TOP), or of a minimal complete Pareto-efficient set, respectively, it is necessary to re-compute the corresponding outcome vectors of either problem (OCOP) or (OOP). In this context, a minimal complete Pareto-efficient set of (TOP) is a subset of the Paretoefficient set that contains one Pareto-efficient solution for each Pareto-nondominated outcome vector. We refer to Serafini (1987) for different solution concepts in multi-objective optimization. The efficient sets of the problems (TOP), (OCOP) and (OOP) are equal and will be denoted by X eff in the following. The respective non-dominated sets are denoted by Y TOP nd := N (c(X), P ), Y OCOP nd := N (c(X), C t ) and Y OOP nd , respectively. A procedure for the computation of the efficient set and the respective non-dominated sets based on this Pareto transformation is outlined in Algorithm 1. // ... resp. obj. spaces 5 return efficient set X eff and non-dominated sets Y OCOP nd and Y OOP nd Note that the structural properties of the problems (OCOP) and (OOP) are preserved by the transformation as we do not change the feasible set and as the transformation of the objective function is linear and bijective. In particular, combinatorial solution strategies, like e.g. Bellman's principle of optimality for knapsack problems, can be applied in step 2 of Algorithm 1 to efficiently compute X eff . Ordinal optimization is thus in general no more complex that standard multi-objective optimization.

Weighted Sum Scalarization and Ordinal Weight Space Decomposition
In the following we investigate the interrelation between weighted sum scalarizations for (TOP) and (OCOP) and numerical representations for (OOP). Thereby we rely on the concept of weight space decompositions, which were introduced by Benson & Sun (2000) for multi-objective linear programming and extended to integer linear problems in Przybylski et al. (2010).
The weighted sum scalarization for (TOP) is with λ i > 0 for i = 1, . . . , K and K i=1 λ i = 1. Analogously, the weighted sum scalarization for (OCOP) can be formulated as s is the strict dual cone of the ordinal cone C t , and K i=1 µ i = 1. Recall that the strict dual cone (C t ) * s is the interior of the dual cone (C t ) * , which is visualized in Figures 3(e) and 3(k).
It is a well-known fact that when considering a multi-objective optimization problem, then optimal solutions of weighted sum scalarizations with weighting vectors λ ∈ R K > are always Pareto-efficient (see, e.g., Ehrgott, 2005). Such solutions are called supported efficient solutions. Thus, problem (WSTOP(λ)) always yields Pareto-efficient solutions for problem (TOP). Since (OCOP) can be interpreted as a multi-objective optimization problems w.r.t. the ordering cone C t , every optimal solution of the associated weighted sum problem (WSOCOP(µ)) with weights in the strict dual cone (C t ) * s of C t is ordinally efficient for (OCOP) (see, e.g., Engau, 2007).
The supported efficient solutions of problems (TOP) and (OCOP) are the same, hence there is a one-to-one correspondence between appropriate weighting vectors λ and µ. For a given λ ∈ R K > and x ∈ X we define µ i = i j=1 λ j for all i = 1, . . . , K. Then it holds that which shows that problems (WSOCOP(µ)) and (WSTOP(λ)) have the same objective functions in this case.
Note that µ i = i j=1 λ j and λ i > 0 for all i = 1, . . . , K implies that µ i < µ j for all i < j, as required. Conversely, weighting vectors µ ∈ (C t ) * s satisfy µ i < µ j for all i < j and hence yield associated weighting vectors λ ∈ R K > by setting λ 1 := µ 1 > 0 and λ i := µ i − µ i−1 > 0 for all i = 2, . . . , K. Note also that while the values of µ i = i j=1 λ j , i = 1, . . . , K (for given λ ∈ R K > ) are in general not normalized to satisfy K i=1 µ i = 1, such weighting vectors µ can be easily normalized by setting  The values on dashed lines may not be chosen for λ and µ, because for the weight space decomposition we assume that λ ∈ R K > and 3 i=1 λ i = 1, and for the ordinal weight space decomposition we require 0 < µ 1 < µ 2 < µ 3 and 3 i=1 µ i = 1.
Note that this normalization is applicable since (C t ) * s ⊂ R K > . As a consequence, a weight space decomposition for the multi-objective problem (TOP) can be translated into an associated ordinal weight space decomposition for the ordinal counting optimization problem (OCOP). In this context, a weight space decomposition subdivides the space of relevant weighting vectors λ ∈ R K > with K i=1 λ i = 1 into polyhedral cells such that all weighting vectors from the same cell generate the same efficient solution(s).
Example 24. In the shortest path problem of Example 1 the solutions x 2 , x 3 , x 4 and x 5 are efficient. In Figure 5 the corresponding weight space decomposition is depicted showing the values of λ and µ for which the respective efficient solution is obtained.
From yet another perspective, weighting vectors µ ∈ (C t ) * s , i.e., weighting vectors µ ∈ R K satisfying 0 < µ i < µ j for all i < j, are related to numerical representations as introduced in Section 2.2. Indeed, numerical representations assign a numerical value ν(η i ) to every ordinal category η i , i = 1, . . . , K, such that ν(η i ) < ν(η j ) whenever i < j. Hence we can chose the values µ i , i = 1, . . . , K, equal to the values ν(η i ) of any numerical representation that satisfies ν(η 1 ) > 0. These values can again be normalized without changing the optimal solutions of (WSOCOP(µ)) by setting It is important to note that this does not imply that numerical representations and weighted sum scalarizations are equivalent. Similarly, it is in general not possible to compute all ordinally efficient solutions of problem (OOP) by solving (WSOCOP(µ)) for an appropriate µ. To see this, recall that a solution x ′ ∈ X is called ordinally efficient for problem (OOP) if and only if there is nox ∈ X that ordinally dominates x ′ , i.e., if for everyx ∈ X there exists a numerical representation νx ∈ V such that νx(x ′ ) ≤ νx(x). In contrast, a solution x ′ ∈ X is optimal for problem (WSOCOP(µ)) with appropriate µ if and only if there exists a numerical representation ν * ∈ V such that ν * (x ′ ) ≤ ν * (x) for all x ∈ X.
Remark 25. Ordinal optimization problems may have non-supported efficient solutions. This is illustrated in Example 26. Hence, we can not expect to determine all efficient solutions with the weighted sum method.

Conflicting Real-valued Objectives and Ordinal Objectives
The results of Section 3 can be extended to multi-objective optimization problems that combine a finite number of p "standard" real-valued objective functions w j : X → R with a finite number of r ordinal objective functions o l : X → C l , l = 1, . . . , r, that are in mutual conflict. The number of categories in the l-th ordinal objective function is denoted by K l , i.e., C l = {η l 1 , . . . , η l K l } for l = 1, . . . , r.
For a feasible solution x = {e 1 , . . . , e n } ∈ X, we assume that w j (x) := n i=1 w j (e i ), j = 1, . . . , p. Moreover, o l (x) = sort(o l (e 1 ), . . . , o l (e n )) for l = 1, . . . , r. This leads to the multi-objective ordinal optimization problem with additional cost functions (MOOP): x ∈ X. (MOOP) By replacing the ordered vectors o l (x) for l = 1, . . . , r by the counting vectors c l (x) for l = 1, . . . , r we get a corresponding multi-objective ordinal counting optimization problem with additional cost functions (MCOP): x ∈ X. (MCOP) We denote the concatenated outcome vectors of (MCOP) as v(x) := w 1 (x), . . . , w p (x), (c 1 (x)) ⊤ , . . . , (c r (x)) ⊤ ⊤ ∈ R p+r , wherer := r l=1 K l . Then problem (MCOP) can be transformed into an equivalent standard multi-objective optimization problem w.r.t. Pareto dominance using a linear transformation that is defined by the block diagonal matrix Here, I p×p ∈ R p×p denotes the identity matrix and A l t is the transformation matrix corresponding to the objective c l for l = 1, . . . , r, c.f. Theorem 17. Thus, we get the multi-objective transformed Pareto cone optimization problem (MTOP) Now, problem (MOOP) or, equivalently, problem (MCOP) can be solved by using a simple adaptation of Algorithm 1, c.f. Section 4.

Coherent Real-valued Objectives and Ordinal Objectives
In some practical applications, the elements of S have a real-valued cost (e.g., the length of an edge) and an associated category (e.g., the safety of the corresponding road segment for a cyclist) such that the real-valued cost is, rather than in conflict, coherent with the respective category. This situation is illustrated at the following example: Example 28. Consider the shortest path problem shown in Figure 7. Let w(e) denote the length of an edge e and let o(e) denote its safety: dotted green edges are save and in category η 1 , while solid red edges are insecure and in category η 2 . Then, irrespective of the number of edges contained in the respective paths, the path x 1 = {e 1 , e 2 , e 3 } should be preferred over the path x 2 = {e 4 , e 5 , e 6 } since the total weights are equal w(x 1 ) = w(x 2 ) = 10), and the red sub-path in x 1 has a smaller weight than that of x 2 . In this sense, the weight or length of an edge can be interpreted as an attribute of its respective category. However, x 1 is dominated by x 2 w.r.t. problem (MOOP).
To model the situation where a real-valued objective function w : S → R is in accordance with an ordinal objective function o : S → C with K categories, i.e., the situation where the weight w(e) reflects the multiplicity with which the category o(e) of the element e is to be counted, we introduce a weighted counting The basic idea of this concept is also used in the risk-aware bicycle routing application geovelo, which takes, besides the route length, also the total length of unsafe route segments into account. For example, when K = 4, w(e) = 7 and o(e) = η 2 , then c w (e) = (0, 7, 0, 0) ⊤ . The weighted counting objective of a feasible solution x = {e 1 , . . . , e n } ∈ X equals the sum of the weighted counting vectors of all elements in x, i.e., c w (x) = n i=1 c w (e i ). Thereby, the i-th component of c w (x) corresponds to the total weight of the elements in x that are in category η i , i = 1, . . . , K. Now the weighted counting vector can be handled analogously to the counting vector. Indeed, as in the previous chapter we consider the transformationc w i (x) := K j=i c w j (x) = A t · c w (x) to obtain the weighted transformed Pareto cone optimization problem min Pc w (x) s. t. x ∈ X (WTOP) w.r.t. the concept of Pareto optimality, that can be solved with the methods developed in the preceding sections.

Modelling Aspects
We emphasize that it depends on the context of the respective application whether the multi-objective model (MTOP) or the aggregated model (WTOP) is more suitable. The following example illustrates that the aggregated model (WTOP) is meaningful whenever w and c are interrelated and coherent objectives, while the multi-objective model (MTOP) is particularly useful for unrelated or incompatible objectives.
Example 29. Consider again the shortest path problem depicted in Figure 7. Obviously, the path x 1 = {e 1 , e 2 , e 3 } is the unique efficient solution for problem (WTOP), while the path x 2 = {e 4 , e 5 , e 6 } is the unique efficient solution for problem (MOOP).
Whether x 1 or x 2 are actually preferred thus depends on the interpretation of the weights and of the ordinal categories. Towards this end, suppose that, as in Example 28, the category of an edge corresponds to its security level.
First, consider the case that the real-valued objective w(e) represents the length of the edge e as in Example 28. Then both objectives are interrelated and hence model (WTOP) is appropriate.
If, on the other hand, w(e) represents the toll of the edge or road e, then this real-valued objective is not an attribute of the corresponding category. In other words, both objectives are potentially conflicting and not coherent. Hence, in this case the path x 2 is preferred since the total amount of toll is the same for both paths, but the second path has more green and fewer red edges.

Conclusion
In this paper we investigate ordinal combinatorial optimization problems. We describe different optimality concepts for ordinal objective functions, namely ordinal optimality, which was introduced first by Schäfer et al. (2021), as well as tail-and head-optimality. We prove that all three concepts are equivalent if all feasible solutions have the same length. In general, only ordinal optimality and tail-optimality are equivalent.
We provide alternative descriptions of these three optimality concepts based on associated ordering cones. Using the fact that ordinal optimality and tailoptimality are equivalent, and that tail-optimality can be represented by a polyhedral cone with K extreme rays in R K , we show that ordinal optimization problems can be transformed into equivalent multi-objective optimization problems with binary cost coefficients. The transformation is realized by a bijective linear mapping. The resulting problem can be solved with standard methods from multi-objective optimization, and hence ordinal optimization is as easy or hard as the associated, "standard" multi-objective problems. For example, ordinal knapsack problems and ordinal shortest path problems can be solved by multi-objective dynamic programming, using Bellman's principle of optimality.
The results can be extended to problems with more than one objective function. We suggest two modelling approaches to combine an ordinal objective function with a real-valued objective function. While in the first approach all objectives are considered in a standard multi-objective setting, the second approach allows to model interrelated and coherent objective functions, where the real-valued objective is interpreted as an attribute of the respective category in the ordinal objective.
Future work should focus on the development of tailored optimization algorithms for the associated multi-objective optimization problems that exploit the fact that these problems have binary cost coefficients. Moreover, specific combinatorial problems like, for example, shortest path, knapsack, assignment and general routing and network flow problems should be analyzed both with coherent and with conflicting ordinal and real-valued objective functions.