ISBN 9783843947756

978-3-8439-4775-6, Reihe Mathematik

Luca Elias Schäfer
On Universal and Multiobjective Model Extensions for Combinatorial Optimization Problems

165 Seiten, Dissertation Technische Universität Kaiserslautern (2021), Hardcover, A5

Zusammenfassung / Abstract

Decisions are usually influenced by a variety of points of view, which can be reflected in different ways in mathematical decision or optimization problems. This thesis addresses the plurality of points of view that is inherently connected with decisions and points out various model extensions for classical combinatorial optimization problems in this respect.

More precisely, this work starts with an abstract definition of a complex system, which is composed of several interconnected, multiobjective subsystems. To this end, a graph-based model is introduced representing the decomposition of a complex system. The traditional terminologies of multiobjective optimization are generalized and different algorithmic procedures are presented that relate subsystems to each other and to the overall system.

Subsequently, two multiobjective model extensions of the maximum flow and shortest path interdiction problem are discussed, in which three players compete against each other in a graph. Two of the three players, called the followers, aim to optimize their respective objectives in the graph independently of each other, while the third player tries to maximally hinder both followers by interdicting arcs of the graph. The complexity is analyzed and exact as well as approximation algorithms are presented.

Afterwards, the shortest path and binary knapsack problem are altered by introducing ordinal evaluations. To this end, dominance relations are introduced to compare feasible solutions with respect to their ordinal levels. By using these relations, algorithmic procedures for the computation of single and all optimal solutions are developed.

Finally, the near-shortest paths problem is generalized by introducing a universal weight vector. Two recursive algorithms computing the set of all near-shortest paths with respect to a universal weight vector are provided and the running-time complexity per path enumerated is analyzed.