Ordinal optimization through multi-objective reformulation
From MaRDI portal
Abstract: 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.
Recommendations
- Multi-objective ordinal optimization for simulation optimization problems
- scientific article; zbMATH DE number 175991
- Multi-objective matroid optimization with ordinal weights
- Ordinal optimisation and simulation
- Constraint ordinal optimization
- Ordinal optimization of DEDS
- Vector ordinal optimization
- Ordinal Optimization
- Publication:3491331
- Constrained ordinal optimization -- a feasibility model based approach
Cites work
- A recursive algorithm for finding all nondominated extreme points in the outcome set of a multiobjective integer programme
- Adaptive parametric scalarizations in multicriteria optimization
- Algorithmic improvements on dynamic programming for the bi-objective \(\{0,1\}\) knapsack problem
- An Efficient Label-Correcting Algorithm for the Multiobjective Shortest Path Problem
- Assignment Problems
- Binary interactions and subset choice
- Committee Selection with a Weight Constraint Based on a Pairwise Dominance Relation
- Computational Results for Four Exact Methods to Solve the Three-Objective Assignment Problem
- Computing representations using hypervolume scalarizations
- Fair division of indivisible items
- Fair division under ordinal preferences: computing envy-free allocations of indivisible goods
- Finite linear qualitative probability
- scientific article; zbMATH DE number 5842432 (Why is no real title available?)
- scientific article; zbMATH DE number 3126094 (Why is no real title available?)
- scientific article; zbMATH DE number 4070651 (Why is no real title available?)
- scientific article; zbMATH DE number 2159094 (Why is no real title available?)
- scientific article; zbMATH DE number 2160602 (Why is no real title available?)
- scientific article; zbMATH DE number 2107164 (Why is no real title available?)
- scientific article; zbMATH DE number 1423920 (Why is no real title available?)
- scientific article; zbMATH DE number 3339018 (Why is no real title available?)
- Lectures on Polytopes
- Minimal paths on ordered graphs
- Multi-objective matroid optimization with ordinal weights
- Multicriteria Optimization
- On the representation of the search region in multi-objective optimization
- Outcome space partition of the weight set in multiobjective linear programming
- Preference structures and their numerical representations
- Scalarizing vector optimization problems
- Search for the best compromise solution on multiobjective shortest path problem
- Shortest paths with ordinal weights
- Solving efficiently the 0-1 multi-objective knapsack problem
- Sorted-Pareto dominance and qualitative notions of optimality
- The binary knapsack problem with qualitative levels
- The multiobjective multidimensional knapsack problem: a survey and a new approach
- Vector Optimization
Cited in
(9)- An explanation of ordinal optimization: Soft computing for hard problems
- Solving group multi-objective optimization problems by optimizing consensus through multi-criteria ordinal classification
- First order rejection tests for multiple-objective optimization
- Multi-objective ordinal optimization for simulation optimization problems
- Quantifying heuristics in the ordinal optimization framework
- On the computational complexity of ordinal multi-objective unconstrained combinatorial optimization
- Using ordinal optimization approach to improve efficiency of selection procedures
- On quasi-orderings and multi-objective functions
- Ordinal optimization and quantification of heuristic designs
This page was built for publication: Ordinal optimization through multi-objective reformulation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6096566)
