Operations Research 2025
Abstract Submission

2328. Axiomatic Foundations and Polyhedral Characterizations for Ordinal Optimization

Invited abstract in session TA-5: Multiobjective Optimization 1: Non-standard Dominance Cones, stream Decision Theory and Multi-criteria Decision Making.

Thursday, 8:45-10:15
Room: H7

Authors (first author is the speaker)

1. Philipp Herrmann
Mathematics, RPTU Kaiserslautern
2. Kathrin Klamroth
Department of Mathematics and Informatics, University of Wuppertal
3. Stefan Ruzika
Mathematik, Rheinland-Pfälzische Technische Universität Kaiserslautern
4. Michael Stiglmayr
School of Mathematics and Natural Sciences, University of Wuppertal
5. Julia Sudhoff
Bergische Universität Wuppertal

Abstract

Ordinal optimization concerns mathematical optimization problems where the objective is to find optimal solutions based on ordered categories rather than precise numerical values. We present a unified theoretical framework for ordinal optimization in mathematics, where optimization problems are formulated using categorical rather than numerical rankings. Unlike traditional optimization that relies on quantitative comparisons, ordinal optimization addresses problems where natural orderings exist but precise numerical values may be absent or inappropriate, such as comparing bicycle routes with different combinations of "safe" and "unsafe" road segments.
Our main contribution is an axiomatic foundation consisting of six fundamental axioms that any suitable order must satisfy for effective ordinal optimization. We establish a correspondence between the class of orders satisfying these axioms and a specific family of convex cones, providing a complete characterization in terms of polyhedral cones. A key structural result concerns the properties of the associated tail cone.
We develop a linear transformation framework based on polyhedral cones that extends the approximation results of Papadimitriou and Yannakakis to the ordinal optimization setting. However, our analysis reveals computational limitations: for polyhedral cones with high complexity, the resulting algorithms exhibit exponential runtime behavior proportional to the number of hyperplanes defining the cone.
Our work provides both theoretical foundations and practical insights for researchers working with optimization problems involving categorical or ordinal data, with particular relevance to applications in operations research, decision theory, and multi-criteria optimization.

Keywords

Status: accepted

Back to the list of papers