J. Sudhoff, K. Klamroth, M. Stiglmayr
Bi-objective optimization problems on matroids are in general NP-hard and intractable, but if one of the objective functions is restricted to binary cost coefficients the problem becomes efficently solvable. A binary objective function often represents two categories and are thus a special case of ordinal coefficients that are in general non-additive.
In this talk we consider ordinal objective functions with more than two categories. This leads to a new class of optimization problems, which we investigate especially with respect to their set of non-dominated outcome vectors. We present a transformation of an ordinal objective function to vector-valued objective functions with non-negative integer values. We show that all suggested models are efficiently solvable by a matroid intersection algorithm.
Moreover, we discuss the application of this transformation to general combinatorial optimization problems with fixed cardinality and ordinal coefficients.
Keywords: matroid optimization, ordinal costs, matroid intersection, multi-objective reformulation
Scheduled
TD3 Game Theory and Multicriteria Decision
June 10, 2021 2:45 PM
3 - TC Koopmans
